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 的思想可以用一个更简化的理论模型来理解——最短超串问题（Shortest Superstring Problem）：

输入：一组字符串 $s_1, s_2, \ldots, s_n$ （视为测序 reads）；
输出：一个包含所有输入串作为子串、且长度尽可能短的字符串。

定义 $\text{overlap}(s_i, s_j)$ 为 $s_j$ 的最长前缀同时也是 $s_i$ 后缀的长度（如 $\text{overlap}(\text{ABCDEF}, \text{DEFGHI}) = 3$ ）。把每个字符串看作顶点，边权设为 $-\text{overlap}(s_i, s_j)$ ，则"找最大总重叠的排列"等价于旅行商问题（TSP），因此最短超串问题是 NP-完全的，不存在已知的多项式时间精确算法。

实用的近似策略是贪心：反复选取重叠最长的一对字符串合并（重叠部分只保留一次），直到只剩一个串。该贪心算法的近似比被推测为 2，实际表现通常远好于最坏上界。OLC 的 Layout 阶段正是这一思想在真实数据上的扩展——它额外处理测序错误、重复序列和正负链等理论模型忽略的因素。

核心流程

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 阶段引入大量假信号。错误纠正和重复处理仍然是长读长组装的核心挑战。