搜索
队伍信息表队伍基本情况介绍（数学基础，编程基础，队伍基本分工）三名队员均具备数学分析、高等代数、概率论与数理统计、数值分析、常微分方程、离散数学、数学建模、运筹学等课程的数学基础；会使用字处理软件“word”、电子表格“excel”、matlab软件、lingo软件、SAS软件等；具备c语言、Java编程基础。队长负责整理综合所有人就建模题目一起讨论的结果，在建模过程中及时收集整合队员的创新性想法，进行整体分析，统筹建模大局，列出建模步骤，给自己和两名队员分配任务，把握建模进度。一名队员主要负责计算机的运用，应用字处理软件“word”，电子表格“excel”，matlab软件、lingo软件等进行模型的相关制图，并用Java编写程序且运行得出结果。另一名队员具有较好的论文写作能力，按照严格的格式要求，综合三个人的思路和个人建模任务完成的成果，清楚地叙述摘要内容，有条理地的把建立模型、设计算法、求解模型等步骤写在论文中，从而完成本数学建模的论文。DNA序列的k-merindex问题摘要DNA序列片段索引在基础生物学研究和在众多的应用领域，如诊断，生物技术，法医生物学，生物系统学中，有着极其重要的应用价值。本文利用Java软件、Rabin-Karp算法和哈希算法，建立了DNA序列数据索引的数学模型及算法，解决了基因序列数据索引的问题。在保证调用100万条DNA序列完整性、准确性和连续性的同时，设计出查询速度尽量快，所用内存尽量小的数据索引方法，并给出建立索引和使用索引所用的计算复杂度和空间复杂度分析。针对问题1，由于100万条DNA序列数据量庞大，所以本文先将原始数据的字符串reads表示成二进制（A=00，C=01，G=10，T=11），通过编写Java程序读取。再将二进制采用Rabin-Karp算法转化成唯一十进制数字存入哈希表。通过此算法的哈希函数，对给定一个确定的k值，将每条DNA序列分成100-k+1个长度为k的k-mer短序列，把一个k-mer里面所有字符的hash值求和。也就是将一个字符串（模式串）转化成为能够快速进行比较的哈希值。任意给定一个k-mer短序列，将对应的十进制数哈希值在100万条DNA序列中进行索引，返回该短序列所在DNA序列编号和相应序列出现的位置。针对问题2，由顺序算法优化成二分法，将k-mer的所有序列哈希值按照升序排列，对给定的k-mer哈希值x，从第一个DNA序列的中间位置开始比较，如果当前位置等于x，则查找到其中一个并记录下来位置信息，再继续查找；如果x小于当前位置值，则在数列的前半段位置查找；如果x大于当前位置值，则在数列的后半段位置查找；直到找出该条DNA序列全部所求位置信息。再进行第二条、第三条直至100万条DNA序列结束。针对问题3，得出建立索引计算复杂度为kT().1log().1sizealsizealO。空间复杂度为nS=1O。针对问题4，得出使用索引查询的时间复杂度是：nOnT。空间复杂度为)4*(kNlO。针对问题5，通过Java程序的反复运行，得出8G内存下所涉及索引方法所能支持的最大k值为67。在索引程序中使用了hash算法（hash表在JDK中的一个实现就是HashMap）来缓存一些数据，从而提高系统的运行速度。Java使用了有向图的方式进行内存管理，尽管可以消除引用循环的问题，但是效率较低。针对问题6，通过模糊综合评价法对索引方法性能进行评价，并对所建立的模型和求解方法的优缺点给出客观分析。最后，对所建立模型进行实际应用的推广。关键词：数据索引；Java软件；二进制；Rabin-Karp算法；哈希算法；二分法；时空复杂度；Proid索引优化；模糊综合评价法。一、问题的重述与分析1.1问题背景生物信息学是20世纪80年代末，随着人类基因组计划的不断发展，基因序列和蛋白质数据的急速增加，以及信息理论和计算机技术的不断发展而逐渐形成的。在过去的十几年中人类对生物信息学，特别是DNA和人类基因序列的研究取得了长足的发展。海量DNA序列的测试完成和发布使人们可以利用计算机技术对包括DNA、RNA和蛋白质等生物序列进行分析，为生物学家提供更多有价值的信息。而DNA序列库的庞大使得它在运用时遇到困难，本文致力于通过建立DNA序列索引的办法，更快更省空间的完成对目标k-mer序列的查找以及相关首位置的返回工作。1.2问题提出给定一个DNA序列，这个序列只含有4个字母ATCG，如S=“CTGTACTCTAT”。给定一个整数值k，从S的第一个位置开始，取一连续k个字母的短串，称之为k-mer（如k=5，则此短串为CTGTA），然后从S的第二个位置，取另一k-mer（如k=5，则此短串为TGTAC），这样直至S的末端，就得一个集合，包含全部k-mer。如对序列S来说，所有5-mer为{CTGTA,TGTAC,GTACT,TACTG,ACTGT,TGTAT}.通常这些k-mer需要一种数据索引方法，可被后面的操作快速访问。例如，对5-mer来说，当查询CTGTA，通过这种数据索引方法，可返回其在DNA序列S中的位置为{1,6}。问题：现在以文件形式给定100万个DNA序列，序列编号为1-1000000，每个基因序列长度为100。（1）要求对给定k，给出并实现一种数据索引方法，可返回任意一个k-mer所在的DNA序列编号和相应序列中出现的位置。每次建立索引，只需支持一个k值即可，不需要支持全部k值。（2）要求索引一旦建立，查询速度尽量快，所用内存尽量小。（3）给出建立索引所用的计算复杂度，和空间复杂度分析。（4）给出使用索引查询的计算复杂度，和空间复杂度分析。（5）假设内存限制为8G，分析所设计索引方法所能支持的最大k值和相应数据查询效率。（6）按重要性由高到低排列，将依据以下几点，来评价索引方法性能索引查询速度索引内存使用8G内存下，所能支持的k值范围建立索引时间1.3问题分析1.3.1问题一分析本题要求建立数据索引办法，使得对于给定k值，可以返回任意一个k-mer所在的DNA序列编号和相应序列中出现位置。即如题中所给例子，索引运行过程如下图1.3.2问题二分析建立的索引，需要查询速度尽量快，所用内存尽量小。通过相关算法来实现。因此我们引用二分法，使用二分法可以减少数据比对次数，从而加快对相关数据的检索。图二分法过程示意图而同时我们将ATCG分别用“00011011”来表示，也就是使用二进制来表示，二进制数在计算机中的空间占用内存大大小于字符在计算机中的占用空间。1.3.3问题三分析1.本题要求对100万个DNA序列建立的索引进行时空复杂度分析。前面已经将AGCT转化成了二进制，接下来就是将对应的数据块的每一项进行索引。即采用一种顺序访问的技术，对大数据块排好序后，再进行线性向下查找比对。分析时间复杂度即先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出nT的同数量级。2.在建立DNA序列索引过程中，以文件形式给定的100万个DNA序列因为随时供索引调用，所以将数据以文件形式存放在本地磁盘中，即形成g://123.txt。再者需要根据给定基因组索引表来获得待比对数据块的位置和大小，所以这个索引表必须常驻内存。索引表每项是一个二元组index，num使用两个4字节整型存储，又由于经常访问整个基因组序列，也要把参考基因组序列存入内存。1.3.4问题四分析1.将read转化成定长的k-mer，并将这些k-mer存入，以备之后查找使用。此时要设定的一个重要参数是k-mer的长度。选定值之后，要将长度的read拆成个k-mer。并且给定k-mer后，要快速的找到该k-mer出现在哪些read的哪些位置上。故要给每个read一个编号，称为readID，我们只需保存readID即可。我们设计了如下的数据结构，称为readID_pos数组，每个k-mer都关联一个readID_pos数组，其中readID是我们给没条read的一个编号，在deBruijn图中，一个readID能唯一识别一条read。readID是升序保存的，便于以后的二分查找操作。pos是该k-mer出现在编号为readID的read中的位置。最后考虑二分法和基于Rabin-Karp的Hash算法的复杂度。2.我们将所有的k-mer存在一个哈希表中，哈希表实际上就是一个超大数组，以每个k-mer的哈希值作为下表就可找到该k-mer的所有信息。其一需要计算k-mer结构大小，如kmer_seq是无符号整型，占4字节，str是指针，在64位操作系统上占8字节。然后再考虑给定DNA序列信息调用时使用数组和匹配时所占用的内存即可。1.3.5问题五分析1.我们利用二分法、Rabin-Karp算法和Hash算法来建立索引而所能支持的k值与程序运行（索引、查找和匹配）时所使用的内存有关。基于建立的索引程序，我们尝试选取不同K值来运行程序，根据程序的运行结果，推测索引方法所能支持的最大k值。2.对于分析相应数据查询效率：使用hash算法（hash表在JDK中的一个实现就是HashMap）来缓存一些数据，从而提高系统的运行速度。正如要索引100万个DNA序列信息，就使用HashMap缓存信息，这样就大大减弱了我们对每个DNA序列进行索引和查找匹配的效率。另一方面，使用Java编程一个最大的优点就是取消了指针，由垃圾收集器来自动管理内存的回收。1.3.6问题六分析对于我们在建立和使用索引时用到的方法：二分法、哈希算法和Rabin-Karp算法等方法进行评价，即基于他们各自的程序结构特点来评价和优化。一方面，Hash表实际是种数据结构，哈希表有一些缺点是基于数组的，数组创建后难于扩展某些哈希表被基本填满时，性能下降得非常严重。这个问题是Hash表不可避免的，即冲突现象，故需要解决冲突问题。另一方面为了实现数字字符的匹配,当数字字符相应的十进制数过大时,为了降低匹配的时间复杂度,我们可尝试使用使用数论中的模运算优化。另一方面，尝试编写优化的查询语句能够很大程度上提高数据查询访问的速度。最后，尝试优化主观因素。如扩大服务器的内存；配置虚拟内存等。总之综合多方面因素采用模糊综合评价法进行评价。二、问题假设与符号说明2.1问题假设(1)假设测序过程中没有其他因素的干扰；(2)假设题目所给定的序列相对位置的碱基全部遵循GU-AC法则；(3)假设题目中所有的序列都是正常可判别的序列，没有出现序列的基因突变等情况；(4)假设基因组每个位置被测到的几率是等可能的；(5)所有片段上的碱基都已经被识别出来，不存在未知碱基。2.2符号说明reads：利用现有的测序技术，可按一定的测序策略获得长度约为50–100个碱基对的序列，称为读长；^：在findstr/r的[]中表示不匹配指定的字符集;+：主要是在copy命令里面会用到它,表示将很多个文件合并为一个文件,就要用到这个+字符了；()：命令包含或者是具有优先权的界定符吧,比如for命令要用到这个(),我们还可以在if,echo等命令中见到它的身影。三、数据分析对于给定100万DNA序列数据进行分析，具有以下特征：（1）数据量庞大，数据占用内存大，但排列整齐，易于分析。（2）由于数据衔接顺畅，在对于给定k值进行相关k-mer划分时，防止上段DNA序列与下段DNA序列衔接在一起出现错误。（3）100万DNA序列顺序不同，但排列规整，容易分析。四、模型的建立和求解4.1问题一的模型建立与求解4.1.1建立索引（1）把附件中DNA序列复制到文本文档123.txt中，并将其保存至G盘，通过FileReaderfr=newFileReader(g://123.txt)将文本文档文件中的序列存入库中，开始建立read条目的数据结构和k-mer条目的数据结构。预读数据，逐条读取read数据，把各个DNA序列读入存储至Arraylist:al1中，如图所示，为相关代码。相关数据录入程序源代码见附录。（2）依次读取每一个read，存入S字符串中，输入相应的K值，将读入的DN