转录组拼接原理

转录组拼接是一个由长变短再由短边长的过程

拼接过程

1. 从reads到contigs : 进行多序列比对并将一致的reads拼接起来来生成contigs，是拼接过程
2. 从contigs到scaffolds : 通过pair end reads信息来判断contigs的顺序、方向和相邻contigs之间的gap大小来生成，是一个排序和定向的过程

拼接算法基本原理

目前几乎所有的拼接算法都是基于图论思想（Graph theory）,其中图论中的两个点表示两个read，而两点之间的连线表示两条read的重叠区域，拼接要做的事情就是在所有的路线中找最优解。

图片.png
图片.png

常用拼接算法

• 1. Greedy extension

贪婪算法（贪心图）。首先选定初始read, 然后找和其重叠区域最高的read进行延伸，直到拼接后的read两端都不能再进行扩展为止。
每一次都是从最优匹配开始，然后次优匹配，到不能匹配时停止。这样一来，贪婪算法通常会得到局部最优解，而不是全局最优解。因此，这种算法在遇到重复序列时会出现比较大的问题。

• 2. Overlap Layout Consensus

OLC图算法主要是用来针对长reads序列拼接，就是把测序产生的长序列用彼此之间的overlap区域连接起来。
主要步骤如下：

• 2.1 Overlap

对所有reads计算任意两条之间的重叠区域，挑选出满足筛选条件的reads。这里区别与贪婪算法，会先把所有overlap都找到。这一步，通常会将一个reads分成若干个长度比较短的序列（kmer/seed/word），要求是每个片段序列之间至少有若干个碱基的重叠区域。

• 2.2 layout garph

简单化过程。对reads进行排序，确定reads之间的位置，建立overlap图，将重叠的reads组合成contig。

• 2.3 Consensus

在已经建好overlap图的基础上，将所有的read序列排列起来，找一条从起始节点到终止节点的最佳近似路径使得最终路径将会遍历一次重叠区域中的每个节点，相当于对初始的reads集合中全部序列进行重构得到目标基因序列。

• 3. De Bruijn Graph

De Bruijn Graph是目前最常用的二代测序拼接算法。比较流行的拼接软件如Velvet、Abyss和SOAP denovo都使用该算法。
与OLC不同之处在于，这个算法将已经非常短的reads再分割成更多个kmer短序列（k 小于reads 序列的长度），相邻的kmers序列通过（k-1）个碱基连接到一起（即每次只移动一个位置），进而降低算法计算重叠区域的复杂度，降低内存消耗。
这里的kmer首先不能太短，比如2个碱基肯定拼不出来基因组，它的长度既需要能够使其携带足够的基因组的信息，也要短到可以进行后续的错误矫正。除此之外，一个read中小的片段被分割之后还不会丢失原来reads 的前后位置信息。
总体而言，该算法将reads打断成长度为K的核酸片段，再用Kmer间的overlap关系构建DBG，最后通过DBG得到基因组序列。
主要步骤如下：

• 3.1 将read分割为一系列连续kmer，构建DBG图
• 3.2 合并DBG图

合并路径中出度入度唯一（one incoming and one outcoming ）的节点，去除段末端，低覆盖度节点和泡状结构。

• 3.3 构建contig

寻找最优路径（经过每个节点且仅经过一次），最优路径对应的碱基序列构成一个contig

• 3.4 构建scaffold

通过PE reads 位置信息确定contig之间的相对位置和方向，组装contig，填充contig之间的gap，得到scaffold序列。