Minimap2 比对算法

快速概览

Minimap2 是当前最广泛使用的长读长比对工具。其核心 seed-chain-align 框架通过粗定位-链式筛选-精细比对的三阶段策略，将长读长比对从 O(m×n) 降低到近线性复杂度。

• Seeding：通过 minimizer 索引快速定位候选区域，避免全对全扫描
• Chaining：使用动态规划将 seeds 聚类为共线性链，过滤假阳性匹配
• Alignment：在链约束区域内使用带状动态规划进行精确比对
• 三阶段渐进策略平衡了速度、内存和准确性

前置知识

所属板块 分析方向与案例

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

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

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

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

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

问题引入：长序列比对的计算挑战

考虑长读长比对的典型场景：

Read 长度：20 kb 参考基因组：3 Gb（人类基因组） 传统 Smith-Waterman 动态规划复杂度：$O(m \times n) = 6 \times 10^{13}$ 操作

这在计算上是不可行的。我们需要一种方法，在不牺牲准确性的前提下，大幅降低计算复杂度。

核心思想：从降维索引到局部精确比对

Minimap2 的核心洞察是：不需要在整个基因组上进行动态规划，只需在可能匹配的区域进行精确比对。

这引出了三阶段框架：

$$\text{完整比对} = \underbrace{\text{Seeding（粗筛）}}_{\text{找到候选区域}} + \underbrace{\text{Chaining（精筛）}}_{\text{组织候选为链}} + \underbrace{\text{Alignment（精确比对）}}_{\text{局部位点计算}}$$

阶段 1：Seeding - 粗定位

问题：如何在 3 Gb 参考基因组中快速找到 20 kb read 的可能位置？

解决方案：使用 minimizer 索引

• 从 read 中提取代表性 k-mer 子集（minimizers）
• 在预构建的参考索引中查询这些 minimizers
• 每个 minimizer “命中” 指示一个候选匹配位置

这类似于在图书馆中通过关键词索引快速定位相关书籍，而非逐页扫描。

阶段 2：Chaining - 链式组织

问题：单个 minimizer 命中不可靠（可能存在大量假阳性），如何识别真实的比对区域？

核心观察：真实的比对会产生共线性的 minimizer 命中——它们在 read 和参考上的相对顺序一致。

解决方案：使用动态规划将 minimizer 命中聚类为链（chain）

• 每个链代表一个候选比对区域
• 链得分反映匹配质量（覆盖长度、共线性程度）
• 保留高分链，丢弃孤立命中

阶段 3：Alignment - 精确比对

问题：已知 read 大致对应参考的某个区域，如何获得碱基级别的精确比对？

解决方案：在链约束的局部区域内进行带状动态规划

• 限制 DP 计算区域（带状）
• 大幅降低计算量
• 获得精确的插入/缺失和错配位置

数学模型

全局比对问题

设 read $R = r_1 r_2 \ldots r_m$，参考基因组 $G = g_1 g_2 \ldots g_n$。

最优比对定义为：

$$\pi^* = \arg\max_{\pi} \sum_{(i,j) \in \pi} s(r_i, g_j) - \sum_{\text{gaps}} \gamma(gap)$$

其中 $s(\cdot)$ 是匹配/错配得分函数，$\gamma(\cdot)$ 是间隙罚分函数。

直接求解需要 $O(m \times n)$ 时间和空间。

Seed-Chain-Align 分解

Minimap2 将全局问题分解为三个子问题：

$$\pi^* \approx \arg\max_{\text{chain}} \left[ \arg\max_{\text{align in chain}} \left( \sum s - \sum \gamma \right) \right]$$

分解的合理性基于序列连续性假设：真实比对在局部是连续的，可以通过种子链来近似。

Seeding 阶段：降维索引

Minimizer 索引构建

参考基因组预处理：

1. 滑动窗口提取 minimizers（窗口大小 $w$，k-mer 大小 $k$）
2. 构建倒排索引：$\text{minimizer} \rightarrow \{(\text{chrom}, \text{pos})\}$

Read 查询：

1. 提取 read 的 minimizers
2. 索引查询 → 获得候选位置列表
3. 这些位置称为 anchors 或 seeds

Seed 过滤策略

并非所有 seeds 都有效：

• 高频过滤：在参考中出现次数 > $f$ 的 minimizers 通常来自重复区域，丢弃
• 距离约束：相邻 seeds 在 read 和参考上的距离应大致相等
• 密度检查：有效比对区域应有足够的 seed 密度

参数权衡

参数	增大效果	减小效果
k-mer 大小 $k$	特异性↑，假阳性↓	敏感性↑，索引大小↑
窗口大小 $w$	索引更小，速度↑	敏感性↑，种子更多

Chaining 阶段：共线性链构建

问题建模

给定 seeds 集合 $S = \{s_1, s_2, \ldots, s_n\}$，每个 seed $s_i$ 包含：

• read 位置 $x_i$
• 参考位置 $y_i$
• 长度 $l_i$

目标：找到子集 $C \subseteq S$，满足：

1. 单调性：$x_1 < x_2 < \ldots < x_k$ 且 $y_1 < y_2 < \ldots < y_k$
2. 最大化链得分

动态规划求解

定义 $DP[i]$ 为以 seed $i$ 结尾的最优链得分。

递推公式：

$$DP[i] = \max_{j < i, y_j < y_i} \left\{ DP[j] + \alpha \cdot (x_i - x_j - l_j) - \beta \cdot |(y_i - y_j) - (x_i - x_j)| \right\}$$

得分组成：

• 覆盖奖励 $\alpha \cdot (x_i - x_j - l_j)$：奖励 read 上的连续覆盖
• 共线性惩罚 $\beta \cdot |\Delta y - \Delta x|$：惩罚参考与 read 距离不一致（暗示重排或错误）

边界条件：$DP[i] \geq l_i$（单个 seed 的最小得分）

算法特性

• 时间复杂度：$O(n \log n)$ 使用平衡树优化，或 $O(n^2)$ 朴素实现
• 输出：通常保留 top-$k$ 条链作为候选比对区域

Alignment 阶段：带状动态规划

问题简化

链已经确定了 read 在参考上的大致位置和方向。精确比对只需要在局部区域进行。

带状动态规划（Banded DP）：

• 限制 DP 矩阵计算区域为对角线附近带宽 $b$ 的范围
• 假设链的共线性保证了最优路径在此带状区域内
• 复杂度从 $O(m \times n)$ 降低到 $O(m \times b)$

递推公式

在带状区域内使用标准 Needleman-Wunsch：

$$F[i][j] = \max \begin{cases} F[i-1][j-1] + s(r_i, g_j) & \text{匹配/错配} \\ F[i-1][j] + \gamma_{\text{open/extend}} & \text{read gap} \\ F[i][j-1] + \gamma_{\text{open/extend}} & \text{参考 gap} \end{cases}$$

使用 affine gap penalty：

• $g_{\text{open}}$：开启间隙的惩罚
• $g_{\text{extend}}$：延伸间隙的惩罚

特殊模式：Splice-Aware

对于 RNA-seq 数据：

• 允许大 gap（内含子，通常 >50 bp）
• 在 gap 边界检测 GT-AG 剪接信号
• 对符合剪接模式的 gap 给予奖励

示例

简化示例

参考基因组：ACGTACGTACGTACGT（16 bp） Read：CGTACGT（7 bp）

参数：k=3, w=5

步骤 1：Seeding

参考 minimizers（简化）：

• ACG: pos 0, 4, 8, 12
• CGT: pos 1, 5, 9
• GTA: pos 2, 6, 10
• TAC: pos 3, 7, 11

Read minimizers：

• CGTACGT 提取 minimizers：CGT (pos 0), CGT (pos 4)

Seeds：

• Seed 1: read pos 0, ref pos 1
• Seed 2: read pos 0, ref pos 5
• Seed 3: read pos 0, ref pos 9
• Seed 4: read pos 4, ref pos 1
• Seed 5: read pos 4, ref pos 5
• Seed 6: read pos 4, ref pos 9

步骤 2：Chaining

筛选 seeds（假设只保留共线性的）：

• Chain 1: Seed 1 (0→1) → Seed 5 (4→5)

  • Δread = 4, Δref = 4
  • 得分 = 3 + α·4 - β·0 = 3 + 4 = 7

• Chain 2: Seed 2 (0→5) → Seed 6 (4→9)

  • Δread = 4, Δref = 4
  • 得分 = 3 + α·4 - β·0 = 7

选择 Chain 1（得分相同，任选）。

步骤 3：Alignment

比对区域：ref pos 1-5 附近 Read: CGTACGT Ref: CGTACGT（从 pos 1 开始）

带状 DP 比对：

Read:  C G T A C G T
Ref:   C G T A C G T
       | | | | | | |

完美匹配，得分 = 7。

复杂度分析

Seeding

时间复杂度

• 索引构建：O(N)，N 为参考长度
• Read seeding：O(L/w)，L 为 read 长度，w 为窗口大小
• 候选查找：O(m · d)，m 为 seed 数，d 为平均倒排列表长度

总时间复杂度：O(L/w + m · d)

空间复杂度

• 索引存储：O(N/w)

总空间复杂度：O(N/w)

Chaining

时间复杂度

• Seeds 排序：O(m log m)，m 为 seed 数
• DP 计算：O(m²) 或 O(m log m) 使用优化

总时间复杂度：O(m²) 或 O(m log m)

空间复杂度

• DP 表：O(m)

总空间复杂度：O(m)

Alignment

时间复杂度

• 带状 DP：O(b · L)，b 为带宽，L 为比对长度

总时间复杂度：O(b · L)

空间复杂度

• DP 矩阵：O(b · L) 或 O(b) 使用滚动数组

总空间复杂度：O(b · L) 或 O(b)

总体复杂度

对于单条 read：

• 时间：O(L/w + m·d + m² + b·L)
• 空间：O(N/w + m + b·L)

在实际情况中，$m \ll L$，$d \ll N$，因此接近线性。

与真实工具或流程的连接

Minimap2 模式

Minimap2 支持多种模式：

• Map-ont：Oxford Nanopore mapping
• Map-pb：PacBio mapping
• Map-hifi：PacBio HiFi mapping
• Splice：RNA-seq splice-aware mapping
• asm5/asm10/asm20：assembly-to-assembly mapping（不同容错）

应用场景

• SV 检测：Sniffles2 使用 Minimap2 进行 read 比对
• Polishing：Racon 使用 Minimap2 的重叠信息
• 转录本分析：StringTie、FLAIR 等使用 Minimap2 进行 RNA 比对
• 基因组组装：Flye、Canu 等使用 Minimap2 进行 read 比对

参数调优

常用参数：

• -k：k-mer 大小（默认 15）
• -w：窗口大小（默认 10）
• -r：匹配/错配得分
• -A：gap 开启罚分
• -B：gap 延伸罚分

常见误区

• Minimap2 只用于长读长：
• 不是。Minimap2 也支持短读长比对，虽然 BWA-MEM2 在短读长上可能更快。
• Seeding 阶段可以省略：
• 不能。Seeding 是降维的关键，没有 seeding 会导致 O(n²) 的复杂度。
• 带宽越大越好：
• 不是。带宽增加会降低速度，应根据数据质量调整。高质量数据可以用小带宽。

算法优化

SIMD 加速

• 向量化 minimizer 哈希计算
• 并行化 DP 计算

多线程

• 并行处理多条 reads
• 并行计算多条链的 DP

自适应参数

• 根据数据质量自动调整带宽
• 根据覆盖度调整 seed 筛选阈值

索引优化

• 压缩索引存储
• 内存映射索引文件
• 分区索引支持超大基因组

参考资料

• Li, H. (2018). Minimap2: pairwise alignment for nucleotide sequences. Bioinformatics, 34(18), 3094-3100.
• Li, H. (2016). Minimap and miniasm: fast mapping and de novo assembly for noisy long sequences. Bioinformatics, 32(14), 2103-2110.
• Li, H., & Durbin, R. (2009). Fast and accurate short read alignment with Burrows-Wheeler transform. Bioinformatics, 25(14), 1754-1760.

重叠检测算法

Minimap 的核心思想来源

延伸阅读

Consensus 算法

利用比对结果进行序列纠错

延伸阅读

PacBio 与 Nanopore

Minimap2 支持的技术平台

延伸阅读

序列比对基础

比对的通用算法框架

延伸阅读