【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
