💡
concept
三、重叠布局共识(OLC)算法
OLC算法更适合长读长数据(PacBio/Nanopore),其工作流程: **(1)Overlap(重叠检测)** 计算所有reads两两之间的重叠关系。对于N条reads,需要O(N²)次比对,计算量巨大。对于长读长数据,通常使用minimap2等快速比对工具进行all-vs-all比对。 **(2)Layout(布局构建)** 根据重叠关系构建布局图(string graph): - 每个r...
📖 定义
OLC算法更适合长读长数据(PacBio/Nanopore),其工作流程:
(1)Overlap(重叠检测)
计算所有reads两两之间的重叠关系。对于N条reads,需要O(N²)次比对,计算量巨大。对于长读长数据,通常使用minimap2等快速比对工具进行all-vs-all比对。
(2)Layout(布局构建)
根据重叠关系构建布局图(string graph):
- 每个read是图中的一个节点
- 如果两个reads有显著重叠,则在它们之间建立边
- 边的方向和长度由重叠的位置和长度确定
- 简化图结构(去除 transitive edges,压缩 unambiguous paths)
(3)Consensus(一致性序列生成)
对布局图中的每个unitig(unambiguous path),将对应的reads进行多序列比对,生成一致性序列作为contig。