【2.0】序列拼接-拼接的两种算法OLC和DBG

测序拼接的主要过程就是把reads分组为重叠群(contigs)，把重叠群分组为支架( scaffolds)。重叠群以reads 进行多重排列，并且形成共同序列，而支架( 即超级重叠群或巨型重叠群)规定了重叠群的顺序和方向以及重叠群之间缺口的大小。

两种算法：

• overlap–layout–consensus (OLC)
• de-bruijn-graph (DBG)

一、OLC

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].

二、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图。 拼接软件拼接结果的好坏

重复区域拼接效果很差。。

三、评价标准

一般使用重叠群和支 架的尺寸大小和精确度进行评判，拼接结果尺寸通 常以最大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