目前,构建Graph的主流方法有3种,Overlap-Layout-Consensus(Celera Assembler、PBcR),de Bruijn Graph(SOAPdenovo )和 String Graph(Falcon)。 相关文献 · 基于De Bruijn图的宏基因组序列组装算法研究(CNKI) · 对基因组组装算法的分析和研究(CNKI) · 基于De Bruijn图的De Novo序列组装软件性能分析(CNKI) · DNA序列拼接中de Bruijn图结构的研究(CNKI) · 基因组学策略(二)揭开组装的神秘面纱上篇(诺禾致源) ·
前言 基因组组装的基本思路:无论是一代sanger、二代短reads、三代长Pacbio,我们得到的测序数据相较于整个基因组而言仍然是极小的;我们的任务就是将这些小片段连接起来;序列之间的联系因为重复序列的存在变得非常复杂,通过overlap我们最终都会构建Graph,所有的算法都会从Graph中得到最优路径,从而得到最初的contig。 1 OLC算法 适用于reads读长较大的测序数据,如一代和三代的reads。 主要分为三步:(1)Overlap:,对所有reads进行两两比对,找到片段间的重叠信息;(2)Layout:根据得到的重叠信息将存在的重叠片段建立一种组合关系,形成重叠群,即Contig;(3)根据构成Contig的片段的原始质量数据,在重叠群中寻找一条质量最重的序列路径,并获得与路径对应的序列,即Consensus。 OLC算法最初成功的用于Sange测序数据的组装,比如Celera Assembler,Phrap,Newbler等均采用该算法进行拼接组装。 2 DBG算法 适用于reads比较短的测序数据,二代数据。缺点:难以对重复序列区域进行分析,更依赖于建库。 首先将reads打断成长度为K的核酸片段,即Kmer,在利用Kmer间的overlap关系构建DBG,再通过DBG得到基因组序列。 DBG算法最早应用于如细菌类小的基因组的组装上,直到李瑞强等(2010)开发SOAPdenovo 算法,成功的组装了采用二代测序的黄瓜及熊猫的基因组,DBG算法开始普遍运用。 DBG算法相比于OLC的优势是什么? 由于二代测序得到的reads长度较短,包含的信息量较少,因此完成基因组拼接需要较高的覆盖度。OLC算法适用于读长较长的序列组装,通过构成的OLC图寻找Consensus sequence的过程,实际上是哈密顿通路寻找的问题,算法非常复杂。 若采用OLC算法,会大大增加拼接的复杂性以及运算量。而采用DBG算法,通过K-1的overlap关系,构建DBG图,通过寻找欧拉路径得到Contig序列,从算法的角度极大的简化了组装的难度。 讲完算法,我们以目前应用广泛的 SOAPdenovo 软件为例来介绍组装过程。 SOAPdenovo软件的组装过程 (1)通过Kmer之间K-1的overlap关系构建contig(重叠群),如图2: (2)利用pair-end信息,将无overlap关系的contigs搭建成scaffold(脚手架),如图3: 1数据纠错 要得到一个有较高准确性的基因组图谱,首先对测序得到的数据进行处理:
绘制Kmer频数分布图时,如上图b所示,Error free代表没有测序错误的Kmer频数分布,Error rate1%代表有1%错误率的Kmer频数分布。 错误Kmer对后续组装会产生很大的困扰,因此,在构建DBG图之前,需要先对数据进行纠错。纠错的两种方法: (1)基于Read间的比对,通过多序列比对,通过概率模型区分测序错误引起的错误Kmer。这种方法纠错准确,但需要消耗较大的计算资源。如ALLPATH-LG,ECHO等纠错软件都基于这种方法。 (2)通过Kmer频数图谱进行区分,这类软件如SOAPdenovo,Euler等。 2构建Contig 根据Kmer之间的overlap关系进行连接,如下图所示:
(1)对De Bruijn图进行化简 简化DeBruijn图需要去掉无法继续连接的分支、低覆盖度的分支,并且利用序列信息化简重复序列在De Bruijn图的分叉通路,对于少量的杂合位点,采用随机选择策略,合并杂合位点。通常需要考虑如下几种情况:
3构建scaffold 将测序得到的reads比对回得到的contigs,利用reads之间的连接关系和插入片段大小信息,将contigs组装成scaffolds。 4补洞 得到的scaffold中间会有较多的gap,为了使组装的序列更完整,需再次利用测序的双末端数据之间的配对关系连接contigs,并利用测序数据与已经组装的contig之间的覆盖关系对contig之间空隙进行补洞,延长contigs,补洞后的contigs长度相比补洞之前一般增加2-7倍。 “揭开组装的神秘面纱下篇”敬请期待~ 参考文献 1. Li RQ, Zhu HM, Ruan J, et al. Denovo assembly ofhuman genomes with massively parallel short readsequencing. Genome Res. 2010,20(2), 265-72. 2. Li ZY, Chen YX, Mu DS, et al. Comparison of the two majorclasses ofassembly algorithms: overlap-layout-consensus andde-bruijn-graph. Brief Funct Genomics. 2012, 11(1), 25-37
3 string graph算法 有利于组装散列重复序列。 string graph中的节点是长度不一的序列,这些序列是由overlappingreads生成,需要设置一个最小overlap大小。
本文转自http://www.cnblogs.com/leezx/p/5590159.html
|
|