目前为止，从头拼接常用的算法主要有两种，分别是OLC（overlap-layout-consensus）和DBG（deBruijn graph）。
1.OLC算法
这种算法比较适用于较长的测序片段的拼接，广泛应用于第一代测序，因为三代测序的read也比较长，所以目前在三代测序中也开始有了新的应用。
OLC算法还比较好理解，首先需要了解几个概念：
reads：测序产生的片段，一代测序大概在500-1000bp左右，二代测序是几十到几百bp左右，三代测序10-50kb。
contigs：就是由reads通过重叠序列叠加形成的更长的片段，也称为重叠群。
scaffolds：需要构建paired-end或者mate-pair库，主要是将contigs进行排序，确定方向和顺序，并且需要补足contigs叠加中产生的缺口。
主要可以分为三个步骤：
（1）对所有的reads进行两两比较，找到相互重叠的reads。当然两条reads之间的重叠区域需要＞阈值（cutoff value）。这个方法跟早期的贪婪算法有点区别。贪婪算法是先找到一条reads，然后找到与它重叠区域最多的序列拼接，依次。这样找到的拼接是局部最优解，当遇到重复序列的时候会遇到很大的问题。但是OLC算法是找到所有的overlap。
（2）构建reads的重叠区域图，将reads拼接成contigs。
（3）在不同的contigs中找到一条最优的拼接路径，确定contigs的排序和方向，形成scaffolds。
OLC在layout中确定拼接顺序基于hamiltonian path，涉及到了图论的内容，在这里简要介绍一下。
图论G中包括了点和边两个元素，点在这边就是表示reads，边表示的reads间存在重叠序列。hamiltonian path算法是将每个顶点都访问一遍。如下图中的G1无法将所有顶点都过一遍，不属于hamiltonian path，同理G2包含了v1v2v3v4路径，G3不仅包含hamiltonian path，还形成了闭合的环路，称其含有Hamiltonian cycle。
OLC算法常用的软件有Canu，MECAT，NECAT，NextDenovo。
2.DBG算法
OLC算法主要是针对一代和三代测序中读长较长的片段，对于二代测序中长度为100-150bp的序列而言，因其信息过于碎片化， 包含的信息少，需要另外对算法进行优化。
在介绍DBG的操作流程前，先来了解一下德布鲁因序列。
德布鲁因序列B（k，n）是指所有长度为n的k元素构成的循环序列。如上图展示的二进制序列00010111，属于B（2，3）序列。也就是是由2个元素，0和1，所有长度为3的组合构成的。如上图，可以直观看到德布鲁因图就是有节点和边构成的有向图，每个节点的元素都在最右端错开一个。对于原始的序列，可以通过构建n维的德布鲁因图的hamiltonian path或者n-1维的Eulerian Path来确定。不同于之前提到的hamiltonian path，Eulerian Path是要经历图中的每一条边而非顶点。上图就能用来构建B（2，4）序列。沿着000，000，001，011，111，111，110，101，011，110...的路径往下走，可以得到k为4的序列
0000
-0001
--0011
---0111
----1111
-----1110
....
可以得到0000111101100101000的序列。
同样的，当对碱基序列进行拼接时，也是得到很多这样的短序列。这些短序列就是上次提到的将每个read打断成k-mers。
DBG的步骤主要包括了：
（1）构建不同k-mers，k-mer的取法详见上篇2021-09-23 k-mer相关 - 简书 (jianshu.com)
（2）按照Eulerian Path将不同的k-mer拼接成contig
比如有两条read
read1:ACTAGCTA
read2:CTAGAA
取k=3
read1:ACT,CTA,TAG,AGC,GCT,CTA
read2:CTA,TAG,AGA,GAA
最后的路径就是
ACT-CTA-TAG-AGC-GCT-CTA-TAG-AGA-GAA
得到拼接序列ACTAGCTAGAA
（3）真实的情况比这个还要复杂很多，而且会遇到测序错误或者SNP等问题，需要进一步对德布鲁因图简化。
一般这些需要简化的情况包括了：去除分支和低覆盖率连接；去除微小重复；合并小包
这种情况主要是由于测序误差产生，直接删除低频k-mer即可。
如果存在一些重复，将这些重复拆开，使得出入度的节点都为1。
有些序列存在SNP，使得2个k-mer的序列非常相似，产生小鼓包，将其合并。
（4）如果此时还有一些分支点无法知道其连接，拆开，得到contig，按照contig的重叠群确定其拼接顺序。
（5）构建scaffolds，这个过程和OLC类似，也需要确定两端序列信息，补足contigs之间的gap。
常用的软件包括了Velvet，华大基因开发的SOAP（short oligonucleotide package）等等。
参考：
Eulerian and Hamiltonian Graphs (studylib.net)
二代测序数据拼接之原理篇 - 云+社区 - 腾讯云 (tencent.com)
德布鲁因图和OLC组装基因组 - 简书 (jianshu.com)
https://www.jianshu.com/p/818549208063
