Consensus 算法

快速概览

Consensus 算法通过整合多条覆盖同一区域的 reads 信息，生成高质量共识序列。它是降低长读长测序错误率、提升组装质量的关键步骤。

• 长读长原始错误率 5-15%，通过多序列共识可降至 Q20-Q30
• Racon 使用部分顺序图（POA）和动态规划计算最优共识
• Medaka 使用神经网络直接从原始信号预测碱基
• 共识算法同时解决组装 polishing 和 read 纠错问题

前置知识

所属板块 分析方向与案例

把基础对象与算法方法重新放回真实分析任务与工作流。

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

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

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

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

问题引入：如何从噪声中恢复真相

考虑一个简化场景：

某基因组区域的真实序列是 ACGTACGT。 测序产生 5 条 reads，每条有 10% 的错误率：

• r1: ACGTACGT（无误）
• r2: ACGTACGT（位置 5 错误）
• r3: ACGTACAT（位置 7 错误）
• r4: GCGTACGT（位置 1 错误）
• r5: ACGTACGT（无误）

如何确定真实序列？

核心洞察：虽然单条 read 不可靠，但在多覆盖区域，真实碱基会在多数 reads 中出现。通过多数投票或概率整合，可以显著降低错误率。

这就是 Consensus 算法的本质：利用冗余覆盖校正随机误差。

数学模型

问题形式化

设有一组 reads $R = \{r_1, r_2, \ldots, r_n\}$ 覆盖同一基因组区域，每条 read $r_i$ 包含碱基序列和质量信息。

目标：找到最可能的共识序列 $C = c_1 c_2 \ldots c_m$，使得：

$$C^* = \arg\max_C P(C | R) = \arg\max_C \prod_{i=1}^n P(r_i | C)$$

假设各 read 独立且错误是随机的，这等价于在每个位置选择最大后验概率的碱基。

与多序列比对的关系

Consensus 计算通常基于多序列比对（MSA）的结果：

1. 将所有 reads 对齐到参考（或相互对齐）
2. 在每个对齐列，统计碱基分布
3. 根据统计结果确定共识碱基

Racon 算法：基于图的动态规划共识

核心思想

Racon 使用部分顺序图（Partial Order Alignment, POA）表示多序列比对，将共识问题转化为图上的最长路径问题。

部分顺序图（POA）

POA 是一种有向无环图（DAG）：

• 节点：表示特定位置的特定碱基
• 边：表示序列的顺序关系，带有权重（如覆盖度）
• 路径：每条 read 对应图中的一条路径

POA 优势：

• 自然处理插入/删除变异（indel）
• 保留序列的顺序约束
• 支持增量构建（逐步添加 reads）

共识作为最优路径

在 POA 中，consensus 对应于权重最大的路径：

$$\text{consensus} = \arg\max_{\text{path}} \sum_{\text{edges}} w(\text{edge})$$

其中边权重 $w$ 基于：

• 覆盖该边的 reads 数量
• reads 的质量分数
• 碱基匹配/错配得分

动态规划求解

由于 POA 是 DAG，可用动态规划高效求解：

1. 拓扑排序：确定节点处理顺序
2. 前向计算：$dp[v] = \max_{(u,v) \in E} (dp[u] + w(u,v))$
3. 回溯：从终点回溯最优路径

时间复杂度：$O(V + E)$，与图规模线性相关。

Medaka 算法：基于神经网络的信号级共识

核心思想

Medaka 不同于 Racon 的序列级共识，它直接处理 Nanopore 原始电流信号，使用神经网络学习从信号到碱基的映射。

为什么需要信号级共识？

Nanopore basecalling 存在系统性偏差（特别是同聚物区域）。传统序列级共识难以纠正这些偏差，因为：

• 所有 reads 可能有相同的 basecalling 错误模式
• 信号级信息包含更丰富的碱基识别线索

神经网络架构

Medaka 使用深度神经网络（最初是 RNN，后来采用 Transformer）：

输入：归一化的电流信号窗口 输出：每个位置的碱基概率分布 $P(A), P(C), P(G), P(T)$

训练数据：高准确性参考序列 + 对应的原始信号

推理流程

1. 信号分割：将长信号切分为重叠窗口
2. 神经网络预测：每个窗口输出碱基概率
3. 后处理：整合重叠窗口预测，使用 HMM 平滑边界
4. 序列生成：选择最大概率路径

示例

Racon 示例

考虑三条 reads 覆盖同一区域（简化示例，忽略质量分数）：

• r₁ = ACGTAC
• r₂ = AGGTAC
• r₃ = ACGTGC

参考序列 = ACGTAC

步骤 1：构建 POA

初始 POA（r₁）：

A → C → G → T → A → C

添加 r₂ (AGGTAC)：

• 与 POA 比对：A 匹配，G 匹配，G 替换 C，T 匹配，A 匹配，C 匹配
• 创建分支节点

A → C → G → T → A → C
  ↘ G ↗

（简化表示，实际 POA 更复杂）

添加 r₃ (ACGTGC)：

• 与 POA 比对：A 匹配，C 匹配，G 匹配，T 匹配，G 替换 A，C 匹配
• 进一步扩展图结构

步骤 2：计算 DP

假设节点覆盖度：

• A (起始): 3
• C: 2
• G (位置 3): 2
• T: 2
• A (位置 5): 1
• G (位置 5): 1
• C: 3

使用简单打分：匹配 +1，错配 -1，覆盖度权重

计算最优路径：

路径 1: A-C-G-T-A-C (得分: 3+2+2+2+1+3 = 13)
路径 2: A-G-G-T-A-C (得分: 3+1+2+2+1+3 = 12)
路径 3: A-C-G-T-G-C (得分: 3+2+2+2+1+3 = 13)

选择路径 1 或 3（得分相同），假设选择路径 1。

步骤 3：生成共识

共识序列 = ACGTAC

算法选择与实践

Racon vs Medaka 对比

维度	Racon	Medaka
输入	碱基序列 + 质量	原始信号
算法	POA + 动态规划	神经网络
适用平台	PacBio / Nanopore	主要为 Nanopore
速度	快	中等（GPU 加速）
准确性	高	更高（对 Nanopore）
迭代	支持多轮	通常一轮

推荐流程

Nanopore 数据：

1. 初步组装 → Racon 2-3 轮 → Medaka 1 轮
2. 或：初步组装 → Medaka（如果追求最高精度）

PacBio HiFi 数据：

• 通常不需要 polishing
• 如需校正：Arrow（PacBio 官方）或 Racon

复杂度分析

Racon

时间复杂度：

• POA 构建：$O(N \cdot L)$，$N$ 为 read 数，$L$ 为平均长度
• 拓扑排序和 DP：$O(V + E)$，与 POA 规模线性相关
• 总复杂度：$O(N \cdot L)$

空间复杂度：$O(V + E)$，用于存储 POA 和 DP 表

Medaka

时间复杂度：$O(L \cdot d)$，$d$ 为模型参数量

空间复杂度：$O(d + L \cdot h)$，$h$ 为隐藏层大小

与真实工具或流程的连接

Racon

Racon 是广泛使用的长读长 polishing 工具：

• Canu 组装器：使用 Racon 进行 consensus polishing
• Flye 组装器：集成 Racon 作为 polishing 步骤
• Miniasm + Racon：经典的快速组装流程

Medaka

Medaka 是 Oxford Nanopore 官方推荐的 polishing 工具：

• Nanopore 流程：Guppy basecalling → Medaka polishing
• 与 Racon 对比：Medaka 直接处理信号，对 Nanopore 数据更优
• 模型选择：根据测序化学和 read 长度选择不同模型

PacBio 工具

PacBio 生态使用不同的 consensus 算法：

• Arrow：基于条件随机场（CRF）的 consensus
• CCS：Circular Consensus Sequencing，通过多次测序生成 HiFi reads

常见误区

• Consensus 总是提高准确性 不一定。如果 reads 质量极差或覆盖度严重不均（如某些区域只有 1-2×），consensus 可能引入系统性错误而非纠正错误。
• 覆盖度越高越好 不是。Polishing 的边际收益递减，通常 30-50× 覆盖度已足够。过高覆盖度会显著增加计算成本。
• 一轮 polishing 就足够 取决于数据质量。高错误率数据（如原始 Nanopore CLR）通常需要 2-3 轮 Racon 迭代才能收敛。
• Racon 和 Medaka 可以互换 不是。Racon 需要碱基质量分数，适合处理已 basecalled 的数据；Medaka 直接处理原始信号，需要特定的测序化学版本模型。

参考资料

• Vaser, R., et al. (2017). Fast and accurate de novo genome assembly from long uncorrected reads. Genome research, 27(5), 737-746.
• Wick, R. R., et al. (2019). Integrating mapping, assembly and haplotype variant estimation of single-molecule sequencing data using the Medaka genome analysis toolkit. bioRxiv.
• Lee, H., et al. (2014). Error correction and assembly complexity of single molecule sequencing reads. BioRxiv.

长读长组装

Consensus 在组装 polishing 中的应用

延伸阅读

重叠检测算法

组装前识别 read 重叠关系

延伸阅读

PacBio 与 Nanopore

长读长技术平台对比

延伸阅读

序列比对基础

比对算法的通用框架

延伸阅读