全局比对与局部比对

快速概览

序列比对并不只有一种「对齐方式」。根据研究目标的不同，我们需要区分试图对齐全长的全局比对，以及只寻找高分片段的局部比对。这两者的核心区别在于边界条件的设定。

• 掌握 Needleman-Wunsch 算法的全局比对逻辑：从头到尾的强制解释
• 掌握 Smith-Waterman 算法的局部比对逻辑：允许在得分低于 0 时「推倒重来」
• 理解为什么局部比对在寻找保守结构域和 Motif 时更具优势
• 辨析两种比对方式在动态规划矩阵初始化和回溯终点上的不同

前置知识

• 编辑距离
• 打分矩阵与罚分
• 曼哈顿旅游问题

所属板块 核心方法

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

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

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

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

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

1. 是什么

全局比对（Global Alignment）和局部比对（Local Alignment）是序列比对的两大基本范式。全局比对要求两条序列从第一个字符到最后一个字符完全对齐，任何未对齐的端点都必须以 Gap 填充。局部比对则允许比对从序列的任意位置开始、在任意位置结束，只提取得分最高的局部相似片段。

形式化地：

• 全局比对：寻找比对路径 $\pi$ 使得 $\text{Score}(\pi)$ 最大，其中 $\pi$ 覆盖 $X[1..m]$ 和 $Y[1..n]$ 的全部字符。
• 局部比对：寻找 $i_0, j_0, i_1, j_1$ 和子比对 $\pi$ 使得 $\text{Score}(\pi)$ 最大，其中 $\pi$ 只覆盖 $X[i_0..i_1]$ 和 $Y[j_0..j_1]$。

理解这两种范式的选择，是正确使用比对工具的前提。

2. 要解决什么生物信息学问题

全局比对适用场景

全局比对假设两条序列在整体上是同源的（Homologous），即它们来自一个共同的祖先序列。典型应用包括：

• 比较两个近缘物种中同一基因的编码序列。
• 比较同一物种中同一基因的不同等位基因（Allele）。
• 验证基因组组装或转录组拼接的正确性。
• 教学和理解动态规划的基本原理。

局部比对适用场景

局部比对不假设两条序列整体相关，只关注它们之间是否存在高分相似片段。典型应用包括：

• 在大型蛋白质数据库中搜索保守结构域（Domain）。
• 在基因组中定位已知的 Motif 或功能位点。
• 将测序 Reads 比对到参考基因组（Read Mapping）。
• 发现两个功能不同的蛋白质之间共享的催化结构域。

选择的关键判断标准

一个实用的判断准则是：如果两条序列的长度和功能预期相似，使用全局比对；如果它们长度差异大或功能预期不同，使用局部比对。 当不确定时，局部比对通常是更安全的选择——它不会强制将无关区域对齐。

3. 全局比对（Global Alignment）

Needleman-Wunsch 算法是全局比对的基石。它假设两条序列在进化上是整体相关的，因此试图将它们从第一个碱基对齐到最后一个。

输入与输出

• 输入：两条序列 $X = x_1 x_2 \cdots x_m$ 和 $Y = y_1 y_2 \cdots y_n$，以及打分体系（替换矩阵 $s(a,b)$ 和 Gap 罚分 $g$）。
• 输出：一个覆盖两条序列全长、使得总得分最大化的比对，以及该比对的得分。

核心递推

$F(i,j) = \max \begin{cases} F(i-1,j-1) + s(x_i, y_j) \\ F(i-1,j) + g \\ F(i,j-1) + g \end{cases}$

初始条件严格定义为：

$$\begin{aligned} F(0, 0) &= 0 \\ F(i, 0) &= i \cdot g, \quad i = 1, 2, \ldots, m \\ F(0, j) &= j \cdot g, \quad j = 1, 2, \ldots, n \end{aligned}$$

全局比对与局部比对的 DP 矩阵填充过程对比

这意味着如果序列 A 的前 $i$ 个字符要与空串对齐，就必须付出 $i$ 个 Gap 的代价。同理，空串与序列 B 的前 $j$ 个字符对齐，需要 $j$ 个 Gap。

• 回溯终点：强制从右下角 $(n, m)$ 开始，直到左上角 $(0, 0)$。

递推的三个来源

每个单元格 $F(i,j)$ 的值来自三个方向：

1. 对角线 $F(i-1,j-1) + s(x_i, y_j)$：$x_i$ 与 $y_j$ 对齐（匹配或替换）。
2. 上方 $F(i-1,j) + g$：$x_i$ 与 Gap 对齐（即 $x_i$ 被删除）。
3. 左方 $F(i,j-1) + g$：Gap 与 $y_j$ 对齐（即在 $x$ 中插入 $y_j$）。

4. 局部比对（Local Alignment）

Smith-Waterman 算法针对的是”局部同源”场景。例如，两个功能完全不同的蛋白质可能共享同一个保守的催化结构域。

输入与输出

• 输入：两条序列 $X = x_1 x_2 \cdots x_m$ 和 $Y = y_1 y_2 \cdots y_n$，以及打分体系。
• 输出：两条序列之间得分最高的局部相似片段（子比对），以及该片段的得分和位置。

为什么全局比对会失效？

如果在全局比对中，两个序列中间有一段高度保守的区域，但两侧是完全无关的噪音，那么两侧的 Gap 或错配惩罚会迅速”淹没”中间的匹配得分，导致算法给出错误的解释。

例如，考虑序列 $X = \text{XXABCXX}$ 和 $Y = \text{YYABCYY}$（其中 X、Y 代表不相关的字符，ABC 是保守核心）。全局比对会强制将两端的 XX 和 YY 也对齐，产生大量错配或 Gap，拉低整体得分。局部比对则能精准提取 ABC 这一高分片段。

核心改进：引入 0

$H(i,j) = \max \begin{cases} 0 \\ H(i-1,j-1) + s(x_i, y_j) \\ H(i-1,j) + g \\ H(i,j-1) + g \end{cases}$

初始条件严格定义为：

$$\begin{aligned} H(i, 0) &= 0, \quad i = 0, 1, \ldots, m \\ H(0, j) &= 0, \quad j = 0, 1, \ldots, n \end{aligned}$$

最终的最优得分为：

$H_{\max} = \max_{0 \leq i \leq m, \, 0 \leq j \leq n} H(i,j)$

• 直觉：如果当前的对齐得分变成了负数（说明当前匹配非常糟糕），算法允许在这里直接放弃之前的对齐，将得分设为 0，从当前点重新开始寻找新的高分片段。
• 回溯终点：从整个矩阵中的最高得分点开始回溯，直到遇到第一个得分为 0 的单元格。

5. Worked Example：全局比对 vs 局部比对

考虑两条序列：

• $X = \text{TACGTACG}$
• $Y = \text{AACGTTTG}$

使用打分体系：匹配 +2，错配 -1，Gap -2。

全局比对（Needleman-Wunsch）

初始化：首行首列按 $-2i$ 和 $-2j$ 填充。

关键步骤（展示部分矩阵）：

	-	A	A	C	G	T	T	T	G
-	0	-2	-4	-6	-8	-10	-12	-14	-16
T	-2	-1	-3	-5	-7	-6	-8	-10	-12
A	-4	0	0	-2	-4	-5	-7	-9	-11
C	-6	-2	-1	2	0	-2	-4	-6	-8
G	-8	-4	-3	0	4	2	0	-2	-4
T	-10	-6	-5	-2	2	6	4	2	0
A	-12	-8	-4	-4	0	4	4	2	0
C	-14	-10	-6	-2	-2	2	2	0	1
G	-16	-12	-8	-4	0	0	0	0	2

全局最优得分：$F(8,9) = 2$。

从 $(8,9)$ 回溯到 $(0,0)$，一条可能的比对为：

T A C G T A C G -
- A - C G T T T G

注意两端产生了大量 Gap，整体得分被拉低。

局部比对（Smith-Waterman）

初始化：首行首列全填 0。

关键步骤（展示部分矩阵）：

	-	A	A	C	G	T	T	T	G
-	0	0	0	0	0	0	0	0	0
T	0	0	0	0	0	2	0	0	0
A	0	2	2	0	0	0	0	0	0
C	0	0	0	4	2	0	0	0	0
G	0	0	0	2	6	4	2	0	0
T	0	0	0	0	4	8	6	4	2
A	0	2	2	0	2	6	6	4	2
C	0	0	0	4	2	4	4	4	2
G	0	0	0	2	6	4	2	2	6

矩阵最大值：$H(5,5) = 8$。

从 $(5,5)$ 回溯到第一个 0：

T A C G T
| | | | |
T A C G T

局部比对精准地找到了序列中间的高分片段 TACGT，得分 8（5 个匹配，每个 +2），而不被两端的不相关区域干扰。

对比总结

维度	全局比对（NW）	局部比对（SW）
**应用场景**	比较近缘物种的同源基因。	寻找结构域、Motif、Read 定位。
**矩阵初始化**	惩罚首行首列（$i cdot g$）。	首行首列全为 0。
**递推公式**	取三个方向的最大值。	取四个方向（含 0）的最大值。
**回溯位置**	必须从 $(n, m)$ 开始。	从矩阵内任意最大值处开始。
**本例最优得分**	2	8

6. 复杂度分析

全局比对（Needleman-Wunsch）

指标	复杂度
时间	$O(mn)$
空间	$O(mn)$（完整矩阵存储）
空间优化	$O(\min(m,n))$（仅需得分时）

局部比对（Smith-Waterman）

指标	复杂度
时间	$O(mn)$（填充矩阵 + 查找最大值）
空间	$O(mn)$（完整矩阵存储）
空间优化	$O(\min(m,n))$（仅需得分时）

两种算法在渐进复杂度上相同。差异在于常数因子：Smith-Waterman 的递推多一个选项（比较 0），但这是常数级别的额外开销。

适用前提

• 两条序列的长度差异不宜过大。如果 $m \gg n$，全局比对会产生大量 Gap，比对结果失去意义。
• 打分体系需要合理设置。特别是 Gap 罚分 $g$ 的绝对值不能太大，否则最优比对会倾向于用 Gap 替代所有错配。
• 对于局部比对，替换矩阵中匹配得分必须为正、错配和 Gap 必须为负，否则”引入 0”的止损机制无法正常工作。

7. 与真实工具的连接

全局比对工具

• EMBOSS Needle：基于 Needleman-Wunsch 的在线工具，适用于蛋白质和核酸的全局比对。
• Stretcher（EMBOSS 套件）：另一种全局比对实现，支持更灵活的打分方案。
• 全局比对在基因组学中的间接应用：全基因组比对工具（如 MUMmer）在锚定保守片段后，对相邻锚点之间的区域进行类似全局比对的精细对齐。

局部比对工具

• EMBOSS Water：基于 Smith-Waterman 的在线工具。
• BLAST：Smith-Waterman 的启发式加速版本，是数据库搜索的标准工具。详见 BLAST。
• SSEARCH：使用 Smith-Waterman 进行数据库搜索的精确工具，适用于小规模数据库或需要最高敏感性的场景。
• 短序列比对器（如 BWA-SW、Bowtie2 的局部模式）：针对下一代测序数据的局部比对工具，核心思想源自 Smith-Waterman，但通过 BWT 索引大幅加速。

常见误区

• 全局比对总能给出更好的生物学结果：
• 不是。全局比对强制对齐全部字符，如果两条序列只有局部相似（如共享一个功能结构域但其余部分完全不同），全局比对会因为强制对齐不相关区域而给出误导性结果。
• 局部比对只能找到一个相似片段：
• Smith-Waterman 矩阵中可能存在多个高分区域。标准算法只报告最高分的一个，但可以通过修改回溯策略来提取所有得分超过阈值的局部比对（即"Waterman-Eggert"方法）。
• 局部比对是全局比对的"改进版"：
• 不是。它们解决的是不同的问题。局部比对多了一个"引入 0"的选项，这是针对特定场景的修改，并非在所有情况下都优于全局比对。如果两条序列确实整体同源，全局比对能提供更完整的演化信息。

相关页面

打分矩阵

定义匹配与错配的权重

延伸阅读

BLAST

局部比对的极速启发式版本

延伸阅读

多序列比对（MSA）

将比对扩展到多条序列

延伸阅读