编辑距离

快速概览

编辑距离是理解序列比对最短路径的一页起点：它把序列相似性问题转成一个可以用动态规划系统求解的最小代价问题。

• 先掌握状态定义和递推关系，再去看全局/局部比对会更顺。
• 它不是现代比对工具的完整算法，但几乎是所有后续打分模型的起点。

前置知识

所属板块 核心方法

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

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

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

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

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

是什么

编辑距离（edit distance）衡量一个字符串变成另一个字符串所需的最少编辑操作数。最经典的设置允许三类操作：

• 插入（insert）
• 删除（delete）
• 替换（substitute）

如果每种操作的代价都设为 1，那么编辑距离描述的是两个字符串之间最直接的”变换成本”。

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

在生物信息学里，我们经常需要回答这样的问题：

• 两条 DNA 序列到底有多相似？
• 某个 read 是否可能来自某段参考基因组？
• 一个变异位点更像是替换、插入还是缺失？

编辑距离把这些”相似不相似”的直觉问题，转成了一个可以计算、可以优化的问题。虽然真实的序列比对通常会使用更复杂的打分体系，但编辑距离依然是理解比对算法的最短路径。

数学模型

状态 `dp[i][j]`

表示把 `x` 的前 `i` 个字符转换成 `y` 的前 `j` 个字符所需的最小代价。

边界条件

空串到长度为 `j` 的串需要插入 `j` 次，长度为 `i` 的串到空串需要删除 `i` 次。

核心操作

删除、插入、匹配/替换三类局部选择决定了当前状态的最优值。

设两个字符串分别为 x = x_1x_2...x_m 和 y = y_1y_2...y_n。

定义 dp[i][j] 表示：把 x 的前 i 个字符转换成 y 的前 j 个字符所需的最小代价。

边界条件为：

$$\begin{aligned} dp[0][j] &= j \\ dp[i][0] &= i \end{aligned}$$

含义很直观：

• 空串变成长度为 j 的串，需要插入 j 次；
• 长度为 i 的串变为空串，需要删除 i 次。

核心递推

当 i > 0 且 j > 0 时，递推关系为：

$$dp[i][j] = \min \begin{cases} dp[i-1][j] + 1 & \text{删除 } x_i \\ dp[i][j-1] + 1 & \text{插入 } y_j \\ dp[i-1][j-1] + \delta(x_i, y_j) & \text{匹配或替换} \end{cases}$$

其中：

$$\delta(x_i, y_j) = \begin{cases} 0, & x_i = y_j \\ 1, & x_i \ne y_j \end{cases}$$

这个递推体现了动态规划的核心思想：当前最优解来自三个更小子问题中的最优选择。

示例

考虑把 GATT 变成 GCAT。

构造一个包含空串行列的动态规划矩阵，蓝色高亮为匹配（代价 0），黄色高亮为替换（代价 1），箭头标出一条最优路径。最终 dp[4][4] = 2，表示最小编辑距离为 2。

一个可能的变换路径是：

1. GATT -> GC TT：把第二个字符 A 替换成 C
2. GCTT -> GCAT：把第三个字符 T 替换成 A

这个例子说明：即使两个序列很短，最优路径也不一定一眼能看出来，而动态规划会系统地枚举所有局部可能性。

为什么动态规划有效

编辑距离问题同时具有：

• 最优子结构：大问题的最优解由小问题最优解组成；
• 重叠子问题：很多中间状态会被反复访问。

例如在比对两个长序列时，“前 50 个字符与前 60 个字符的最优代价”可能会被多个后续状态共同依赖。动态规划通过缓存中间结果避免重复计算。

复杂度与适用前提

如果直接填完整个矩阵：

• 时间复杂度：$O(mn)$
• 空间复杂度：$O(mn)$

如果只需要最终距离而不需要回溯路径，可以把空间压缩到 $O(\min(m,n))$。

但要注意，编辑距离模型有很强的简化假设：

• 所有插入、删除、替换代价都一样；
• 不区分不同字符替换的生物学意义；
• 不考虑一段连续 gap 比多次离散 gap 更合理这类现象。

这些限制也是为什么真实生物序列比对往往会引入更复杂的打分矩阵和 gap 罚分模型。

与真实工具或流程的连接

编辑距离本身很少直接作为现代大规模比对工具的完整算法，但它是多个现实任务的核心原型：

• read mapping 中局部精细比对的思想基础；
• variant calling 中插入/缺失的解释基础；
• 拼接、纠错和模糊匹配中的基础距离概念；
• 教材中 Needleman–Wunsch 和 Smith–Waterman 的出发点。

可以把它理解成”最简单的序列比对模型”。后面的全局比对、局部比对、打分矩阵和 affine gap penalty，都是在这个模型上不断加入更真实的生物学假设。

常见误区

• 编辑距离越小，就一定是更好的生物学解释：
• 不一定。编辑距离只反映最小操作数，不一定反映更真实的进化过程或测序错误模型。
• 替换和插入/删除应该永远同价：
• 在教学模型里可以这样设定，但真实比对通常不会这么简单。
• 编辑距离就是序列比对的全部：
• 不是。它只是最基础的抽象，真实系统往往还需要：

参考资料

• An Introduction to Bioinformatics Algorithms
• Dan Gusfield, Algorithms on Strings, Trees, and Sequences
• Needleman–Wunsch / Smith–Waterman 相关原始论文

相关页面

• 全局比对与局部比对
• 打分矩阵与 gap 罚分
• 索引结构概览
• RNA-seq 工作流概览

Needleman-Wunsch 算法

在编辑距离基础上引入打分矩阵的全局比对算法

延伸阅读

最长公共子序列

与编辑距离有直接数学关系的序列相似性度量

延伸阅读

Smith-Waterman 算法

从编辑距离扩展而来的局部比对算法

延伸阅读

全局比对与局部比对

比对策略的选择与适用场景

延伸阅读

打分矩阵与 gap 罚分

编辑距离的简化假设如何被更真实的打分模型替代

延伸阅读