基本概念
- k-mer指的是bai将一条read，连du续切割，挨个碱基划动得到zhi的一序dao列长度为K的核苷酸序列
- contig表示从大规模测序得到的短读(reads)中找到的一致性序列
- 来确定一些Contig之间的顺序关系,这些先后顺序已知的Contigs组成Scaffold
Scaffold上可能有若干个Contig，中间有模糊序列相连接成Scaffold
德布鲁因图
所谓德布鲁因图就是有节点和边构成的有向图，其要求是相邻两个节点的元素错开一个碱基，例如第一个ATGCC和第二个TGCCA出了第一个和最后一个元素以外，都能完全匹配；由于测序错误或者其他原因，会有少数reads测错，所以会有上图存在的分叉路径存在，但由于匹配到的reads比较少，所以可以忽略
德布鲁因图是将你测序所得到的reads以kmer方式排列，如果几条reads之间有overlap，那么就很容易拼接成一个比较长的Contig，如上图所示最佳Contig序列为：ATGCCAATG，紫色为测错reads
那么将我们的reads转换为德布鲁因图的时候需要注意，图的节点代表k-mer，边代表欧拉行走的路径（欧拉行走指的是每一条边仅遍历一次）
假设说我有两个序列需要根据德布鲁因图拼接为Contig：
序列：
那么这两条reads的k-mer（k=3）分别为：
read1：ACT, CTA, TAG, GCT, CTA
read2：CTA, TAG, AGA, GAA
德布鲁因图：
每一条边遍历一次，两条边代表遍历两次，那么各个节点连接起来为：
ACT-CTA-TAG-GCT-CTA-TAG-GCT，Contig为：ACTAGCCTAGAA
但是实际情况远比这个复杂：
当有很多reads时，我们将会得到很多路径，那么我们需要将模型简化
大致有以上a，b，c，d这几种情况，黑色表示reads较多的路径，红色代表较少的路径，那么我们往往忽略较少reads的，而保留主干路径，由主干路径组装成Contig
OLC
OLC是: Overlap-Layout-Consensus的简写，首先构建重叠图，然后将重叠图收束成Contig，然后每一个Contig选择最有可能的核苷酸序列
重叠图的意思是对于一些序列，前后有若干个碱基是一样的（如上图所示），我们将其称之为重叠图
那么实际上我们测序的reads类似于上图的a，b，c片段：
而多个reads（片段）就可以构成重叠图，如上图所示，每个节点相当于一条read，有一种组长方法是基于SAS：Shortest common superstring
就是组装出最短的Contig序列，使得所有的reads都是该序列的子集
而寻找SCS的算法多采用贪心算法实现，例如下图所示：
最后确定相同位置的Contig，矫正碱基情况：
参考：ppt
网友评论