基因组组装算法研究应用已审核.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年代，随着着人类基因组筹划实行而突飞猛进。从第一代到当前普遍应用第二代，以及近年来正在兴起第三代，测序技术正向着高通量、低成本方向发展。既有测序技术中，可按一定测序方略获得长度约为50–100个碱基对序列，称为读长（reads）。基因组复制份数约为50–100。基因组组装软件可依照得到所有读长组装成基因组，这些软件核心是某个组装算法。惯用组装算法重要基于OLC（Overlap/Layout/Consensus）办法、贪婪图办法、de Bruijn图办法等尽管如此，当前能直接读取碱基对序列长度远不大于基因组序列长度，因而需要运用一定办法将测序得到短片段序列组装成更长序列。
一种好算法应具备组装效果好、时间短、内存小等特点。新一代测序技术在高通量、低成本同步也带来了错误率略有增长、读长较短等缺陷，既有算法性能尚有较大改进空间。
本题规定咱们尝试建立模型，由程序计算得到基因组长须组装。算法与程序规定能有效地解决在测序过程中浮现碱基对辨认错误，或则基因中浮现重复片段状况。
将所建立模型检查运营后，本题规定咱们进一步对其进行探究。针对一种全长约为120,000个碱基对细菌人工染色体（BAC），采用Hiseq测序仪进行测序，结合附录中测序方略、数据格式以及读长数据，在测序长度约为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第五个碱基）
图 1 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
运用既有测序技术，可按一定测序方略获得长度约为50–100个碱基对序列，称为读长；
contig（C）：
由read通过一定算法拼接产生3kb～10Mb以内某些基因组片段;
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来扩展这条被视作contigread，重
复执行这样操作，最后便得到一定长度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}.=V\S,令=W（，）,=,.
（2） 更新，:=V\S,若<+,则令=+,=
（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 00001000
read2 00000001 00001110 00001010 10010000 01100011 10001100 11010100
read3 00000001 11000100 10101011 10111111 11010110 11010000 10010010
read4 00000001 11111000 11101010 00000011 01000101 11111111 11000010
初始kmer 00000001
后继kmer
contig 00000001

（3）当前候选后继k-mer状况如下：
初始kmer 00 00 00 01
候选后继kmer1 00 00 01 01
候选后继kmer2 00 00 01 00
候选后继kmer3 00 00 01 11
候选后继kmer4 00 00 01 11

（4）选定后继k-mer为 AACT,即00000111；进行下一段拼接，此时num为5，前驱结点cur 为1，addr为2；此时contig增长了一种碱基；

read1 00 00 00 01 01 11 11 01 01 00 00 10 11 10 11 11
read2 00 00 00 01 00 00 11 10 00 00 10 10 10 01 00 00
read3 00 00 00 01 11 00 01 00 10 10 10 11 10 11 11 11
read4 00 00 00 01 11 11 10 00 11 10 10 10 00 00 00 11
read5 00 00 01 00 11 11 11 00 11 11 11 00 00 00 00 10
初始kmer 00 00 00 01
后继kmer 00 00 01 11
contig 00 00 00 01 11

（5）重复（4）环节，直到无法找到符合条件后继k-mer则该条contig拼接结束；若该条contig长度不不大于100bp则保存下来，否则删除；程序继续运营以上案列，得到一种长度为360bpcontig如下：

{ }

（6）到此一条contig拼接结束，开始重复（1）环节；最后得到若干条长度不不大于100bp contig。
{ }
5.7基于概率模型基因组从头测序算法
在算法设计之初，咱们构想是如果已知第一条碱基片段和第二条碱基片段，那么就可以通过这两条碱基片段拟定基因组中下一条碱基片段。事实上，在基因组中通过第一条碱基片段和第二条碱基片段可以拟定第三条碱基片段往往不止一种，普通状况下浮现次数最多第三条碱基片段是对的。这是由于 read 数据中存在大量碱基测序错误，因而那些浮现次数较低碱基片段往往具有测序错误碱基。简而言之，算法核心思想就是通过第一条碱基片段和第二条碱基片段拟定第三条碱基片段，然后再通过这第二条碱基片段和第三条碱基片段拟定第四条碱基片段，重复这样操作，抱负状况下，最后便可以得到满足一定长度规定 contig。事实上，这与二阶马尔可夫模型思想不谋而合，即都是系统将来某一时刻状态仅仅依赖于当前两个状态。因而,本文所研究基于概率模型基因组从头测序算法将二阶马尔可夫模型运用到 DNA 拼接过程中。
基于概率模型基因组从头测序算法一方面运用 read 中信息构建概率模型，然后在序列末端截取两条相似长度碱基片段，运用概率模型便可拟定这两条碱基片段之后浮现概率最大某一碱基片段，并将其拼接在序列末端，这样序列便在原有长度基本上得到了扩展。算法继续在序列末端截取两条相似长度碱基片段，用同样办法便可得到新后继碱基片段，序列就在这样操作过程中得到不断地扩展，最后获得一定长度 contig。详细拼接过程如下所述。
若以 now 和 next 作为种子，假定 now =k1k2…k10，next =k11k12…k20（实际中 now 和 next 已被转换为相应十进制数）。一方面在主表中定位索引值为now元素，即prim -aryTable[now]。然后遍历 primaryTable[now]中指针所指向副表，若副表中只存在唯一项具有next，则该项中lastMer值即为所要寻找后缀last，假定last= k21k22k23k24，此时应将该项中freContig值加一，避免在下次拼接中选取该组now和 next 作为种子。这样便通过第一前缀now和第二前缀next并结合概率模型拟定了概率值为 1 后缀 last，同步序列在原有基本扩展了4个碱基。然后取当前序列最后20个碱基作为新第一前缀和第二前缀，即now =k5k6…k14，next =k15k16…k24，用同样办法拟定新第一前缀 now 和第二前缀 next 后缀 last。重复执行上述操作，序列便在原有基本上不断地扩展，最后得到一种完整contig。
然而，在实际拼接过程中，通过第一前缀now和第二前缀next在哈希表中可以拟定后缀 last 往往不止一种，这是由于尽管使用 HiTEC 办法进行了测序数据纠错解决，但在 read 数据中依然存在大量碱基测序错误，因而对于同一种后缀 last，它们在 read 数据中也许有各种存在形式，区别仅在于1~2 个碱基不同。事实上，对于一种后缀 last，尽管存在某些具有测序错误碱基后缀干扰，但对的后缀 last 浮现概率要明显不不大于那些具有测序错误碱基后缀，因而对于这种状况，应当选取浮现概率明显较大后缀作为对的后缀 last。当浮现无后缀状况或浮现概率较大后缀不止一种时，算法结束本次拼接并输出一条contig，然后选用新种子now和next进行下一条 contig拼接。综上所述，基于概率模型基因组从头测序算法描述如下。
基于概率模型基因组从头测序算法：
算法输入：经 HiTEC 办法纠错解决 read 数据
算法输出：n 条 conitg（0 < n < 3000）
算法环节：
01. 由 read 数据构建概率模型；
02. 拟定种子now和next，若不存在种子，则转至环节8；
03. 在主表中定位索引值为now元素，遍历primaryTable[now]中指针所指向副表；
04. 若副表中存在唯一项t满足nextMer等于next，则last等于该项中
lastMer值，获取新now和next，转至环节3，否则继续环节5；
05. 若副表中存在 n(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长度在 35bp~75bp，与此同步，碱基测序错误率在 1%~2%。在DNA拼接过程中，测序错误可以导致大量问题，大大减少了拼接成果精确率。因而，在进行DNA序列拼接之前，有必要对 read 数据进行预解决，修正 read 中测序错误碱基，从而提高DNA序列拼接效果。当前对read数据进行预解决办法大体上可以分为两类：一类是修正测序错误碱基，咱们称之为“纠错”，另一类是删除具有大量测序错误read。然而，第二类办法存在减少read数据覆盖率风险，这在一定程序上会减少算法精准性，因而下面给出HiTEC纠错算法，优化模型。
给定某一长度为 L 基因组 G，G 可以理解为由字符 A、T、G、C 构成字符串，且每一种字符浮现概率均为0.25。假定有n条来自基因组Gread，记作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个位置上碱基均是对的，即ri[k – w…k − 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].系统科学与数学,.
[2]王东阳，任世军，王亚东.DNA序列拼接中de Burijn图构造研究[J].智能计算机与应用,.
[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 stub
File file=new File("E:\\基因数据","data1.txt")；/*File file2=new File("D:\\基因数组","oo.txt");*/
String []a = new String[60000];
String []b = new String[60000];
String []c = new String[60000];
DataInput myData = new DataInput();
try{
FileReader 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())!=null;i++){ if(i%4 == 1){
a[j] = s;
j++;
}else if(i%4 == 2){
b[k] = myData.StringToByte(s);
k++;
}else if(i%4 == 0){
c[p] = s;
p++;
}
/* System.out.println(i+":"+s);
outTwo.write(i+":"+s);//write()函数用法▲
outTwo.newLine();*/
}
inOne.close();
inTwo.close();
/* outTwo.flush();//▲
outOne.close();
outTwo.close();*/
}
catch(Exception e){
System.out.println(e);
}
for(int i = 0;i<100;i++)
System.out.println("a["+i+"]"+a[i]);
for(int i = 0;i<100;i++){
System.out.println(b[i]);
System.out.println("a[40000]"+a[40000]);
try {
Class.forName("com.mysql.jdbc.Driver");
String url = "jdbc:mysql://localhost/genmdata?user=cyh&password=1011325";
Connection conn =DriverManager.getConnection(url)；//Statement stmt = conn.createStatement();
String sql = "";
sql ="insert into datasave(dataId,data,quality) values(?,?,?)";
PreparedStatement pstmt = conn.prepareStatement(sql，Statement.RETURN_GENERATED_KEYS);
for(int i = 0;i<a.length;i++){
//sql = "insert into datasave(dataId,data,quality) values('"+a[i]+"','"+b[i]+"','"+c[i]+"')";
pstmt.setString(1,a[i]);
pstmt.setString(2,b[i]);
pstmt.setString(3,c[i]);
pstmt.executeUpdate();
//stmt.executeUpdate(sql);
}
//stmt.close();
pstmt.close();
conn.close();
} catch (ClassNotFoundException e1) {
// TODO Auto-generated catch block
e1.printStackTrace();
}
System.out.println("a1:"+a[1]);
}
public String StringToByte(String str){
String reString="";
char c[] = str.toCharArray();
for(int i=0;i<c.length;i++){
if(c[i]=='A'){
reString +="00";
}else if(c[i]=='C'){
reString +="01";
}else if(c[i]=='G'){ reString +="10"；}else if(c[i]=='T'){ reString +="11"；} } return reString；}
}