2.2.1 Levenshtein Distance

Levenshtein 距离，中文常叫编辑距离，是衡量两个字符串有多“不一样”的一种标准。

一句话定义：

把字符串 A 变成字符串 B，最少需要多少次“单字符编辑操作”。
每次操作只能是：插入一个字符、删除一个字符、替换一个字符。
每次操作的代价都是 1。

---

1. 三种允许的操作

假设要把 kitten 变成 sitting：

1. k → s：替换
   kitten → sitten
2. e → i：替换
   sitten → sittin
3. 末尾插入 g：插入
   sittin → sitting

一共 3 次操作，所以：

$$\text{Levenshtein}(kitten, sitting)=3$$

再看一个 DNA 例子：

• R = AC
• Q = AG

把 AC 变成 AG，只需要把 C 替换成 G，所以距离是 1。

---

2. 在序列比对里，它对应什么？

在序列比对中，Levenshtein 距离把三种情况都罚 1：

情况	操作	代价
匹配	字符相同	0
错配	替换	1
插入	在 Q 中多一个字符，相当于 R 有 gap	1
删除	在 R 中多一个字符，相当于 Q 有 gap	1

也就是说：

• 匹配不增加距离；
• 错配、插入、删除各增加 1；
• 不区分 gap open 和 gap extend，gap 每延长一个字符都再罚 1。

所以，Levenshtein 距离越小，两条序列越相似。

---

3. 怎么用动态规划算？

设两个序列：

$$R = r_1r_2\dots r_m,\quad Q = q_1q_2\dots q_n$$

定义 $D(i,j)$：

用 $R$ 的前 $i$ 个字符和 $Q$ 的前 $j$ 个字符时，最小的 Levenshtein 距离。

初始化：

$$D(i,0)=i$$

意思是：$Q$ 为空，要把 $R$ 的前 $i$ 个字符全删掉，需要 $i$ 次删除。

$$D(0,j)=j$$

意思是：$R$ 为空，要插入 $Q$ 的前 $j$ 个字符，需要 $j$ 次插入。

递推公式：

$$D(i,j)=\min \begin{cases} D(i-1,j)+1 & \text{删除 } r_i\\ D(i,j-1)+1 & \text{插入 } q_j\\ D(i-1,j-1)+[r_i \ne q_j] & \text{匹配或替换} \end{cases}$$

其中：

$$[r_i \ne q_j]= \begin{cases} 0, & r_i = q_j \text{ 匹配}\\ 1, & r_i \ne q_j \text{ 错配} \end{cases}$$

最后：

$$\text{Levenshtein}(R,Q)=D(m,n)$$

---

4. 一个简单矩阵例子

设：

• $R = AC$
• $Q = AG$

矩阵如下：

	空	A	G
空	0	1	2
A	1	0	1
C	2	1	1

右下角是 $D(2,2)=1$，所以距离是 1。

回溯看：

• A 和 A 匹配，代价 0；
• C 和 G 错配，代价 1。

所以比对为：

A C
A G

Levenshtein 距离 = 1。

---

5. 和 WFA 的关系

论文第二节说，Myers 的 $O(nd)$ 算法和 WFA 的简单版本，都是基于 Levenshtein 距离。

这里的 $d$ 就是：

两条序列的 Levenshtein 距离。

WFA 的做法是：

• 分数 $s=0$：只做匹配，沿对角线免费前进；
• 分数 $s=1$：允许一次错配/插入/删除；
• 分数 $s=2$：允许两次；
• ……
• 第一次到达终点 $(m,n)$ 时，这个分数 $s$ 就是 Levenshtein 距离。

所以 WFA 里说的“分数”，在 Levenshtein 模式下就是“编辑距离”。

---

6. 和 affine gap 的区别

Levenshtein 距离是最简单的打分方式：

• 每个错配罚 1；
• 每个插入字符罚 1；
• 每个删除字符罚 1；
• 不区分“打开 gap”和“延长 gap”。

而生物序列比对常用 affine gap：

• 打开一个 gap 罚 $o$；
• 延长一个 gap 罚 $e$；
• 通常 $o > e$。

例如：

A C G T
A - - T

Levenshtein 会认为中间两个 gap 各罚 1，总共罚 2。
Affine gap 会认为打开 gap 罚一次，再延长一次，总罚 $o+e$。

所以 affine gap 更贴近生物序列中“连续插入/删除更常见”的现象，但计算也更复杂。

---

7. 总结

Levenshtein 距离 = 最小编辑次数。

它允许：

• 插入；
• 删除；
• 替换。

每个操作代价都是 1，匹配代价是 0。
在序列比对中，它相当于一种最简单的全局比对打分方式。
WFA 的简单版本就是按 Levenshtein 距离一层一层扩展波前，第一次到达终点就找到最优距离。
TALCO 论文里提到 Edlib、Myers、Bitap 等算法，也都和 Levenshtein 距离密切相关。