经典：基因组测序数据从头拼接或组装算法的原理
疫情防控安全基因组测序数据的拼接/组装 （图⽚来源：google）
从头拼接每⼀个物种的参考基因组序列（reference genome）的产⽣都要先通过测序的⽅法，获得基因组的测序读段（reads），然后再进⾏从头拼接或组装（英⽂名称为do novo genome asmbly）
genome asmbly），最后还原测序物种的各条染⾊体的序列，即ATGC四种碱基的排列顺序。
之所以要进⾏基因组拼接，是因为现在的测序技术还只能测较短的序列，⽆法直接获取⼀整条染⾊体的序列。如⼀代测序（Sanger测序）之所以要进⾏基因组拼接，是因为现在的测序技术还只能测较短的序列，⽆法直接获取⼀整条染⾊体的序列
⼀般可测1kb左右的序列；⼆代测序（next-generation quencing），⼀般可测50~500bp；三代测序虽然可测100kb甚⾄更长的序列，但现在三代测序技术还不是很成熟，还有较⾼的测序错误率。（欢迎关注微信公众号：AIPuFuBio，和使⽤⽣物信息学平台AIPuFu：
）
基因组测序数据的从头组装过程，可简单描述为：reads---->contig---->scaffold---->chromosome
reads---->contig---->scaffold---->chromosome，具体如下所⽰：
基因组序列从头组装⽰意图（图⽚来源：Guo et al. Genomics, 2017）
⾸先基因组测序产⽣reads，然后对reads进⾏组装产⽣长⽚段Contigs，再确定Contig的⽅向和顺序，组装产⽣更长的⽚段Scaffolds，最后再组装连接Scaffold得到完整的染⾊体序列。
苍云
：contig和scaffold。
接下来，给⼤家依次介绍⼀下上图从头拼接中涉及到的两个概念：contig和scaffold
Contig是由多个reads通过组装⽽形成的长⽚段。由于测序读段较短、基因组序列通常含有较多重复序列、⽽且还有测序错误等原因，除了Contig是由多个reads通过组装⽽形成的长⽚段。
简单的基因组序列外，⼤部分物种的基因组序列组装都会先产⽣很多contig，⽆法⼀次获得完整的染⾊体序列。
Scaffold为多条contig序列连接形成更长⽚段，这些contig⽅向和顺序已经确定，且contig间未知序列（⼀般⽤NNNN表⽰）的长度也获知。
人参苗Scaffold的获得⼀般主要通过双端测序（如paired-end quecing或mate-pair quencing）来确定contig的顺序和⽅向，以及contig之间的间隔距离，具体如下⽰意图所⽰。花
由reads组装产⽣contig，再由contig连接形成scaffold的⽰意图 （图⽚来源：google）
从头组装的核⼼算法主要可以分为以下⼏⼤类：
有趣的网名基因组测序数据的从头组装的核⼼算法主要可以分为以下⼏⼤类：
关羽传1、基于贪⼼算法（greedy-extention）；
2、基于Overlap-Layout-Connsus（OLC）；
3、基于de Bruijn Graph；
4、以上两种或多种算法的组合；
5、其他类型。
具体如下图所⽰：
读后感格式基因组从头组装算法分类及代表性软件发表的时间（图⽚来源：Zhanget al. PlosOne, 2011）
其中最经典的两类为：
1）Overlap-Layout-Connsus（OLC）算法，基于OLC算法的组装软件主要是针对长测序读段（如Sanger测序、454测序等）设计1）Overlap-Layout-Connsus（OLC）算法
常绿小乔木的；
2）de Bruijn Graph算法，基于de Bruijn Graph的组装软件则主要是针对⼆代测序产⽣的短读段数据设计。
2）de Bruijn Graph算法
具体如下所⽰：
1）Overlap-Layout-Connsus（OLC）算法
Overlap-Layout-Connsus（OLC）算法的⽰意图（图⽚来源：Ayling et al. Briefings in Bioinformatics, 2019）2）de Bruijn Graph算法
de Bruijn Graph算法的⽰意图（图⽚来源：Ayling et al. Briefings in Bioinformatics, 2019）
现在主流的是⼆代测序技术，因此再给⼤家详细介绍⼀下专门针对⼆代测序数据开发的基于de Bruijn Graph的从头拼接⽅法。
Velvet，是基于de Bruijn Graph设计的经典代表，其算法⽰意图如下：
其中⼀个⾮常著名的软件就是Velvet
Velvet从头组装软件的算法设计⽰意图（ 图⽚来源：Zerbinoet al. 2008, Genome Rearch）
其中红⾊碱基为测序错误或SNP位点。
Velvet的组装原理，主要可分为这⼏个步骤：
1）⾸先把所有测序读段（reads）都分割为更⼩的⽚段k-mer；
Reads产⽣k-mer的过程⽰意图。这⾥k为7，假如read的长度为n，则总共可产⽣n-1个k-mer。
2）把每个k-mer作为⼀个节点，然后判断k-mer之间是否有k-1碱基的重叠，如果有则作为两个不同的节点连接起来。依次这样连接所有可连接的k-mer就形成了Velvet从头组装软件算法设计⽰意图中第2步的de Bruijn Graph；
3）依次合并相邻的k-mer，因为相邻的k-mer有k-1个碱基的重叠，就可进⼀步简化de Bruijn Graph形成Velvet从头组装软件算法设计⽰意图中第3步的简化后的图；
4）使⽤⼀系列算法消除由测序错误⽽形成的tips（具体如Velvet从头组装软件的算法设计⽰意图中所⽰），并合并bubbles（两条或多条路径序列，⼀般由SNP造成，如Velvet从头组装软件的算法设计⽰意图）；
5）最后拼接得到Contig序列。
值得注意的是，Velvet从头组装软件算法设计⽰意图中最后⼀步拼接产⽣了回⽂序列，主要是由于原始序列中含有回⽂，如果k取为偶数（图中
k=4）就容易在组装中形成这种现象。
