编辑距离

快速概览

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

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

是什么

编辑距离（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。

一个可能的变换路径是：

GATT -> GC TT：把第二个字符 A 替换成 C
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，都是在这个模型上不断加入更真实的生物学假设。

最长公共子序列（LCS）

最长公共子序列（Longest Common Subsequence, LCS） 是编辑距离的一个特例：只允许插入和删除（不允许替换），目标是找两个字符串共有的最长子序列。子序列（subsequence）不要求连续，区别于子串（substring）。

与编辑距离的数学关系

如果编辑距离只允许插入和删除操作，则它与 LCS 长度有直接关系：

d(v, w) = n + m - 2 \cdot s(v, w)

其中 $s(v, w)$ 是 LCS 长度， $n$ 、 $m$ 是两串长度。直观含义：最小编辑操作数等于把两个字符串都删减到 LCS 所需的总删除次数。

递推关系

定义 s[i][j] 为 v 的前 i 个字符与 w 的前 j 个字符的 LCS 长度：

s[i,j] = \max \begin{cases} s[i-1, j] & \text{if } v_i \notin \text{LCS} \\ s[i, j-1] & \text{if } w_j \notin \text{LCS} \\ s[i-1, j-1] + 1 & \text{if } v_i = w_j \end{cases}

边界条件 s[i, 0] = s[0, j] = 0。这与编辑距离的递推同构，对应一个编辑图上的最长路径问题：水平/垂直边权重 0（插入/删除），对角边在匹配时权重 +1。

示例

v = ATCTGAT，w = TGCATA，最终 s[7,6] = 4。一个 LCS 是 TCTA（或 TGAT、GCAT 等，可能有多个最优解）。

局限与扩展

LCS 只考虑匹配，不考虑错配代价，因此不足以反映生物学相似性。在蛋白质序列中某些替换更”保守”，这些细节在 LCS 中被忽略。LCS 的常见应用是 diff 算法、版本控制和序列初步筛选；要更精确的生物学分析，需推广为全局比对（Needleman-Wunsch）、局部比对（Smith-Waterman）和仿射间隙罚分。

参考资料

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