OLC：Overlap-Layout-Consensus

快速概览

OLC 是经典的三阶段组装范式：先找 reads 之间的重叠关系，再构建布局确定相对位置，最后综合多条 read 的信息生成共识序列。

Overlap：快速筛选并精确计算 read 之间的重叠
Layout：将重叠关系组织成图或路径，推断顺序和方向
Consensus：利用冗余覆盖纠正错误，输出稳定序列
长读长时代，OLC 思路因重叠信息更丰富而重新受到重视

所属板块 核心方法

索引、比对、组装与概率模型构成的核心算法主轴。

阅读目标 帮助建立阅读上下文

先判断这页与你当前问题的关系，再决定是否深入展开。

建议前置 先建立相关基础对象与方法直觉

建议先建立相关基础对象与方法直觉，再进入本页。

是什么

OLC（Overlap-Layout-Consensus）是一类经典组装思路，它把序列重建问题拆成三个阶段：

Overlap：寻找 reads 之间的重叠关系；
Layout：根据重叠关系构建布局；
Consensus：从布局中求共识序列。

和 de Bruijn graph 相比，OLC 更强调”read 与 read 之间的真实重叠”，而不是先分解成 k-mer 再建图。

为什么重要

组装的核心问题始终是：如何从局部观测恢复整体序列。

在 OLC 框架中，我们假设：

如果两条 read 有足够可靠的重叠，它们就可能来自原始序列上的相邻区域；
把许多这样的重叠关系拼接起来，就有机会恢复更长的序列骨架；
最后再用多条 read 的信息求出更稳健的共识序列。

长读长时代让这套思路重新变得非常重要，因为长读长之间的重叠信息更丰富，更有机会跨过重复区域并提供稳定布局线索。

核心流程

OLC 组装流程示意图 — OLC 组装的三个核心阶段：重叠检测、布局构建与一致性序列生成。

1. Overlap (重叠检测)

目标是找出哪些 reads 之间存在显著重叠。

这一阶段最直接，但往往也是最贵的，因为潜在 read 对数目很大。要解决的问题包括：

如何快速筛掉不可能重叠的 read 对；
如何区分真实重叠与重复/错误造成的假重叠；
如何给重叠边打分。

2. Layout (布局图构建)

得到重叠关系后，可以把 reads 组织成图或路径结构，尝试推断它们在原始序列上的相对顺序和方向。

这一阶段最容易遇到的麻烦是：

重复区域造成歧义；
某些 read 质量差，使布局不稳定；
图中存在多个看似合理的延伸方向。

3. Consensus (共识序列生成)

即使 layout 大体正确，read 本身也可能有错误。因此最后还需要把多条重叠 read 综合起来，得到更可靠的 consensus sequence。

这一步强调的是”用冗余覆盖纠正单条 read 的错误”。

示例

假设有三条 read：

R1: ACGTAC
R2:   GTACGA
R3:      ACGATT

如果发现：

R1 与 R2 在 GTAC 上有高质量重叠；
R2 与 R3 在 ACGA 上有高质量重叠；

那么 layout 阶段就可能推断它们沿同一条更长序列排列。最后 consensus 阶段再综合覆盖信息，输出更稳定的结果。

与真实工具或流程的连接

OLC 不是单一算法，而是一整类设计范式。它的思想在很多长读长组装和共识构建流程中都能看到：

先找重叠；
再构布局；
最后做共识纠错。

与 de Bruijn graph 相比，可以粗略理解为：

思路	更关注什么	常见优势	常见挑战
OLC	read-read overlap	长读长信息利用更直接	overlap 搜索昂贵
de Bruijn graph	k-mer 图结构	短读长场景更高效	对错误和重复非常敏感

因此，它们并不是简单的”新旧替代关系”，而更像不同数据条件下的不同建模选择。

算法细节

Overlap 计算算法

基于动态规划的重叠检测

给定两条 read $r_1$ 和 $r_2$ ，目标是找到它们之间的最大重叠。这可以形式化为序列对齐问题。

算法 1：后缀-前缀最长公共子串

输入：read r₁, read r₂，最小重叠长度 L_min
输出：最大重叠长度和重叠位置

1. 构造后缀数组 SA₁ 包含 r₁ 的所有后缀
2. 构造前缀数组 PA₂ 包含 r₂ 的所有前缀
3. 对于每个后缀 s ∈ SA₁：
   a. 如果 |s| < L_min，跳过
   b. 在 PA₂ 中二分搜索与 s 匹配的最长前缀
   c. 记录匹配长度
4. 返回最大匹配长度及其位置

时间复杂度： $O(n \log n)$ ，其中 $n$ 为 read 长度（使用后缀数组）

空间复杂度： $O(n)$

基于 k-mer 的快速筛选

为了避免对所有 read 对进行昂贵的对齐计算，先使用 k-mer 进行快速筛选：

算法 2：k-mer 索引筛选

输入：read 集合 R，k-mer 长度 k，最小共享 k-mer 数 t
输出：候选重叠对集合 C

1. 构建倒排索引 I：k-mer → {read ids}
2. 对于每个 read r ∈ R：
   a. 提取 r 的所有 k-mer 集合 K_r
   b. 对于每个 k-mer k' ∈ K_r：
      - 将 r 添加到 I[k']
3. 对于每对 read (r_i, r_j)：
   a. 计算 |K_{r_i} ∩ K_{r_j}|
   b. 如果 |K_{r_i} ∩ K_{r_j}| ≥ t，加入候选集 C
4. 返回 C

时间复杂度： $O(N \cdot L)$ 构建， $O(|C| \cdot L)$ 验证，其中 $N$ 为 read 数量， $L$ 为 read 长度

Layout 构建算法

重叠图构建

将 reads 作为顶点，重叠关系作为边，构建有向图：

定义：重叠图 $G = (V, E)$ ，其中

$V$ ：所有 reads
$E = \{(r_i, r_j, w, o)\}$ ： $r_i$ 与 $r_j$ 有权重为 $w$ 、偏移为 $o$ 的重叠

算法 3：重叠图构建

输入：候选重叠对集合 C
输出：重叠图 G = (V, E)

1. 初始化空图 G
2. 对于每个候选重叠对（r_i, r_j） ∈ C：
   a. 计算精确重叠长度 o 和对齐分数 s
   b. 如果 s ≥ 阈值 S_min：
      - 添加边（r_i, r_j） 到 E
      - 设置边权重 w = s
3. 返回 G

路径寻找算法

在重叠图中寻找 Hamiltonian 路径或近似路径：

算法 4：贪心路径延伸

输入：重叠图 G = (V, E)
输出：路径集合 P

1. P = ∅
2. 标记所有顶点为未访问
3. 当存在未访问顶点时：
   a. 选择未访问且入度最小的顶点 v_start
   b. path = [v_start]
   c. 标记 v_start 为已访问
   d. while 当前顶点 v 有出边：
      - 选择权重最大的边（v, u）
      - 如果 u 未访问：
         * 将 u 加入 path
         * 标记 u 为已访问
         * v = u
      - 否则：break
   e. 将 path 加入 P
4. 返回 P

时间复杂度： $O(|V| + |E|)$ ，假设每次选择出边是常数时间

注意：这是启发式算法，不保证最优解。精确的 Hamiltonian 路径问题是 NP-hard。

Consensus 算法

多序列对齐与一致性

给定 layout 中的重叠 reads，计算 consensus 序列：

算法 5：基于列投票的 Consensus

输入：对齐后的 reads A = {a₁, a₂, ..., a_m}（每行长度为 n）
输出：consensus 序列 c

1. c = ""（空字符串）
2. 对于列 j = 1 到 n：
   a. 统计该列各碱基的计数：count[A, C, G, T, -]
   b. 计算各碱基的频率
   c. 选择频率最高的碱基 b_max
   d. 如果 b_max 的频率 ≥ 阈值 Q_min：
      - c += b_max
     否则：
      - c += 'N'（不确定）
3. 返回 c

时间复杂度： $O(m \cdot n)$ ，其中 $m$ 为 reads 数量， $n$ 为对齐长度

质量加权 Consensus

考虑测序质量分数的改进算法：

算法 6：质量加权 Consensus

输入：对齐后的 reads A，质量分数 Q = {q₁, q₂, ..., q_m}
输出：consensus 序列 c

1. c = ""
2. 对于列 j = 1 到 n：
   a. 对于每个碱基 b ∈ {A, C, G, T}：
      - score[b] = Σ log₁₀(P(b|q))，其中 P(b|q) 是质量分数 q 下碱基 b 的正确概率
   b. 选择 score 最大的碱基 b_max
   c. c += b_max
3. 返回 c

质量分数转换：质量分数 $q$ 通常定义为 $q = -10 \log_{10}(P_{error})$

复杂度总结

阶段	主要算法	时间复杂度	空间复杂度
Overlap	k-mer 筛选 + 动态规划	$O(N \cdot L)$	$O(N \cdot L)$
Layout	图构建 + 贪心路径	O(V+E)	O(V+E)
Consensus	列投票	$O(m \cdot n)$	$O(n)$

其中 $N$ 为总 read 数量， $L$ 为平均 read 长度， $m$ 为局部区域 read 数量， $n$ 为对齐长度。

常见误区

OLC 已经过时，只剩 de Bruijn graph 有意义：
不是。长读长时代 OLC 思路因重叠信息更丰富而重新受到重视。Canu、Flye 等现代组装器都基于 OLC 框架，而非 de Bruijn graph。两种思路各有适用场景。
overlap 找到了，就等于组装完成：
不是。找到 overlap 只是第一步。layout 阶段需要解决重复区域造成的歧义、低质量 read 造成的布局不稳定等问题，这往往比 overlap 检测更困难。
consensus 只是最后的润色步骤：
不是。consensus 阶段承担着错误纠正的关键任务。单条长读长的错误率可达 5-15%，如果没有充分的 consensus 纠错，最终序列质量会很低。Racon、Medaka 等工具就是专门做这一步的。
长读长组装天然不会被重复和错误影响：
不是。长读长虽然能跨过更多重复区域，但高错误率会在 overlap 检测和 layout 阶段引入大量假信号。错误纠正和重复处理仍然是长读长组装的核心挑战。