基于高通量测序数据的基因组从头组装方法

摘要

本发明提供了基于高通量测序数据的基因组从头组装方法，包括步骤：1)依据高通量测序数据构建de Bruijn图，基于纠错后的de Bruijn图进行测序数据纠错和super read组装；2)利用super read进行初级contigs组装；3)调取特定局部的初级contigs和reads，局部组装，将所有的局部组装结果合并；4)通过子图分割算法和模拟退火算法对contigs进行排序得到最终的scaffolds。本发明通过de Bruijn图纠错消除高通量测序带来的错误，提高了数据准确性；采用构建super read的方法提高测序读长，显著提升contigs长度；通过局部组装大大提升了重复序列的处理能力。

说明书

技术领域

本发明涉及一种基因组组装方法，特别是涉及一种基于短序列测 序片段的基因组从头组装方法。

背景技术

随着第二代测序技术的迅速发展，测序费用的急速下降，从头基 因组测序愈发受到研究者的青睐。但是，利用大量的短的read数据 重新恢复出基因组原貌也面临着巨大的挑战，而其中最为关键的一步 就是contigs组装。De Bruijn图构建是图论组装算法的核心，它是现 在主流从头组装算法的核心，它是基于kmer的重叠信息来构建欧拉 图，它是contigs构建的基石，因此本发明的开发也将基于De Bruijn 图。

目前的contigs组装算法都只进行一次De Bruijn图构建，同时针 对图中的kmer大小也是相对固定的，虽然存在一些多kmer组装算法， 但它们也都只进行一次构图，再进行合并。对于组装中使用的短序列 一般的组装软件也只是进行简单的过滤也纠错处理，并不会对这些最 原始的短序列进行二次加工，这也就在很大程度上限制的De Bruijn 图构建中kmer大小的上限。因此对于不进行短序列加工的基因组组 装方法，kmer大小都比较小，在De Bruijn图构建中会产生较多的分 支，极大的提高De Bruijn图的复杂度，从而降低组装效果。

另外，动植物基因组的一大特点就是重复序列比例较高，而重复 序列会让基因组组装过程中产生大量的可选位点和分支，进而提高组 装难度。目前主要有两种主流的策略来处理其中的部分情况：一种策 略是利用大片段文库跨过重复序列，并估计重复序列区域大小，然后 选取一个合适长度的重复序列路径；另一种则是先回避重复序列区 域，在完成初步组装后再回过头来进行重序区域的组装。从策略上讲， 第二种方法对于复杂基因组来说更有效，因为它把全局问题进行了局 部化，大大降低了组装的难度。

发明内容

针对现有技术存在的不足，本发明的目的是提供一种基于高通量 测序数据的基因组从头组装方法——GNOVO，该技术首先通过数据 纠错来处理高通量测序固有的测序错误，同时通super read组装将较短 的read组装为具有更大读长的super read，从而部分克服测序读长过短 的问题。其次，通过局部组装，将全基因组上的重复序列转变为局部 的单拷贝序列，从而大大降低了重复序列处理的难度，提高了contigs 组装的长度。

为了实现本发明目的，本发明的一种基于高通量测序数据的基因 组从头组装方法——GNOVO，主要步骤为：

1)通过高通量测序数据构建de Bruijn图(使用较小的kmer)，并 进行图纠错处理，并基于纠错后的de Bruijn图进行测序数据纠错，纠 错原理见图4；

2)基于纠错后的de Bruijn图进行super read组装；

3)用super read重新构建de Bruijn图(使用较大的kmer)，并进行 图纠错处理，对纠错后的de Bruijn图进行拆分，得到初级contigs；

4)根据mate-pair的连接信息调取特定局部的初级contigs，并依 据测序数据的比对信息收集局部的reads进行局部组装，将所有的局部 组装结果合并到一起，并进行纠错后拆分处理，从而得到contigs；

5)根据mate-pair的连接信息构建scaffold连接图，通过子图分割 算法对contigs进行分割，并采用模拟退火算法在局部对contigs进行排 序得到最终的scaffolds。

GNOVO组装原理流程图见图1。

步骤1-4中都是以de Bruijn图为核心结构的，在GNOVO中，de  Bruijn图是以哈希的数据结构形式存在的，其构建算法为：

1)根据基因组大小和kmer大小对哈希表进行空间分配与初始化；

2)迭代读取每条read，并进行编号，编号从0开始。

3)从5’到3’端依次提取所有的kmer，并将其存贮到哈希表中。 如果kmer已经存在，则只需存贮kmer的路径信息就可以了，即存贮其 前驱与后驱。如果kmer不存在，则需要新建kmer节点，同时还需存贮 路径信息。

4)存贮read中第一个kmer信息时，如果其在哈希表中不存在， 则说明其真前驱kmer节点不存在，至少到当前为止，它是不存在的。 因此，这个时候就需要新建一个未端测序突起节点，用于取代真实前 驱kmer节点，作为该kmer节点的回溯前驱节点。

5)在存贮非第一个kmer节点时，如果发现该kmer已经存在了， 并且该kmer节点的回溯前驱节点为未端测序突起节点，则需要将该未 端测序突起节点去掉，同时将该kmer节点回溯前驱节点设置为前一个 kmer节点。因为，在当前read中，该kmer不是第一个kmer，所以其一 定有一个真实前驱，即它的前一个kmer，因此，可以用真实前驱kmer 节点来代替未端测序突起节点，从而减少未端测序突起数量，进而节 省部分内存。

de Bruijn图作为核心数据结构，其准确性是十分重要的，因此， GNOVO中开发了一系列的图纠错处理，主要步骤包装：1)de Bruijn 图简化处理；2)未端测序突起删除处理；3)泡状路径合并操作；4) 低覆盖度边清除处理。

1)de Bruijn图简化处理：依据哈希表，对每个kmer节点进行遍 历。对于当前kmer节点，依据其真实前驱与后驱进行延伸，如果当前 kmer节点的互补节点也存在，则需要同时依据这两个节点进行延伸。 延伸方法：沿着出边与入边的方向进行延伸，即沿真实前驱与后驱进 行延伸。单个方向上的延伸条件：延伸处的kmer节点(包括其互补 kmer，如果存在)有且仅有一个真实前驱，同时有且仅有一个真实后 驱。单个方向上的延伸终止：对于后驱延伸来说，延伸到的当前kmer 节点有两个或多个真实前驱，或者说有两个或多个真实后驱，或者说 没有真实后驱了，或者说延伸到的当前kmer节点已经在De Bruijn图中 存在了。对于前驱延伸来说，延伸到的当前kmer节点有两个或多个真 实前驱，或者说有两个或多个真实后驱，或者说没有真实前驱了，或 者说延伸到的当前kmer节点已经在De Bruijn图中存在了。

2)未端测序突起主要是由于read末端的测序错误产生的， GNOVO中未端测序突起错误的判断标准为：a)长度小于2K(K为kmer 的长度)；b)必须存在高覆盖度的等位入边或出边。

3)泡状路径是指由具有相同起点和终点的两条不同的路径构成 的图形结构，除起点和终点外，图形内部不存在其它任何的交叉节点。 泡状路径主要是由杂合位点与read中部的测序错误产生的，GNOVO 中泡状路径的定义为：1)路径长度均小于200bp；2)路径的相似度 大于0.8；3)至少有一条路径的覆盖度低于某个特定的阈值。泡状路 径搜索算法的核心算法是“Dijkstra-like breadth-first search”(Dijkstra 算法是最短路径搜索算法中最著名的算法，“breadth-first search”表 示广度优先遍历)。

4)低覆盖度边主要是由read测序错误产生的，其主要的判别标 准：1)覆盖度小于某个特定的阈值；2)边两端的节点均存在除当前 边外的至少一个真实前驱和至少一个真实后驱。覆盖度阈值的选取， 对于单倍体来说，一般默认选取边覆盖度的均值或者说中位数的1/2， 对于双倍体基因组来说，默认选取边覆盖度的均值或者说中位数的 1/4。但是最好的方法是根据覆盖度的总体分布进行阈值的选取。

Super Read是指一条较长的序列，它是通过补齐paired-end之间的 缺口或者说是通过重叠信息连接paired-end两端而得到的一条序列， Super Read的构建原理见图5。由于它是基于paired-end获得的，因此 它的长度的期望值将为文库片段大小。由于super read是连接了双端的 read与中间的缺口，因此其长度一般比read的读长长很多，以super read 作为组装起点具有非常大的优势。Super read的组装是采用深度优先 算法进行路径搜索得到的。

在很多分析中，都是基于单拷贝节点出发的，原因主要有：1) 先从单拷贝节点出发，组装分析比较容易，而且出错的概率会较小。 2)有了单拷贝节点的信息，则在后期处理重复序列时可以借助它作 为基点，解决一部分重复序列组装。

这里假设有一条边，它的长度为n，Xi表示以边上的位点i为read 起始位点的read数目(注意这里边长的实际长度为n-k+1，因为边是以 kmer为基础的，因此i的最大值为n-k+1)。这里假设Xi为独立的随机 变量，它是服从期望为ρ的泊松分布，它的期望ρ由边的覆盖度的分 布来确定(这里是指所有边的覆盖度的分布情况，即总体分布)。

根据中心极限理论，一个长度为n的边上的Xi的期望值应该服从 均值为ρ，标准差为的正态分布。如果某条边是单拷贝边， 那么Xi的平均值与ρ的差异就不应太大。这里取下面的比值作为边唯 一性的判定准确：

$F(\bar{X},n,\rho )=\frac{\log 2}{2}+(n-k+1)\frac{{\rho }^2-{\bar{X}}^2/2}{2\rho }$

为了衡量边的特异性或者说唯一性，GNOVO中采用F>＝5作为 判定的标准。即F越大(即Xi的平均值越小)，边的特异性就越强， 但小的Xi的平均值也可能是由于测序错误而导致的，但是这部分错 误一般都能在前面的纠错过程中被纠正。

GNOVO中局部组装算法主要思想是通过对基因组进行局部化的 组装，降低组装的复杂性，得到较好的局部组装效果。再通过合并每 个局部组装的结果，得到整个基因组的组装结果，使基因组组装效果 (contigs)得到明显提升，局部组装原理可以参考图6。其主要的步骤有：

1)将初级contigs和reads做比对，通过reads的比对结果，得到初 级contigs之间的距离信息，以及reads和初级contigs的关系。将初级 contigs和reads信息读入内存。

2)初级contigs种子的选取。过滤掉多拷贝(拷贝数>2)或长度较 短的初级contigs。对保留的初级contigs根据初级contigs之间的距离关 系，构建scaffold连接图，并在其中选择相距较远且较长的初级contigs 作为种子。得到种子后将选出在种子附近一定范围内的初级contigs。

3)局部reads选取：对每个局部的初级contigs，根据比对结果选 择只有一端在初级contigs上的测序片段。同时将处在缺口处并且测序 片段覆盖度大于0.9的super read也选取出来。

4)在局部构建de Bruijn图进行局部组装。

5)把每个局部图内的局部组装结果进行合并，得到全局的组装 结果，然后进行简化与图纠错处理，从而得到最终的contigs。

在scaffold组装过程中，首先会将整体的scaffold图进行子图拆分， 分割为一个个小的独立的子图，该子图与其他contigs的paired end都落 在边界contigs(长度大于文库大小的contigs，正常paired reads不可能 跨过它)上，因此可以将每个子图都看成是一个小整体，对其单独进 行scaffold组装。GNOVO中采用模拟退火算法对contigs进行排序，排 序过程中选取冲突边最小的排序结果为最终的scaffold。scaffold组装 后，会将其看成一个整体，再重新与其他contigs进行组装。

采用模拟退火算法对子图中的contigs完成排序后，GNOVO采用 二次规化算法进行相邻contigs间的缺口大小的估计，计算过程中的目 标函数为：

$f\left(\chi \right)=\underset{\mathrm{iϵE}}{\Sigma }\frac{{((C_i+{\Sigma }_{\mathrm{jϵ}{G}_i}{g}_j)-{\mu }_i)}^2}{{\sigma }_i^2}$

公式中，E为子图中边的集合，C_i为边i跨过的contigs的总长， 为边i跨过的缺口的总长，μ_i为边i对应的平均文库大小，为 边i对应文库的方差。

所述的基因组从头组装方法，其中所述的组装方法在Linux操作 系统上采用C语言、perl语言和fortran语言编程实现，可对大基因 组测序数据进行处理，计算具有可并行性、内存较低和速度快等优点。

本发明的关键点在于：

1)通过先对de Bruijn图纠错的方法先进行图纠错，然后再用纠 错后的de Bruijn图来对高通量测序数据进行纠错处理。

2)依据纠错后的de Bruijn图，采用路径搜索算法来对pair-end进 行组装，进而得到读长较长的super read，并采用super read进行初级 contigs构建。

3)根据pair-end和mate-pair的比对信息调取特定局部的初级 contigs和reads，进行局部组装，最后将所有的局部组装结果合并到一 起得到contigs。

4)采用模拟退火算法对分割后的scaffold子图进行scaffold组装。

采用局部组装的策略先在每个局部进行组装，将整体系统的复杂 性转化局部的单一性，从而大大降低组装的难度。

本发明的基于高通量测序数据的基因组从头组装方法(命名为 GNOVO方法)中的contigs组装思路与一般的contigs组装算法不同， 它采用两次构建De Bruijn图的策略，第一个图是基于较小的K进行 构建的，主要用于纠错与super read构建；而第二个图则是利用super  read数据，并基于较大的K进行构建的，其主要用于初级contigs构 建。由于初级contigs的构建是基于具有较大长度的super read来构建 的，同时较大的K也能更好的处理部分重复序列。Super read处理重 复序列组装方向的应用见图2。另外，由于高通量测序的read都较短， 为基因组组装算法提出了巨大的挑战，但是本发明的研发思路却是从 基因组组装算法中跳跃出来，将研发的重点放在如何提高read的长 度，从而为组装算法的输入提供更高的起点。根据pair-end之间的距 离信息，利用图论算法完成pair-end间缺口的填充，进而得到较长长 度的super read(对于有重叠信息的pair-end，则直接进行连接即可)。 由于高通量测序数据的read都非常短，而super read的长度较read 要长许多，因此以super read作为组装的起点的策略将会有更大的优 势，如：1)可以使用更长的重叠信息进行read连接；2)super read 能够跨过更长的重复序列(见图2)；3)GNOVO基于super read能 够采用更大的KMER，降低图复杂度，进而更好的处理杂合序列(见 图3)。其次，利用局部组装的思想，将全基因组上的重复序列转变 为局部的单拷贝序列，从而大大降低了重复序列处理的难度，提高了 contigs组装的长度。GNOVO中的局部组装算法根据pair-end和 mate-pair的比对信息调取特定局部的初级contigs和reads，进行局部 组装，最后将所有的局部组装结果合并到一起得到contigs。最后， GNOVO还结合子图分割算法与模拟退火算法对得到的contigs进行 排序，得到最终的scaffolds。

本发明的有益效果主要表现在：

1)通过基于纠错后的de Bruijn图对原始测序数据进行纠错，保 证了测序结果的准确性，碱基错误率一般小于0.0001，同时也提供了 一种新的测序数据纠错方法。

2)基于de Bruijn图，采用路径搜索算法来对pair-end进行组装， 可以得到更长的序列，从而大大降低组装的难度，对于180bp文库来 说可以得到150bp至230bp的序列。

3)利用super read进行基因组组装，有利于de Bruijn图组装算法 中采用更大的kmer(>95)，从而降低图复杂度，提高初级contigs的长 度，保证了最终的组装效果，对于细菌数据N50可以直接超过10kb， 甚至可以达到30-50kb。

4)采用局部组装策，在局部对部分基因组进行组装，大大降低 了组装难度，特别是重复序列组装的难度，保证了最终contigs的长度， 对于细菌数据N50可以直接超过50kb，甚至可以达到100-500kb，同时 也提供了一种新的局部组装方法；

5)采用模拟退火算法对分割后的scaffold子图进行scaffold组装， 所构建的scaffold长度更长，N50通常能达到500kb以上。

6)充分利用Linux集群优势，通过并行计算设计和路径哈希设计 等途径提高了运算效率，克服了计算机内存对大数据集运算的制约， 可完成10G以内的基因组组装。

附图说明

图1为GNOVO组装流程概括图，其中A为原始数据过滤，如果测 序read中的N碱基比例较高(>5％)，或者说低质量碱基(质量值<20) 的比例较高(>5％)，则这样的read将在原始测序数据处理阶段被过滤 掉。B为read纠错，基于纠错后的de Bruijn图，paired ends与mate-pairs 数据将分别采用不同的策略进行纠错。C为Super read构建成，基于纠 错后的de Bruijn图，采用路径搜索算法进行super read构建。D为初级 contigs组装，利用super reads数据，采用大kmer，依据de Bruijn图理 论构建初级contigs。E为局部组装，先调取种子附近的单拷贝初级 contigs，然后从单端比对数据中调取局数read，最后在小的局部构建 de Bruijn图进行组装。F为Scaffold构建，即根据mate-pair的连接信息 构建scaffold。

图2为重复序列解决方案图，其中A为大kmer策略，即采用比重 复序列长的kmer进行重复序列组装。B和C为连接策略，即利用paired  ends和mate-pairs的连接信息，或者说是super reads的跨过连接信息， 将中等长度的重复序列进行组装。D为局部组装策略，在局部，很多 重复序列都是单拷贝的，容易进行组装的。E为缺口填充策略，即在 完成scaffold组装后，针对每个缺口进行局部组装。

图3为杂合序列处理方案图，其中A为对简单的孤立的SNP区域进 行合并。B为通过super read的跨过连接信息，识别相邻杂合序列的组 装方式，并进行合并处理。C为对于距离较近的较大杂合区域，采用 paired ends或者说是mate-pairs的连接信息，将杂合部分进行合并。

图4为Read纠错图，其中A为利用简单过滤后的原始测序数据构 建de Bruijn图，然后进行纠错处理，处理方式主要为未端测序突起删 除、错误边删除和泡状路径合并。B为Paired ends纠错，其中小的灰 色矩形为测序错误，PE为原始read，PE*为纠错后的read。C为 Mate-pairs数据纠错，MP为包含测序错误的read，MP*是纠错后的结 果。其中灰色的矩形部分为测序错误，即图中的E，在纠错过程中将 被删除。J是文库构建过程中引入的环化位点。

图5为Super read构建原理概括图，其中A中R1和R2分别为paired  end的两端序列，通过kmer检索的方式定位到纠错后的de Bruijn图上。 B为采用图论中的路径搜索算法进行R1与R2间路径的搜索，图中的虚 线为搜索得到的路径。C为依据搜索路径上的kmer信息，提取完成的 路径序列，即super read。

图6为局部组装原理概括图，其中A中“c1,”“c2,”“c3,”“c4,” “c5,”“r1,”“r2,”和“r3”为初级contigs，“c1,”“c2,”“c3,” “c4,”和“c5”都是单拷贝,“r1,”“r2,”和“r3”都是单拷 贝，“c2”和“c4”是从所有单拷贝初级contigs中筛选得到的种 子。B中灰色的弧线为mate-pairs在不同初级contigs之间的连接信息。 “c1”和“c3”是“c2”的邻近初级contigs，“c3”和“c5”是“c4” 的邻近初级contigs。短的灰色矩形为UARs，即没有比对单拷贝初级 contigs的read。C为在局部构建de Bruijn图，并进行纠错。D为基于 局部纠错后的de Bruijn图，对有连接的关系的初级contigs进行路径 搜索，进行局部组装。E为将所有的组装结果进行合并，得到最终的 基因组组装结果。

图7为两歧双歧杆菌(Bifidobacterium bifidum PRL2010)基因组 共线性图。GNOVO组装结果与两歧双歧杆菌(基因组序登录号为 CP001840.1,组装基因组大小为2,214,656bp)的共线性图，其中纵向 为GNOVO的组装基因组，横向为参考基因组，黑色点线为基因组共 线性部分。

图8为链霉菌(Streptomyces roseosporus NRRL 15998)基因组共 线性图。GNOVO组装结果与链霉菌(Streptomyces roseosporus NRRL 15998，基因组序登录号为NZ_DS999644.1,组装基因组大小为 7,817,295bp)的共线性图，其中纵向为GNOVO的组装基因组，横向 为参考基因组，点线为基因组共线性部分。

具体实施方式

以下实施例用于说明本发明，但不用来限制本发明的范围。

实施例1 大肠杆菌(E.coli)基因组组装

1)测试数据介绍

该测试数据是从NCBI(National Center for Biotechnology  Information，即美国国立生物技术信息中心)的SRA(Short Read  Archive)数据库下载得到的，SRA数据库网址为 www.ncbi.nlm.nih.gov/sra，数据的详细登录号为SRX016044。测试数 据的详细信息如下：

上传日期：2009-05-22；

文库大小：180bp；

测序总量：2.1G；

预测基因组测序深度：456.5x。

2)评估方法

共对7个组装软件进行测试比较，对每个组装软件的主要参数进 行遍历，然后选取组装结果最好的结果进行比较评估，各软件最好组 装结果的详细组装参数如下：

GNOVO(本发明方法)组装参数为：k1＝25，k2＝95，m1＝5， m2＝2，其它参数均为默认参数，这里k1为第一次构建de Bruijn图的 kmer大小，k2为第二次基于super read进行初级contig组装时构建de  Bruijn图的kmer大小；m1为第一次构建de Bruijn图时，进行低覆盖度 边删除纠错处理的参数，用于定义低覆盖度的阈值，m2为第二次构 建de Bruijn图时，进行低覆盖度边删除纠错处理的参数，用于定义低 覆盖度的阈值；

JR-Assembler组装参数为：均为默认参数；

Edena：m＝53，其它参数均为默认参数；

Taipan：k＝50，其它参数均为默认参数；

Velvet：k＝45，其它参数均为默认参数；

ABySS：k＝45，其它参数均为默认参数；

SOAPdenovo：k＝53，其它参数均为默认参数；

GNOVO在进行组装时，第一步通过高通量测序数据构建de  Bruijn图，并基于纠错后的de Bruijn图进行测序数据纠错。这里进行 构建de Bruijn图时kmer大小采用25(采用参数k1进行指定)，同时对 原始de Bruijn图进行纠错，这里对低覆盖度边进行删除时采用5为阈 值，即深度小于5的边都将被删除。在完成图纠错后，原始测序reads 将被比对到de Bruijn图上进行纠错。

纠错前后de Bruijn图主要信息见表1：

表1 GNOVO方法组装E.coli基因组第一步纠错前后de Bruijn图主要信息

从纠错前后的指标对比可以看出，kmer总数降低大约10％，但是 节点数与kmer种类数却都分别下降了400倍和80倍，可见测序错误产 生了大量的低深度kmer和额外的节点，从而使用de Bruijn图的复杂度 极大的提高了。

GNOVO在进行组装时，第二步将read比对回de Bruijn图中，采用 路径搜索算法构建super read。在进行路径搜索过程中，默认的搜索参 考为3，即3倍的准确差。原始read数为6096923，成功构建Super read 的read数目为5843968，搜索效率为95.8％(5843968/6096923)。

GNOVO在进行组装时，第三步利用super read重新构建de Bruijn 图，通过图纠错和拆分处理，得到初级contig。这里进行构建de Bruijn 图时kmer大小采用95(采用参数k2进行指定)，同时对原始de Bruijn 图进行纠错，这里对低覆盖度边进行删除时采用2为阈值，即深度小 于2的边都将被删除。在完成图纠错后，将de Bruijn图从节点处进行 拆分，得到初级contigs。

纠错前后de Bruijn图主要信息如下：

表2 GNOVO方法组装E.coli基因组第三步纠错前后de Bruijn图主要信息

从上表可以看出，此时的图复杂度已经非常低了，只有2324个节 点了，即组装的完整性是非常好的。

得到的初组contigs的统计信息为：contig总长为4.55Mb，contigs 总数为169，contig N50长度为60284bp。

GNOVO在进行组装时，第四步根据pair-end和mate-pair的比对信 息调取特定局部的初级contigs和reads，进行局部组装。在局部组装中， 默认最小支持度为3，即两个初级contigs间的连接数只有大于等于3时 才有效(参数-cutoff进行设置，一般不建议修改)。局部组装中的kmer 大小使用多kmer，默认情况下为19、57和95(通过参数“-k”、“-q” 和“-n”进行设置)。组装得到的contigs的统计信息为：contig总长为 4.55Mb，contigs总数为161，contig N50长度为63618bp。

GNOVO在进行组装时，第五步利用mate-pair连接信息构建 scaffold连接图，通过子图分割算法和模拟退火算法对contigs进行排序 得到最终的scaffolds。在scaffold组装过程中，同样默认最小支持度为 3，即两个初级contigs间的连接数只有大于等于3时才有效(参数-cutoff 进行设置，一般不建议修改)。这里由于没有大文库，因此scaffold组 装效果没有提升，与第四步组装一致。

3)结果比较

各组装软件的组装结果见表3：

表3 各组装软件组装E.coli基因组结果

contigs数目:长度在300bp以下的Contigs不进行统计。

总长：所有contigs的总长。

最大contig长度：组装结果中最长contig的长度最长最长的contig的长度和

平均contig长度：所有contig长度的平均值。

N50：表示将所有的Contigs按照从长到短进行排序，然后将Contig按照这个顺序依次相加，当相加的长度达 到Contig总长度的一半时，最后一个加上的Contig长度即为Contig N50。

组装错误contig数：不能比对到原始的参考基因组上的contig数目。

本实施例中，本发明的组装方法GNOVO得到了161个contigs，其 次为JR-Assembler软件的方法，得到192个contigs，远优于其他组装软 件，并且GNOVO的N50长度为63.618K，比JR-Assembler(48.673K) 和Velvet(43.998K)高出10K以上，说明GNOVO的组装完整性在该 实例中远好于其他组装软件。GNOVO得到的最长contig为334.908K， 比其他软件高出100K以上。GNOVO的错误组装的contig数为0，与其 他大部分软件一致，显示了其高准确性。在本实施例中，GNOVO较 其他组装软件显示了较大的优势。

实施例2 链霉菌(S.roseosporus)基因组组装

1)测试数据介绍

该测试数据是从NCBI的SRA数据库下载得到的，SRA数据库网 址为www.ncbi.nlm.nih.gov/sra，数据的详细登录号为SRX026747和 SRX016085。

a)测试数据SRX026747的详细信息如下：

上传日期：2010-08-06；

文库大小：180bp；

测序总量：10.7G；

预测基因组测序深度：1389.6X。

b)测试数据SRX016085的详细信息如下：

上传日期：2009-09-20；

文库大小：4kb；

测序总量：3.5G；

预测基因组测序深度：454.5X。

2)评估方法

这里共对5个组装软件进行测试比较，对每个组装软件的主要参 数进行遍历，然后选取组装结果最好的结果进行比较评估，各软件最 好组装结果的详细组装参数如下：

GNOVO组装参数为：k1＝25，k2＝95，m1＝11，m2＝5，其它参数 均为默认参数(详细的评估细节可参考实施例1)；

JR-Assembler：均为默认参数

ABySS：k＝45，其它参数均为默认参数；

Velvet：k＝49，其它参数均为默认参数；

SOAPdenovo：k＝63，其它参数均为默认参数；

3)结果比较

各组装软件的组装结果见表4：

表4

在本实施例中，GNOVO的N50为最高的13.134K，其次为 Velvet(12.499K)；最长contig长度为73.115K，比Velvet(61.423K)高 出10K以上。Contig数量为1,242个，多于ABySS最少的1,127个。本实 例中，GNOVO在contig最大长度、平均长度、N50长度上均比其他组 装软件略优，仅在contig数上稍高于ABySS，整体上展示了较好的组 装能力。

但是值得注意的是，GNOVO的组装结果的大小为9.79M，明显 大于其它的组装结果。因此，发明人对原始数据进行了nt数据比对， 比对结果显示原始数据中含有两个细菌的数据，因此推测原始数据为 一个混合菌。通过从NCBI下载对应细菌的参考基因组，即链霉菌 (Streptomyces roseosporus NRRL 15998，基因组序登录号为 NZ_DS999644.1,组装基因组大小为7,817,295bp)和两歧双歧杆菌 (Bifidobacterium bifidum PRL2010，基因组序登录号为CP001840.1, 组装基因组大小为2,214,656bp)，通过MUMMER进行全基因组比对 (相似度要求99％)发现，GNOVO的组装结果可以很好的比对到这 两个基因组上，比对结果见图7和图8。同时，这也证明了发明人开始 的推测，即原始数据是一个混合菌，同时也从侧面证明了GNOVO显 著提升contigs长度，具有较高的组装准确性，通过局部组装大大提升 了重复序列的处理能力。

实施例3 粗糙脉孢菌(N.crassa)基因组组装

1)测试数据介绍

该测试数据是从NCBI的SRA数据库下载得到的，SRA数据库网 址为www.ncbi.nlm.nih.gov/sra，数据的详细登录号为SRX030834。

a)测试数据SRX030834的详细信息如下：

上传日期：2010-11-11；

文库大小：180bp；

测序总量：5.5G；

预测基因组测序深度：148.3X。

2)评估方法

这里共对6个组装软件进行测试比较，这里对每个组装软件的主 要参数进行遍历，然后选取组装结果最好的结果进行比较评估，各软 件最好组装结果的详细组装参数如下：

GNOVO组装参数为：k1＝25，k2＝95，m1＝5，m2＝2，其它参数 均为默认参数(详细的评估细节可参考实施例1)；

JR-Assembler：均为默认参数

ABySS：k＝35，其它参数均为默认参数；

Velvet：k＝37，其它参数均为默认参数；

SOAPdenovo：k＝47，其它参数均为默认参数；

Edena：m＝45，其它参数均为默认参数；

3)结果比较

各组装软件的组装结果见表5：

表5

本实施例中，GNOVO的N50为10.473K，较其他组装软件(4～6K) 有较好的组装完整性；组装的contig最大长度和平均长度均优于其他 组装软件。GNOVO的contig数为11,300，多于Velvet的10,187个，位于 第二位。在该实施例中，GNOVO整体的组装效果上要优于其他组装 软件。

实施例4 中间葡萄球菌(S.intermedius ATCC 27335)基因组组装

1)测试数据介绍

该测试数据是从NCBI的SRA数据库下载得到的，SRA数据库网 址为www.ncbi.nlm.nih.gov/sra，数据的详细登录号为SRX297066和 SRX297065。

a)测试数据SRX297066的详细信息如下：

上传日期：2012-11-18；

文库大小：180bp；

测序总量：1.1G；

预测基因组测序深度：564.10X。

b)测试数据SRX297065的详细信息如下：

上传日期：2012-11-19；

文库大小：5kb；

测序总量：1.5G；

预测基因组测序深度：769.23X。

2)评估方法

共对5个组装软件进行测试比较，对每个组装软件的主要参数进 行遍历，然后选取组装结果最好的结果进行比较评估，各软件最好组 装结果的详细组装参数如下：

GNOVO组装参数为：k1＝25，k2＝95，m1＝11，m2＝2，其它参数 均为默认参数(详细的评估细节可参考实施例1)；

Allpaths-lg：均为默认参数

SPAdes：K＝61,73,95，其它参数均为默认参数；

MaSuRCA：k＝85，其它参数均为默认参数；

SOAPdenovo：k＝77，其它参数均为默认参数；

3)结果比较

各组装软件的组装结果见表6：

表6

本实施例中，GNOVO组装得到了细菌的完整序列(1个Scaffold)， Contig数7个，远优于其他组装软件(10个以上的Scaffold)，显示了其 在组装上的强大能力，GNOVO显著提升contigs长度；通过局部组装 大大提升了重复序列的处理能力。

虽然，上文中已经用一般性说明及具体实施方案对本发明作了详 尽的描述，但在本发明基础上，可以对之作一些修改或改进，这对本 领域技术人员而言是显而易见的。因此，在不偏离本发明精神的基础 上所做的这些修改或改进，均属于本发明要求保护的范围。