DNA序列的k-mer index问题建模.doc

队伍信息表队伍基本情况介绍（数学基础，编程基础，队伍基本分工）三名队员均具备数学分析、高等代数、概率论与数理统计、数值分析、常微分方程、离散数学、数学建模、运筹学等课程的数学基础；会使用字处理软件“word”、电子表格“excel”、matlab软件、lingo软件、SAS软件等；具备c语言、Java编程基础。队长负责整理综合所有人就建模题目一起讨论的结果，在建模过程中及时收集整合队员的创新性想法，进行整体分析，统筹建模大局，列出建模步骤，给自己和两名队员分配任务，把握建模进度。 一名队员主要负责计算机的运用，应用字处理软件“word”，电子表格“excel”，matlab软件、lingo软件等进行模型的相关制图，并用Java编写程序且运行得出结果。 另一名队员具有较好的论文写作能力，按照严格的格式要求，综合三个人的思路和个人建模任务完成的成果，清楚地叙述摘要内容，有条理地的把建立模型、设计算法、求解模型等步骤写在论文中，从而完成本数学建模的论文。 DNA序列的k-mer index问题 摘要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，得出建立索引计算复杂度为。空间复杂度为=。针对问题4，得出使用索引查询的时间复杂度是：。空间复杂度为。 针对问题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分别用“00 01 10 11”来表示，也就是使用二进制来表示，二进制数在计算机中的空间占用内存大大小于字符在计算机中的占用空间。1.3.3问题三分析1. 本题要求对100万个序列建立的索引进行时空复杂度分析。前面已经将AGCT转化成了二进制，接下来就是将对应的数据块的每一项进行索引。即采用一种顺序访问的技术，对大数据块排好序后，再进行线性向下查找比对。分析时间复杂度即先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出的同数量级。2. 在建立DNA序列索引过程中，以文件形式给定的100万个DNA序列因为随时供索引调用，所以将数据以文件形式存放在本地磁盘中，即形成g:/123.txt。再者需要根据给定基因组索引表来获得待比对数据块的位置和大小，所以这个索引表必须常驻内存。索引表每项是一个二元组使用两个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的一个编号，在de Bruijn图中，一个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：利用现有的测序技术，可按一定的测序策略获得长度约为50100个碱基对的序列，称为读长；：在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盘，通过FileReader fr = new FileReader(g:/123.txt)将文本文档文件中的序列存入库中，开始建立read条目的数据结构和k-mer条目的数据结构。预读数据，逐条读取read数据，把各个DNA序列读入存储至Arraylist :al1中，如图所示，为相关代码。相关数据录入程序源代码见附录。（2）依次读取每一个read，存入S 字符串中，输入相应的K值，将读入的DNA片段根据K值，通过for循环建立相应的长度的k-mer序列，输入目标k-mer序列，与所得k-mer序列进行比对。比对成功后输出相符k-mer序列所在DNA序列以及相应序列中出现的位置。若比对失败，即输出对不起，没找到，如图1所示，为相关代码。如图2为处理过程图。图1 相关程序 图1 相关代码K=3原第二DNA序列片段目标k-mer输出“在第2行的：第1个” “在第2行的：第15个” 图2 处理过程图4.1.2模型求解由于数据非常庞大，演算拼接过程不能完整的展示，接下来将列举一段算法拼接的过程：（注：结果过长，将截取部分结果。）（1） 初始k-mer定为 GGA即 101000，该k-mer出现在多条read上，并出现在不同read的不同位置或者是同一read的不同位置，当k=3，k-mer取“GGA”时运行结果部分截图。 当给定不同的K值和给定其它不同k-mer时同样可以得出正确结论，由于数据庞大，可能结果比较多，下面给出部分运行结果截图。(2) 对于给定k-mer进行对比，找到相应位置并进行对第一个位置的输出的流程（注：仍然以上述图2中的例子为例，其中对应二进制转化（A - 00 C-01 G-10 T-11）得到下列图3 图4 图5 图3 二进制对应转换图read 10100000110111100100000111011010001110位置1位置15图4 对应二进制数比对图k-mer 101000 101000位置DNA序列目标k-mer1G11G002G11G003A00A004A005T116C017T118G109C0110A0011A0012C0113T1114C0115G11G0016G11G0017A00A0018T1119G10 位置1图5 完整对比加位置输出示意图4.2问题二的模型建立与求解 所建索引的查询速度和所用内存分析4.2.1提高查询速度由于100万DNA序列数据量巨大，为了提高索引查询速度，采用二分法查找。而使用二分法进行查找时，数据需是排好序的，在我们的模型程序中，我们使用for循环将数据按顺序排好，排好后再使用二分法进行数据查找分析。二分法的主要思想是：（设查找的数组区间为arraylow, high）（1）确定该期间的中间位置K（2）将查找的值T与arrayk比较。若相等，查找成功返回此位置；否则确定新的查找区域，继续二分查找。区域确定如下：a.arraykT 由数组的有序性可知arrayk,k+1,highT;故新的区间为arraylow,，K-1b.arraykT 类似上面查找区间为arrayk+1,，high。每一次查找与中间值比较，可以确定是否查找成功，不成功当前查找区间缩小一半。对题目附件中所给出的100 万个DNA序列， 每个序列的长度为 100。给定一个确定的k值，每个DNA序列可分成100-k+1个长度为k的短序列（可能会有重复的短序列）。每条DNA序列仅含有A、C、G、T四种碱基，现将碱基替换成2位二进制数，即令A=00，C=01，G=10，T=11。这四个碱基看成二进制的序列数，对指定长度的DNA短序列其二进制表示是唯一的。将二进制转化为十进制数，则对指定长度的DNA短序列所对应的的十进制数也是唯一的。例如取定序列TGCA（11100100），换算成十进制为：0*20+0*21+1*22+0*23+0*24+1*25+1*26+1*27=0+0+5+0+0+32+64+128=229。将每个长度为100的DNA序列中的100-k+1个长度为k的短序列转化成十进制数（唯一确定）。 由顺序算法优化成二分法，将k-mer的所有序列哈希值按照升序排列，对给定的k-mer哈希值m，从第一个DNA序列的中间位置开始比较，如果当前位置等于m，则查找到其中一个并记录下来位置信息，再继续查找；如果m小于当前位置值，则在数列的前半段位置查找；如果m大于当前位置值，则在数列的后半段位置查找；直到找出该条DNA序列全部所求位置信息。再进行第二条、第三条直至100万条DNA序列结束。由于100万条readsDNA序列数量过大，且将每条长度为100的DNA序列转化成二进制在本文难于表示，以下选取reads1的10个碱基序列为例，进行二分法匹配解释。 设reads 1：CTAGGAGTA长为10，给定k=3，分成10-k+1=7个长度为k=3的3-merDNA短序列：原位置序号12345673-merCTATAGAGGGGAGAGAGTGTA二进制011100110010001010101000100010001011101100十进制28501040341144 按照十进制数值升序排列，得新的序列：新序列号原位置序号36154723-merAGGAGTCTAGAGGGAGTATAG二进制001010001011011100100010101000101100110010十进制10112834404450 给数列中赋值： =10、= 11、=28、=34、=40、=44、=50； 给定一个3-mer：GGA，二进制为101000，采用Rabin-Karp算法转化成唯一十进制数字m=40。 在Java软件中运行验证该结果：事实上，对于百万级别的Java语句，无论索引怎样优化，都会用比较严重的延时。解决方法为，每次新查询的一页时，进行select count（*），之后就把结果集总数通过上页下页的链接传递。另外，要select top，如果是oracle，那么在浏览的第十页的时候，让数据库只返回到第十页*30条/页=300条。4.2.2降低索引所用内存 碱基序列用二进制表示，节省内存开销；我们通过使用二进制数“00”“01”“10”“11”来代替“A”“T”“C”“G”，从而可以达到降低索引所用内存的效果。当缓存的资料比较多的时候。其实我们可以使用操作系统中的缓存的概念来解决这个问题，也就是给被缓存的分配一个一定大小的缓存容器，按照一定的算法淘汰不需要继续缓存的对象，这样一方面会因为进行了对象缓存而提高了系统的运行效率，同时由于缓存容器不是无限制扩大，从而也减少了系统的内存占用。现在有很多开源的缓存实现项目，比如ehcache、oscache等，这些项目都实现了FIFO、MRU等常见的缓存算法。 4.3问题三的模型求解 建立索引的时空复杂度分析 算法的时空复杂度是指算法的计算复杂度和空间复杂度。算法的运行计算主要花费在数据块的排序、数据块二分查找和数据块之间的比对。接下来分析这两种方式的计算复杂度。 一个算法的计算复杂度（Time Complexity）是指该算法的运行计算与问题规模的对应关系。一个算法是由控制结构和原操作构成的，其执行的计算取决于二者的综合效果。为了便于比较同一问题的不同算法，通常把算法中基本操作重复执行的次数（频度）作为算法的计算复杂度。算法中的基本操作一般是指算法中最深层循环内的语句，因此，算法中基本操作语句的频度是问题规模k的某个函数，记作。其中“”表示随问题规模的增大，算法执行计算的增长率和的增长率相同，或者说，用“”符号表示数量级的概念。复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：，其中，n为问题的规模，为语句关于n所占存储空间的函数。通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：，其中，n为问题的规模，为语句关于n所占存储空间的函数。 4.3.1建立索引所用的计算复杂度分析通过前面的分析，对100万个序列，将从文件中取出的所有字符，分成若干短串，存储到字符数组中 ，每个短串含有个字符。即将对应的数据块的每一项进行索引。建立索引计算复杂度：.4.3.2建立索引所用的空间复杂度分析 在建立DNA序列索引过程中，以文件形式给定的100万个DNA序列因为随时供索引调用，所以将数据以文件形式存放在本地磁盘中，即形成g:/123.txt。再者需要根据给定基因组索引表来获得待比对数据块的位置和大小，所以这个索引表必须常驻内存。索引表每项是一个二元组使用两个4 字节整型存储，所以两个项的索引表总共占用256M 固定大小的内存空间。由于经常访问给定的整个基因组序列，故需要把参考基因组序列存入内存。大小为n 的参考基因组经过编码后大约在n/4 左右。待K-mer赋k值处理后的数据块一般不会太大，占用空间很小，对于100万条基因序列，处理后的数据块每项用三个整型存储，大约需要24M 内存空间。所以本算法的空间复杂度是：=。4.4问题四的模型求解使用索引查询的计算复杂度与空间复杂度分析：4.4.1使用索引查询的计算复杂度分析 由前面分析知，该程序是将从文件中取出的所有字符，分成若干短串，存储到字符数组str中，每个短串含有k个字符。所以索引的计算复杂度即是预处理的时间：。而由这个程序知，该for 循环是在字符数组str中查找与短串ss相同的短串，并将所在位置存放到集合al中。对这个排好序的数据块线性向下查找的计算复杂度是:。假设大的数据块中的小数据块的平均大小是n。两小数据块之间一次比对需要次比较，最坏情况个数据块均参与查找对比，所以总共比较次。 故若用顺序查找方法查找时的计算复杂度是。使用这种方式字符串和大数据块之间比对的时间复杂度是执行总次数=次.根据渐进时间复杂度中的“大阶”可得.所以此时使用索引所用的时间复杂度是:。另外查找时的计算复杂度是：当时，； 当时，； 而，使用二分法进行查找时的时间复杂度是。设数据文件里有条read，每条read长度为，k-mer长度为。首先，每条read都需要通过过滤器，过滤时要遍历read上每一个碱基，统计质量值。故过滤的时间与read的长度成正比，为。设有条read通过了过滤器。对这些read，每一条都要生成 个k-mer，生成每个k-mer时间与成正比，为。这时我们仅仅得到了k-mer的碱基，我们还要计算k-mer的哈希值，该计算时间依然与成正比，为。由于哈希表是无冲突的，故接下来可在常数时间内找到该k-mer所对应的k-mer结构以及readID_pos数组，并更新相应字段，故该时间为 。从而，建立哈希表的总时间为： + 一般地，与成正比，即，是大于1的常数。在我们的实验中，与近似相等，代入上述公式，经过化简可得建立哈希表的时间复杂度为。而对于我们索引程序中的Rabin-Karp算法：理论上，Rabin-Karp算法的复杂度是，其中n和k分别是文本和模式串的长度。最坏情况下，DNA序列的每一个序列中所有长度为k的子串K-mer(一共n-k+1个)都和模式串匹配，所以算法复杂度为(n-k+1)k)。然而实际情况下，需要进一步比对的子串个数总是有限的（假设为c个），那么算法的期望匹配时间就变成。故在实际使用过程中，Rabin-Karp的复杂度通常被认为是。由前面知，给定的DNA序列数为100万，序列编号为1-1000000，每个基因序列长度为100。故此时n=100,由前面程序运行知k取值为5、8、15，显然，kn,又根据渐进时间复杂度中的“大阶”可得：故该模型中使用索引查询的时间复杂度是：。 下图表示的是Rabin-Karp算法复杂度中，当n和m分别是文本和模式串的长度时，Rabin-Karp的复杂度通常被认为是的原理。4.4.2使用索引查询的空间复杂度分析 上述的k-mer结构大小是16字节，其中kmer_seq是无符号整型，占4字节，str是指针，在64位操作系统上占8字节，num是无符号短整型，占2字节，cur也是无符号短整型，占2字节。str1j.equals(ss)数组中每一行是4字节，其中 br.readLine()占25位，pos占5位，del_flag占1位，保留位占1位。故建立哈希表所需的空间总共为：.考虑到N与n近似相等，并将代入公式化简可得建立哈希表的空间复杂度为。 4.5 问题五的模型求解4.5.1所设计的索引方法所能支持的最大k值前面我们建立的索引用到了二分法、Rabin-Karp算法和Hash算法而所能支持的k值与程序运行（索引、查找和匹配）时所使用的内存有关。而由前面4.3和4.4的时空复杂度分析，我们尝试选取不同K值来运行程序，得到如下截图：由上面截图知k=68时程序报错，出现了乱码，而k=67时程序正常运行，k=69时，又出现了乱码。所以推测索引方法所能支持的最大k值是67。4.5.2相应数据查询效率 我们在索引程序中使用了hash算法（hash表在JDK中的一个实现就是HashMap）来缓存一些数据，从而提高系统的运行速度。正如我们要索引100万个DNA序列信息，就使用了HashMap缓存信息，这在提高系统速度的同时也加大了系统的内存占用，特别是当缓存的资料比较多的时候。这样就大大减弱了我们对每个DNA序列进行索引和查找匹配的效率。 另一方面，由Java的内存管理特点：Java一个最大的优点就是取消了指针，由垃圾收集器来自动管理内存的回收。程序员不需要通过调用函数来释放内存。Java使用了有向图的方式进行内存管理，尽管可以消除引用循环的问题，但是效率较低。五、模型的评价与改进 5.1模型的优点我们在建立和使用索引时用到的方法：二分法、哈希算法和Rabin-Karp算法。（1）对于二分法：它适用于已排好序的查找，二分法对于已排序的数组效率较高。未排序的话需要先排序再调用此方法。而对于未排序的数组因为需要先排序，效率可能比其他的方法稍低（加上排序的时间复杂度）；（2）对于哈希表：哈希表是种数据结构，它可以提供快速的插入操作和查找操作。不论哈希表中有多少数据，插入和删除（有时包括侧除）只需要接近常量的时间，即的时间级。总之，哈希表不仅速度快，编程实现也相对容易；（3）而对于Rabin-Karp算法：Rabin-Karp算法非常适用于多模式匹配（multiple pattern match）。它能做到对较长的模式串能得到较短的哈希值，而且，速度上应该有显著提升。（4）碱基序列用二进制表示，节省内存开销；总之本模型针对新型DNA序列的K-mer问题逐一进行了解决，把大量数据的基因序列问题成功的转化为JAVA中的Rabin-Karp算法和哈希表索引的问题，配合二分法、启发式搜索法实现了在较短的时间内对海量DNA序列进行索引、查找和对比等处理。本模型的算法高效，容易推广到实际的大数据基因序列问题中，具有一定的实际应用价值。5.2模型的缺点（1）对于二分法：该算法运行速度慢；且只适用于有序表，且限于顺序存储结构，对线性链表无法有效的进行查找；（2）对于基于Rabin-Karp算法的Hash表：是基于数组的，数组创建后难于扩展某些哈希表被基本填满时，性能下降得非常严重。并且，有许多字符串匹配算法的复杂度小于O(n+m)；（3）有时候它和普通匹配法一样慢，并且它需要额外空间；（4）由于比赛时间限制，本模型没有对分段中可能出现的误差进行较好的规避。如上述的基因序列中出现重复片段干绕问题；对于海量数据比对过程中也应有的内存优化问题；（5）在实际中，DNA序列是动态的，存在着大量的不确定性；（6）该模型处理重复片段的能力较弱。由于内存问题，暂时还无法处理k值过大的K-mer问题。5.3模型的改进 一方面，我们上面程序中采用的哈希算法建立的Hash表实际是种数据结构，由模型的缺点我们也知，哈希表有一些缺点是基于数组的，数组创建后难于扩展某些哈希表被基本填满时，性能下降得非常严重。这个问题是Hash表不可避免的，即冲突现象：对不同的关键字可能得到同一哈希地址。此时我们只需要解决冲突问题。 尝试采用“开放定址法”来解决冲突问题。具体做法是：当冲突发生时，使用某种探测技术在散列表中形成一个探测序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址(即该地址单元为空)为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探查到开放的 地址则表明表中无待查的关键字，即查找失败。另一方面为了实现数字字符的匹配,当数字字符相应的十进制数过大时,为了降低匹配的时间复杂度,我们可尝试使用使用数论中的模运算优化。 另一方面，由对问题五的分析知， 查询语句不够优化 在数据查询访问过程中，使用最频繁的是使用自定义的查询语句进行数据输出的。所以尝试编写优化的查询语句能够很大程度上提高数据查询访问的速度。最后，尝试优化主观因素。如扩大服务器的内存；配置虚拟内存：虚拟内存大小应基于计算机上并发运行的服务进行配置，一般设置为物理内存的1.5倍；如果安装了全文检索功能，并打算运行Microsoft搜索服务以便执行全文索引和查询，可考虑将虚拟内存大小设置为至少计算机中物理内存的3倍。参考文献：【1】胡松年,薛庆中，基因组数据分析手册，浙江大学出版社。2003年。【2】胡运发，数据索引与数据组织模型及其应用，复旦大学出版社。2012年。【3】蔡厚新，数据结构导论，中国人民大学出版社。2010年。【4】王永，李昌兵，何波。混沌加密算法与Hash函数构造研究，电子工业出版社。2011年。【5】司守奎，数学建模算法与应用，北京，国防工业出版社，2011年。【6】Patrick Niemeyer G Jonatban Knudsen 李晨熙, Java语言入门，中国电力出版社，2001年。【7】吕国英,任瑞整,钱宇华.算法设计与分析M，北京:清华大学出版社,2006年。【8】刘军，浅谈算法设计与算法时间复杂度J，电脑知识术,2008年。【9】李士勇.工程模糊数学及应用M.哈尔滨：哈尔滨工业大学出版社，2004年【10】宁晓秋.模糊数学原理与方法M.徐州：中国矿业大学出版社，2004附录：import java.io.Buf