基因组组装算法研究(已审核).doc

_基因组组装算法研究摘要基因组测序是生物信息学的核心，有着极其重要的应用价值。近些年来，新的测序技术大量涌现，与传统的Sanger方法相比，这些方法产生的read(由测序仪直接测得的 DNA 片段)长度更短，数量更多，覆盖率更大。然而，传统的拼接算法并不适用于利用短 read 进行拼接，新的拼接算法在拼接效果上仍有待提高。本文首先介绍了传统的基因组拼接所用的贪婪算法和overlap-layout-consensus 算法，这两种算法仅适用用于第一代测序技术所得的reads,并不适用于第二代基因测序。对于第二代测序技术所得的reads,可以建立de bruijn 图算法的数学模型，然后编写程序，组装基因片段。利用第二代测序技术可以在一次实验中获得高通量短 read，然而第二代测序技术并不完美，由于在测序前要通过 PCR 手段对待测片段进行扩增，因此增加了测序的错误率。因此，本文利用HiTEC纠错算法对de bruijn 图算法进行优化。另外，本文还利用了基于概率模型的基因组从头测序算法克服了原有拼接算法过度依赖碱基片段之间重叠信息的缺陷，创造性地将 DNA 拼接过程抽象为二阶离散马尔可夫过程，与此同时，每一条碱基片段被抽象为系统中的一个状态。关键词：贪婪算法，OLC算法，de bruijn 图算法，HiTEC纠错算法一、问题重述遗传信息是生物遗传与进化的主要研究依据。能否快速和准确地获取生物体的遗传信息对于生命科学研是否有重大发现具有重要意义。对每个生物体来说，基因组包含了整个生物体的遗传信息，这些信息通常由组成基因组的DNA或RNA分子中碱基对的排列顺序所决定。获得目标生物基因组的序列信息，进而比较全面地揭示基因组的复杂性和多样性，成为生命科学领域的重要研究内容。确定基因组碱基对序列的过程称为测序。测序技术始于20世纪70年代，伴随着人类基因组计划的实施而突飞猛进。从第一代到现在普遍应用的第二代，以及近年来正在兴起的第三代，测序技术正向着高通量、低成本的方向发展。现有的测序技术中，可按一定的测序策略获得长度约为50100个碱基对的序列，称为读长（reads）。基因组复制份数约为50100。基因组组装软件可根据得到的所有读长组装成基因组，这些软件的核心是某个组装算法。常用的组装算法主要基于OLC（Overlap/Layout/Consensus）方法、贪婪图方法、de Bruijn图方法等尽管如此，目前能直接读取的碱基对序列长度远小于基因组序列长度，因此需要利用一定的方法将测序得到的短片段序列组装成更长的序列。一个好的算法应具备组装效果好、时间短、内存小等特点。新一代测序技术在高通量、低成本的同时也带来了错误率略有增加、读长较短等缺点，现有算法的性能还有较大的改善空间。本题要求我们尝试建立模型，由程序计算得到基因组的长须组装。算法与程序要求能有效地解决在测序过程中出现的碱基对识别错误，或则基因中出现重复片段的情况。将所建立的模型检查运行后，本题要求我们进一步对其进行探究。针对一个全长约为120,000个碱基对的细菌人工染色体（BAC），采用Hiseq2000测序仪进行测序，结合附录中的测序策略、数据格式以及读长数据，在测序长度约为70的情况下，对上述所建立的模型与算法程序进行组装验算。二、问题分析本题是基于新一代测序技术的基因组装算法问题，要求设计算法针对性的解决新一代测序技术带来的一些弊端。2.1 read长度较短，数量较多de bruijn图新一代测序技术所得的read长度较短，数量较多，不易发现read之间的重叠关系。可以将read转化成定长的k-mer，然后寻找k-mer之间的重叠关系。然后建立de bruijn图，把短序列拼接问题转化为de bruijn图中的欧拉路径问题。2.2 个别碱基对识别错误多重对比纠错通过将多个read放在一起比对来发现错误，如图1所示 。图中通过途中4条read比对，可发现read3中的一个碱基错误（read3的第五个碱基）图 Error! Main Document Only. 4条read对比图read1 AACA TGCA TGCT TGAC reda2 TGCA TGCT TGAC ACAG read3 TGCT CGAC ACAG CGTT read4 TGAC ACAG CGTT 2.3基因组中存在大量重复片段重复片段可能导致拼接错误，或者导致不连续的较短contig出现。重叠片段类型主要有以下几种，如图2所示重复片段问题可以用如下问题解决：通过对比，可先将重复片段隔离开来，较高的覆盖度有利于重复片段的隔离，但是，较多的测序错误将不利于该过程的进行。如果重复片段比read 长，可利用pared end read 来解决；如果重复片段比read 短，那么该read又被称为 spanner，一个spanner 就是一个重复片段两端再加几个碱基组成。利用spanner 解决重复片段问题需要如下两个信息：一是重复片段两端配对的read ，这两个read 必须不相同；二是重复片段中的一个配对read ，只要知道一个即可，另一个配对read 可以不在重复片段中。通过分析已知的基因组，可获得有关重复片段的更多信息，如，重复片段的长度，重复片段的模式等。图 2 重叠片段类型三、 模型假设1假设测序过程中没有其他因素的干扰；2假设题目所给定的序列相对位置的碱基全部遵循GU-AC法则；3假设题目中所有的序列都是正常可判别的序列，没有出现序列的基因突变等情况；4假设一个完整基因组，打断成500bp的片段是随机的；5假设基因组每个位置被测到的几率是等可能的；6所有片段上的碱基都已经被识别出来，不存在未知碱基。四、符号说明原基因进行第j-1次复制并对其进行任意切割后的第i个基因基因的长度，即有个碱基对K碱基对数量，即有K个碱基对第一个碱基对到第K个碱基对组成的基因第-K+1个碱基对到第个碱基对组成的基因第一个碱基对到第-K个碱基对组成的基因第K+1个碱基对到第个碱基对组成的基因Conting（C）由经过贪心算法和最短路径算法后拼接产生的基因从顶点到的一条路的权.也就是的值的父亲点，用以确认最短路的路线.S 具有永久标号的顶点集.read利用现有的测序技术，可按一定的测序策略获得长度约为50100个碱基对的序列，称为读长；contig（C）：由read经过一定算法拼接产生3kb10Mb以内的一些基因组片段;supercontig（S）：使用contig作为参考序列延伸，并进行合并得到更长的contig,即supercontig;quality（Q）:根据本题数据，每一个read都含有一个质量值，该值能反映该read的正确率。质量值越高，read的正确率越高。k-mer长度为k的一段DNA片段五、 模型的建立及求解5.1拼接算法简介目前，DNA 拼接组装算法大体上可以分为两类：一类是有参考基因组的重测序，一类是无参考基因组的从头测序。重测序是针对有参考基因组的物种提出的。通过使用第一代测序方法，消耗大量人力物力，经过较长时间，测定了一些物种的基因组，并且已将测序完成的基因组存入基因库中，将来可以作为参考基因组使用。对于这些物种的其它个体，它们的基因组与其相应的参考基因组相差不大，故在拼接时参考基因组会起到重大作用。但对于其他新的个体，没有参考基因组可供使用，于是人们提出了从头测序，即仅仅使用测序仪读出的一条条 read 来拼接组装成整个基因组。 目前，从头测序主要有三类 DNA 拼接组装算法：（1）贪婪算法；（2）基于 overlap-layout-consensus（重叠-排列-生成一致序列）思想的算法；（3）基于 de bruijn 图的算法。其中贪婪算法和基于 overlap-layout-consensus 思想的算法是针对第一代测序数据提出的。第一代测序所得的 read较长，数量相对较少，易于发现 read 之间的重叠关系。基于 overlap-layout-consensus 思想的算法建立重叠图，将 DNA 拼接问题转化为图论问题。新一代测序技术所得的 read 长度较短，数量较多，不易发现 read 之间的重叠关系，因此前两种方法不再适用，于是人们提出了基于de bruijn 图的算法，将 read转化成定长的 k-mer(长度较短的碱基片段)，然后寻找k-mer 之间的重叠关系，建立de bruijn 图，最后将 DNA 拼接问题转为图论问题。5.2贪婪算法 假定在 read 集合中存在两条 read，分别记作 ri和 rj，其中 0 i，j n 且 i j。若这两条 read 可以被表示为 ri= xy，rj= yz，则 y 即为这两条 read 之间的最大重叠区域，当 y 的值等于 0 时，表示这两条 read 之间无重叠区域。若两条 read 之间的重叠区域 y 大于一定的阈值，则将这两条 read 合并为一条read。 贪婪算法的具体步骤是：首先选择满足一定要求的 read 作为 contig 的种子，然后寻找和该 read 的两端含有重叠区域的 read，并对选作种子的 read 进行扩展，直到当前拼接的序列的两端无法继续扩展。最后选择下一条满足要求的 read 重复执行上述操作，直到拼接结束。利用贪婪算法进行序列拼接时，若存在两个及以上的 read 与当前拼接的序列的某一段含有重叠区域时，算法无法确定应该选择哪一条 read 进行扩展，因此当遇到这种情况时，算法终止，所以利用贪婪算法所拼接的 contig 的长度往往较短。实际上为避免这种情况的发生，贪婪算法在选择种子的阶段，首先依据覆盖度文件和质量文件 contig 中的种子进行打分，并且优先选择分数较高的read作为种子。利用贪婪算法的软件主要有：SHARCGS，SSAKE和 VCAKE。SHARCGS 只能拼接测序错误率低于 0.05%的 read，因此利用 SHARCGS 对第二代测序技术所产生的数据进行拼接时效果并不理想。SSAKE 只能对无碱基测序错误的 read 进行拼接，尽管该方法能够拼接的 read 的长度为 25bp，但产生大量的拼接错误。VCAKE 在 SSAKE 基础上进行了改进，能够对含有更多测序错误的 read 进行拼接。5.3 overlap-layout-consensus 算法利用 overlap-layout-consensus 算法进行 DNA 拼接时，第一步是利用所有待拼接的 read 构造一个有向图 G，图 G 中的每一个结点均是与之对应的一条特定的 read。如果图 G 中的某两个结点由一条公共边相连，则说明这两个结点所代表的 read 之间的重叠部分大于预先设定的阈值。然后确定经过每个结点唯一一次的一条路径，实际上这条路径刚好访问每个结点仅一次。通过上述操作，DNA 序列拼接问题便转化为人们所熟悉的 Hamilton 路径问题。overlap-layout-consensus 算法大体可以分为如下三步：（1）首先确定适当的阈值，当两条read间重叠区域的长度大于该阈值时，算法便认为这两个read之间存在重叠区域。 （2）同贪婪算法类似，首先将某一条read看作为一条contig，然后通过寻找与该read之间存在重叠区域的read来扩展这条被视作contig的read，重复执行这样的操作，最终便得到一定长度的contig。 （3）在 contig图中对read进行排列，然后确定一种投票机制，即根据碱基的质量值对read进行加权计算，通过投票机制来确定最终的 DNA 序列。 基于“overlap-layout-consensus”思想的算法有：Edena和 Arachne等。5.4 de bruijn 图算法二十世纪八十年代末，Pevzner等人提出基于de bruijn图的算法，并首次将该算法用于 DNA 序列拼接。基于 de bruijn 图的算法的核心思想是将序列拼接问题转换为人们所熟悉的欧拉路径问题。Pevzner 等人认为传统的overlap-layout-consensus 算法导致了将 DNA 序列拼接问题转换为 Hamilton 路径问题，他们受到杂交测序方法 SBH(Sequencing by Hybridization)的启发，创造性地提出了在 de Bruijn 图中寻找欧拉路径的构想，尽管杂交测序方法SBH 从未在测序工程中实际应用过，但它直接引发了基因芯片工业的诞生。构造 de Bruijn 图的方法如下所述：图 2de Bruijn 图（1） 在 read 集合 R = r1，r2，rn中，首先将每一条 read 分割成若干 k-mer(长度更短的 DNA 片段)。假定集合 R 中任意一条 read 的长度均为 l，k-mer 长度值设为 k，那么集合 R 中的任意一条 read均可被分为 l k + 1 条 k-mer，并且这些 k-mer 作为 de Bruijn 图的顶点。（2） 对于给定的两条 k-mer x 和 y，如果在某 read ri中存在一条长度为 k +1 的子串，且该子串的前k个碱基与k-mer x(或y)精确匹配，同时该子串的后 k 个碱基与 k-mer y(或x)精确匹配，那么该算法认为两条k-mer x和y之间存在一条公共边。将采用上述方法构造的 de Bruijn 图记作 G。对于 read 集合 R = r1，r2，rn中的任意一条read ri，若在 de Bruijn 图 G 中存在一条路径 P，且该路径 P 访问 ri中的每一条 k-mer仅一次，则欧拉路径问题便可理解为：给定某一de Bruijn 图 G 以及 G 中的路径集合 P，在de Bruijn 图 G 中确定某一条欧拉路径 Q，使得路径集合 P 中的每一个元素都是欧拉路径 Q 的子路径。利用欧拉路径算法进行DNA 序列拼接的主要步骤如下所述：首先利用纠错软件修正 read 中测序错误的碱基；然后按照上述方法构建de Bruijn 图；构建de Bruijn 图之后，应将 read 集合中的所有 read 排列在de Bruijn 图中，在 de Bruijn 图中，每一条 read 均被视作一条路径；最后在de Bruijn 图中寻找一条欧拉路径，使得该路径包含de Bruijn图中所有read 所对应的路径。与 overlap-layout-consensus 算法相比，基于 de bruijn 图的算法有更低的时间复杂度，这是因为欧拉路径问题实际上是一个线性时间的问题。利用欧拉路径思想的拼接算法有 EULER-SR、ALLPATHS、Velvet、和 EULER等。5.5 de bruijn 图算法模型的建立令=其中1in,1jm.设，i。,j且1，n,1,m。设A为阶空矩阵。若=，则A(n+,n+)=1若，则A(n+,n+)=+则可得关于迪克斯特拉（Dijkstra）算法的邻接矩阵A。接下来利用最短路径算法和贪心算法求出基因重组的最佳方案。定义为节点图，中的任意一点皆为一个结点，则共有nm个点，其中第n+1个点表示，即以n个点为一周期，以此类推。并从其中随意定义一点为初始点. 对每个顶点，定义两个标记（,),其中：= 算法的过程就是在每一步改进这两个标记，使最终为从顶点到的最短路的权.输入为带权邻接矩阵W.（1） 赋初值：令S=，=0.=VS,令=W（，）,=,.（2） 更新，:=VS,若+,则令=+,=（3） 设是使取得最小值的中的顶点，则令S=S，.（4） 若，转（2）；否则，停止.5.6模型的求解（1）将k值定为4。把上述read1文件中的序列存入库中，开始建立read条目的数据结构和k-mer条目的数据结构。预读数据，逐条读取read数据，每条readID进行升序保存；生成该read上所有k-mer（共85个k-mer），统计这些k-mer出现的次数，填写k-mer结构中的num字段。如图所示，为相关代码片段。相关数据录入程序源代码见附录。（2）遍历de bruijn图，根据上一步统计的k-mer数量，申请readID_pos数组所需要的内存空间。依次读取每一个read，填写readID_pos数组中的第cur行，填好之后把cur值加1。（3）将碱基替换成2位二进制数。A=00，C=01，G=10，T=11。由于数据非常庞大，演算拼接过程不能完整的展示，接下来将列举一段算法拼接的过程：（1）初始k-mer定为 AAAC即 00000001，该k-mer出现在4条read上，且k-mer出现在每条read上的pos为1.这四条read开始参与拼接。如图为k-mer比对拼接相关代码（2）此时num 为4，addr为1，cur为-1；read1 00000001 01111101 01000010 11101111 00010000 10011101 00001000read2 00000001 00001110 00001010 10010000 01100011 10001100 11010100 read3 00000001 11000100 10101011 10111111 11010110 11010000 10010010read4 00000001 11111000 11101010 00000011 01000101 11111111 11000010初始kmer 00000001后继kmercontig 00000001（3）当前候选后继k-mer情况如下：初始kmer00 00 00 01候选后继kmer100 00 01 01候选后继kmer200 00 01 00候选后继kmer300 00 01 11候选后继kmer400 00 01 11（4）选定后继k-mer为 AACT,即00000111；进行下一段拼接，此时num为5，前驱结点cur 为1，addr为2；此时contig增加了一个碱基；read100000001011111010100001011101111read200000001000011100000101010010000read300000001110001001010101110111111read400000001111110001110101000000011read500000100111111001111110000000010初始kmer00000001后继kmer00000111contig0000000111（5）重复（4）步骤，直到无法找到符合条件的后继k-mer则该条contig拼接结束；若该条contig的长度大于100bp则保存下来，否则删除；程序继续运行以上案列，得到一个长度为360bp的contig如下： 110111110010010100001000100011000111111000111010010110010011100011011010111011000000010000111000010111110100001011110100010000111011000011001101111000000111111111010000001010010100100010010011011001011001111011001110100010010110001001110010010110010100111110110101111101010001010001011100001110100000110111101011011011011011011011010101111000101111010111110001001000111101101001101000110010000000110010000101001010001011100010011000111011101100010000010011100110101111100110101110000010100100000101111011001100110110001010101010110010001101001111010111001011111011001101001111111111101111110100111011110111111111001100001111001110111111001101001001001101110010011100101111010011101101110011110111001111001101001101111011 （6）到此一条contig拼接结束，开始重复（1）步骤；最终得到若干条长度大于100bp 的contig。 101100010011100100101100101001111101101011111010100010100010111000011101000001101111010110110110110110110110101011110001011110101111100010010001111011010011010001100100000001100100001010010100010111000100110001110111011000100000100111001100 5.7基于概率模型的基因组从头测序算法在算法设计之初，我们的构想是如果已知第一条碱基片段和第二条碱基片段，那么就可以通过这两条碱基片段确定基因组中的下一条碱基片段。实际上，在基因组中通过第一条碱基片段和第二条碱基片段可以确定的第三条碱基片段往往不止一个，通常情况下出现次数最多的第三条碱基片段是正确的。这是因为 read 数据中存在大量的碱基测序错误，因此那些出现次数较低的碱基片段往往含有测序错误的碱基。简而言之，算法的核心思想就是通过第一条碱基片段和第二条碱基片段确定第三条碱基片段，然后再通过这第二条碱基片段和第三条碱基片段确定第四条碱基片段，重复这样的操作，理想情况下，最终便可以得到满足一定长度要求的 contig。实际上，这与二阶马尔可夫模型的思想不谋而合，即都是系统未来某一时刻的状态仅仅依赖于当前的两个状态。因此,本文所研究的基于概率模型的基因组从头测序算法将二阶马尔可夫模型运用到 DNA 拼接过程中。 基于概率模型的基因组从头测序算法首先利用 read 中的信息构建概率模型，然后在序列末端截取两条相同长度的碱基片段，利用概率模型便可确定这两条碱基片段之后出现概率最大的某一碱基片段，并将其拼接在序列末端，这样序列便在原有长度的基础上得到了扩展。算法继续在序列末端截取两条相同长度的碱基片段，用同样的方法便可得到新的后继碱基片段，序列就在这样的操作过程中得到不断地扩展，最终获得一定长度的 contig。具体的拼接过程如下所述。若以 now 和 next 作为种子，假定 now =k1k2k10，next =k11k12k20（实际中 now 和 next 已被转换为相应的十进制数）。首先在主表中定位索引值为now的元素，即prim -aryTablenow。然后遍历 primaryTablenow中的指针所指向的副表，若副表中只存在唯一的项含有next，则该项中的lastMer值即为所要寻找的后缀last，假定last= k21k22k23k24，此时应将该项中的freContig值加一，避免在下次拼接中选择该组now和 next 作为种子。这样便通过第一前缀now和第二前缀next并结合概率模型确定了概率值为 1 的后缀 last，同时序列在原有的基础扩展了4个碱基。然后取当前序列的最后20个碱基作为新的第一前缀和第二前缀，即now =k5k6k14，next =k15k16k24，用同样的方法确定新的第一前缀 now 和第二前缀 next 的后缀 last。重复执行上述操作，序列便在原有的基础上不断地扩展，最后得到一个完整的contig。然而，在实际的拼接过程中，通过第一前缀now和第二前缀next在哈希表中能够确定的后缀 last 往往不止一个，这是因为尽管使用 HiTEC 方法进行了测序数据纠错处理，但在 read 数据中仍然存在大量的碱基测序错误，因此对于同一个后缀 last，它们在 read 数据中可能有多种存在形式，区别仅在于12 个碱基不同。实际上，对于一个后缀 last，尽管存在一些含有测序错误碱基的后缀的干扰，但正确的后缀 last 的出现概率要明显大于那些含有测序错误碱基的后缀，因此对于这种情况，应该选择出现概率明显较大的后缀作为正确的后缀 last。当出现无后缀情况或出现概率较大的后缀不止一个时，算法结束本次拼接并输出一条contig，然后选取新的种子now和next进行下一条 contig的拼接。综上所述，基于概率模型的基因组从头测序算法描述如下。基于概率模型的基因组从头测序算法：算法输入：经 HiTEC 方法纠错处理的 read 数据 算法输出：n 条 conitg（0 n 1)项，即 t1，t2，tn。对于其中任意一项ti的nextMer值均等于next，则继续步骤6，否则转至步骤7； 06. 若 n项中存在唯一项ti满足 freRead / n 项 freRead 值之和 0.6，而对于其它 n 1 项，该值均小于 0.2，则 last 等于该项中的 lastMer 值，获取新的 now 和 next，转至步骤 3，否则转至步骤 7； 07. 结束本次拼接并输出一条 contig，获取新的 now 和 next，转至步骤 3； 08. 输出 n 条 contig，算法终止；7、模型的优化利用第二代测序技术可以在一次实验中获得高通量短 read。然而第二代测序技术并不完美，由于在测序前要通过 PCR 手段对待测片段进行扩增，因此增加了测序的错误率。例如，Illumina 公司的 Solexa 技术在一次测序中可以获得100万条read，每一条read长度在 35bp75bp，与此同时，碱基的测序错误率在 1%2%。在DNA拼接过程中，测序错误能够造成大量问题，大大降低了拼接结果的准确率。因此，在进行DNA序列拼接之前，有必要对 read 数据进行预处理，修正 read 中测序错误的碱基，从而提高DNA序列拼接的效果。目前对read数据进行预处理的方法大体上可以分为两类：一类是修正测序错误的碱基，我们称之为“纠错”，另一类是删除含有大量测序错误的read。然而，第二类方法存在降低read数据覆盖率的风险，这在一定程序上会降低算法的精确性，因此下面给出HiTEC纠错算法，优化模型。给定某一长度为 L 的基因组 G，G 可以理解为由字符 A、T、G、C 组成的字符串，且每一个字符出现的概率均为0.25。假定有n条来自基因组G的read，记作r1，r2，rn，其中每一条read的长度均为l，且基因组G中的碱基测序错误率为p。注意，算法将包含非A、T、G、C碱基的read删除。如果某一条read的某一位置上的碱基与基因组 G 中相应位置上的碱基不同，或与其他 read 中相应位置上的碱基不同，则该碱基为错误的碱基。 由 n 条 read 及其反向互补串构造字符串 R，即 R = r1$r1$r2$r2$ rn$rn$，其中$表示非 A、T、G、C 的字符,令SA和LCP分别表示R的后缀数组和最长公共前缀数组。假定从基因组 G 中位置 j 处抽取一条 read，记作 ri，该read中的位置 k处存在一个测序错误的碱基，在位置k之前的w个位置上的碱基均是正确的，即rik wk 1是正确的。令 ri = xuay，其中x，u，y均是由字符A、T、G、C 组成的字符串，x 的长度记作|x|，且|x|= k - w -1，u 的长度记作|u|，且|u| =w，a 为字符 A、T、G、C 中的某一字符，且a与基因组 G 中位置j + k -1 处的字符 b 不同。然而，很多其他的 read 也是从基因组G中这一区域抽取的，因此这些 read 均含有正确的子串 ub。在实际的纠错过程中，若发现字符串u后边的字符是b的次数明显多于a，则该位置上的字符 a 很有可能是错误的，实际上应该是b，若证据充分，则应将a替换为b。实际上字符串u足以说明字符a 是错误的，而正确的应该是字符b。对于字符a，supp(u，a)表示 R 中字符串 ua 出现的次数。8.模型的评价8.1 模型的优点(1) 本模型的算法容易推广到实际的基因组组装中，具有一定的实际应用价值；(2) 本模型针对新一代测序技术出现的问题逐一进行了解决。新一代分割的读长较短，不易发现reads之间的重叠关系，本文放弃了传统的重叠图算法。把基因重组问题成功的转化为Dijkstra的问题，配合全基因组鸟枪法测序实现了在较短的时间内对大量reads数据进行比对处理。8.2 模型的不足(1)忽略了碱基存在的内环境因素及其生化结构的影响；(2)在实际中，基因组组装是一个复杂的数学问题，存在着大量的不确定性；(3)一些新的想法缺乏足够的理论根据，所以有些问题的解决带有一定的主观性；(4)该模型处理重复片段的能力较弱。当有reads拼接失败时，意味着小于reads长度的重复片段被检验出来，但无法处理大于reads长度的重复片段。参考文献：1高随祥,杨德庄. 扩展de Burijn图的生成树和广播J.系统科学与数学,2003.2王东阳，任世军，王亚东.DNA序列拼接中de Burijn图结构的研究J.智能计算机与应用,2011.3韩东涛. 基于概率模型的基因组从头测序算法研究.4邱风.基于de Burijn图的短序列拼接算法的优化及并行化.附录package cn.data;import java.io.*;import java.sql.*;public class DataInput /*A=00*C=01*G=10*T=11*/public static void main(String args) throws SQLException,ClassNotFoundException/ TODO Auto-generated method stubFile file=new File(E:基因数据,data1.txt); /*File file2=new File(D:基因数组,oo.txt);*/String a = new String60000;String b = new String60000;String c = new String60000;DataInput myData = new DataInput();tryFileReader inOne=new FileReader (file);BufferedReader inTwo=new BufferedReader(inOne); /*FileWriter outOne=new FileWriter(file2);*/*BufferedWriter outTwo=new BufferedWriter(outOne);*/String s=null;int i;int j;int k;int p;for(j=0,k=0,p=0,i=1;(s=inTwo.readLine(