【2.0】基因组组装-拼接的两种算法OLC和DBG
从测序的代数看
- 一代测序双脱氧终止法：成本高，读长长，但是通量低
- 二代测序焦磷酸（illumina）：成本低，读长短，通量高且拼装的原理是基于德布鲁因图来拼装的
- 三代PacBio，Nanopore：成本高，读长超长，通量高，基于overlap拼接
通常来说拼接顺序如下：
- reads：为我们测序的读段reads
- contig：片段重叠群，指拼接软件基于短序列之间的重叠区（overlap），拼接获得的较长序列。
- 片段框架，由先后顺序已知的Contigs组成的序列，中间有Gap。基因组de novo测序中，通过reads拼接获得Contigs后，往往还需要构建454 Paired end库或Illumina Matepair库，以获得一定大小片段（如3Kb、6Kb、10Kb、20Kb）两端的序列。基于这些序列，可以确定一些Contig之间的顺序关系，这些先后顺序已知的Contigs组成Scaffold。
- N50：Reads拼接后会获得一些不同长度的Contigs。将所有的Contigs长度相加，获得Contig总长度。然后将所有的Contigs按照从长到短进行排序，如获得Contig1，Contig2，Contig3…Contig25。将Contigs按照这个顺序依次相加，当相加的长度达到Contig总长度的一半时，最后一个加上的Contig长度即为Contig N50，可以作为基因组拼接的结果好坏的一个判断标准。此概念很容易被误认为所有Contigs长度排名第50的序列长度，与之类似的有N90，N50与N90同样适用于Scaffolds。
测序拼接的主要过程就是把reads分组为重叠群(contigs)，把重叠群分组为支架( scaffolds)。重叠群以reads 进行多重排列，并且形成共同序列，而支架( 即超级重叠群或巨型重叠群)规定了重叠群的顺序和方向以及重叠群之间缺口的大小。
两种算法：
- overlap–layout–consensus (OLC)
- de-bruijn-graph (DBG)
一、OLC
Over lap Layout Consensus
OLC generally works in three steps: first overlaps (O) among all the reads are found, then it carries out a layout (L) of all the reads and overlaps information on a graph and finally the consensus (C) sequence is inferred 它是intuitionistic assembly algorithm，由Staden (1980)发明，主要用于长的低丰度序列的拼接，特别是一代数据，常见的软件有Arachne[6], Celera Assembler [7], CAP3 [8], PCAP [9],Phrap [10], Phusion [11] and Newbler [12].
基于OLC算法的拼接，基本原理如下： 首先找到reads与reads之间的overlap区域，然后根据这些overlap区域拼接出scaffolds，最后基于这些scaffold的关系确定先后顺序，完成拼接
二、DBG
DBG是anti-intuition algorithm，它是首先将reads分割为更短的k-mers,然后来构图。1995 by Ramana M.Idury and Michael S. Waterman. 适合搞丰度的短的序列的拼接。相应的软件有Euler-USR [15],Velvet [16], ABySS [17], AllPath-LG [18] ，SOAPdenovo [19] 【22，23】对这种算法提出了质疑，而【18，19】认为这种算法还是有较高的可信度的。争议一直存在，但软件的改进也没有停止过。
图A是OLC，图B是DBG，假设我们获得的reads是20bp.图A中，我们生成6个片段，每个片段长度(L)是10bp,至少重叠长度（O）为5bp,然后各个片段建立OLC图。图B的k-mers为5，建立DBG图。 拼接软件拼接结果的好坏
重复区域拼接效果很差。。
这个方法主要基于图论里面的德布鲁因图来完成拼接的
比方说以读段AGATACT为例，那么3-mer（k=3）构成的德布鲁因图如上，每个3-mer前后错位1个碱基，依次排列开。 那么对于两条读段来说，首先找到两条序列重叠的部分，发现它们之间仅一个碱基不同，根据德布鲁因图，发现它们其中三个k-mer会有所不同，并形成一个小包
那么小包外的部分就确定为我们的基因组的一部分了 对于10个读段来说：
对于不同的k-mer，会隆起一个小包，那么小包外的部分即可以确定为基因组的一部分，对于小包来说，根据更多的读段，在进行打分，从而选择最优的那条路径
目前二代组装常用的软件有：
- OLC：Canu，Celera Assembler，Falcon等
- DBG：SOAPdenovo2，SPAdes，ALLPath-LG，Velvet等
三、三代数据组装基因组
三代数据读长较长，需要30X以上的深度 它的拼接基本想法和二代的OLC比较类似，先寻找测序reads之间的overlap关系，把它们拼接成Contig，然后根据图论的方法，解出最优路径，然后对Contig进行矫正，从而拿到一致性序列
只不过较二代数据来说，由于三代读长较长，所以基于长reads拼接较为准确直观
目前三代拼接的软件有：
- CANU
- WTDBG2
四、遗传图谱挂载染色体
一般来说，无论是二代还是三代数据，按照上面两节介绍的技术来组装，只能组装到scaffolds的水平，接下来拼接到染色体水平，需要利用HI-C来做染色体挂载
Hi-C建库
Hi-C建库原理是，在同一条染色体上的DNA片段因为空间距离更近，所以更容易被蛋白交联在一起。所以Hi-C测的是被蛋白交联的DNA片段，所以这样组装就可以将这些Contig依据染色体进行分组
像热图红色部分即为染色体分组 目前染色体挂载常用的软件有：ALLHIC，3d-DNA，LACHESIS，SALSA2
五、讨论
一般使用重叠群和支 架的尺寸大小和精确度进行评判，拼接结果尺寸通 常以最大contig长度、contig平均长度、全部contig 总全长和N50 值等统计数据表示。作为评判拼接 结果好坏的另一指标———精确度，一般情况下则很 难准确衡量。
参考资料：
- 文献：Comparison of the two major classes of assembly algorithms: overlap layout consensus and de-bruijn-graph
- 文献：四种常用高通量测序拼接软件的应用比较
- 山东大学 基础医学院 生物信息学课题组荣誉出品 http://www.crc.sdu.edu.cn/bioinfo
- https://www.jianshu.com/p/031de137bf38
