2.2 WFA algorithm

一句话概括：WFA 是“波前算法”，它不填满整个 $m\times n$ 的 DP 矩阵，而是按编辑距离/分数从 0 开始一层一层向外扩展；每层只记录每条对角线上能走到的最远位置，直到第一次到达终点，就找到了最优比对。

下面按“直觉 → 简单版 → 回溯矩阵 → affine gap 扩展 → 与 TALCO 的关系”来讲。

---

1. 为什么需要 WFA？

经典 Needleman-Wunsch / Smith-Waterman 要填整个 $m\times n$ 矩阵，时间和内存都是 $O(mn)$。
但很多时候两条序列非常相似，真正的差异很少，比如只有 $d$ 个错配/插入/删除。
如果 $d$ 很小，就没必要算整个矩阵。

WFA 的想法是：

我只关心“分数为 0 时能走到哪、分数为 1 时能走到哪、分数为 2 时能走到哪……”
一旦某个分数 $s$ 能走到终点，这个 $s$ 就是最优编辑距离。

这就是“波前”：按分数一层层推进。

---

2. 核心概念：对角线、波前、匹配免费延伸

2.1 对角线

在 DP 矩阵里，定义对角线：

$$k = i - j$$

其中 $i$ 是参考序列 $R$ 的位置，$j$ 是查询序列 $Q$ 的位置。

• 主对角线：$k=0$，表示 $R$ 和 $Q$ 同步前进。
• 插入：$k$ 变成 $k-1$ 或 $k+1$。
• 删除：$k$ 变成另一个相邻对角线。
• 错配：留在同一条对角线 $k$。
• 匹配：也留在同一条对角线 $k$，但分数不增加。

2.2 匹配免费延伸

这是 WFA 最关键的一点：

如果当前格子是匹配，那么可以沿着同一条对角线一直走，直到遇到不匹配或序列结束。

所以 WFA 不需要一格一格算匹配，而是用最长公共前缀 LCP 直接跳过去。
这样速度会快很多。

2.3 波前

设 $W_s$ 表示“分数为 $s$ 时的波前”。
对于每一条对角线 $k$，$W_s$ 只记录一个值：

在分数 $s$ 下，对角线 $k$ 上能到达的最远位置。

因为同一条对角线上，走得越远越好，所以只需要保留最远位置。

---

3. 简单版 WFA：只考虑 Levenshtein 距离

先假设：

• 错配罚 1
• 插入罚 1
• 删除罚 1
• 匹配罚 0

这就是论文里说的 Myers 的 $O(nd)$ 算法的基础。

3.1 递推直觉

从分数 $s-1$ 到分数 $s$，只有三种操作会让分数增加 1：

1. 错配：留在同一条对角线 $k$，位置前进 1。
2. 插入：从对角线 $k-1$ 来。
3. 删除：从对角线 $k+1$ 来。

示意公式：

$$X_s(k)=\max \begin{cases} X_{s-1}(k)+1 & \text{错配}\\ X_{s-1}(k-1)+1 & \text{插入}\\ X_{s-1}(k+1) & \text{删除} \end{cases}$$

然后沿对角线做匹配延伸：

$$X_s(k) \leftarrow X_s(k) + \text{LCP}$$

直到不能匹配为止。

具体偏移量取决于对角线定义，这里只看直觉：
错配/插入/删除让分数 +1，匹配让位置免费前进。

3.2 流程

• 分数 $s=0$：从 $(0,0)$ 出发，沿主对角线尽可能匹配。
• 分数 $s=1$：从 $s=0$ 的波前出发，考虑一次错配/插入/删除，得到新的波前，再匹配延伸。
• 分数 $s=2$：从 $s=1$ 继续。
• …
• 直到某条波前到达终点 $(m,n)$。

此时分数 $s$ 就是最优编辑距离 $d$。

3.3 为什么快？

• 经典 DP 要算 $m\times n$ 个格子。
• WFA 只算到分数 $d$。第 $s$ 层最多有 $2s+1$ 条对角线。
• 总格子数大约是：

$$\sum_{s=0}^{d}(2s+1)=O(d^2)$$

• 加上 LCP 延伸，总时间复杂度是：

$$O(nd)$$

• 如果只存波前，内存是 $O(d)$；如果要存回溯指针，内存是 $O(d^2)$。

论文里说 WFA 需要 $O(nd)$ 时间和 $O(d^2)$ 内存，就是因为要保存三角回溯矩阵。

---

4. 三角回溯矩阵：怎么找回比对？

WFA 不仅算分数，还要能重建比对。它用一个三角形矩阵：

• 行：分数 $s$，即 alignment score。
• 列：对角线 $k$。
• 每个格子：存一个 traceback pointer。

每个指针有三种可能，指向上一行的：

1. 同一对角线：表示错配。
2. 相邻左对角线：表示插入。
3. 相邻右对角线：表示删除。

匹配不增加分数，所以不会产生新的行，而是沿着同一条对角线免费延伸。
回溯时，从终点所在的格子开始：

• 先沿对角线反向补上匹配段；
• 再根据指针跳到上一行；
• 重复，直到回到 $(0,0)$。

这样就得到了完整比对。

---

5. 一个极简例子

设：

• $R = AC$
• $Q = AG$
• 错配罚 1，插入/删除罚 1，匹配罚 0

分数 $s=0$

从 $(0,0)$ 出发，主对角线 $k=0$：

• $A$ 和 $A$ 匹配，免费前进到 $(1,1)$。
• 下一个 $C$ 和 $G$ 不匹配，停。

所以 $s=0$ 的波前最远到 $(1,1)$。

分数 $s=1$

从 $s=0$ 的 $(1,1)$ 出发：

• 做一次错配：$C$ 对 $G$，分数 +1，到达 $(2,2)$。

$(2,2)$ 就是终点。

所以最优编辑距离 $d=1$。

回溯

从 $(2,2)$ 回溯：

• 这一步是错配，指针指向 $s=0$ 的同一对角线。
• 在 $s=0$ 层，$A$ 和 $A$ 是匹配，沿对角线反向补上。
• 回到 $(0,0)$。

最终比对：

A C
A G

---

6. WFA 如何支持 affine gap？

Levenshtein 距离里，每个 gap 都罚 1。
但生物序列更常用 affine gap：

• gap open：打开一个 gap 的罚分，比如 $o$
• gap extend：延长一个 gap 的罚分，比如 $e$

这时不能只用一个波前，而要维护多个状态：

• $M_s$：当前是匹配/错配状态
• $I_s$：当前是插入状态
• $D_s$：当前是删除状态

递推时，插入和删除要分别考虑：

• 从匹配状态打开 gap：付 gap open；
• 从插入/删除状态继续延长：付 gap extend。

论文里的公式 (4) 到 (7) 就是 WFA 对 affine gap 的递推。
因为要维护多个波前，内存和计算量会增加一个常数倍，但仍然是 $O(nd)$ 量级。

WFA-Adapt

WFA 库还有一个启发式版本叫 WFA-Adapt。
它会丢弃三角矩阵中“落后太多”的外侧对角线，相当于做 banding，减少计算和内存。
但这是一种启发式，不保证一定和完整 WFA 结果完全一致。

---

7. WFA 的优缺点

优点：

• 当两条序列差异小、$d$ 很小时，比经典 DP 快很多。
• 内存只和 $d$ 有关，而不是和 $m\times n$ 有关。
• 支持 affine gap 和更一般的距离度量。
• 天然按分数推进，适合做波前并行。

缺点：

• 如果两条序列很长且差异很大，$d$ 会接近 $n$，复杂度退化。
• 如果打分参数范围很大，波前层数也会变多。
• 需要保存回溯信息时，内存是 $O(d^2)$，长而 noisy 的比对仍然可能占几百 MB。
• BiWFA 是 WFA 的内存优化版，用运行时间换内存，但长 noisy 比对仍然需要很大内存。

---

8. 和 TALCO 的关系

TALCO 把 WFA-Adapt 做 tiling，形成 TALCO-WFAA。

为什么可以切 tile？因为 WFA 本身是三角矩阵：

• 行 = 分数
• 列 = 对角线

论文里把 WFA 的 frontier 定义为：

• Levenshtein 距离下：一行就够，因为分数 $s+1$ 的路径一定经过分数 $s$。
• Affine gap 下：需要两行，因为分数 $s$ 的路径可能经过 $s-1$ 或 $s-2$。

TALCO 在每个 tile 里：

1. Phase 1：正常算波前，存 traceback 指针。
2. 到达 marker 后进入 Phase 2：传播 convergence pointer，看所有回溯路径是否汇聚到 marker 上同一个格子。
3. 如果汇聚，就从这个格子开始回溯，保证和完整 WFA-Adapt 的结果一致。

所以 TALCO-WFAA 是第一个能把 WFA-Adapt 做任意长序列比对加速、同时保证 banding 约束下最优的 tiling 方案。

---

9. 一句话总结

WFA 就是按“编辑距离/分数”从 0 开始逐层扩展波前：匹配免费跳，错配/插入/删除换对角线并加 1；三角矩阵记录回溯来源；第一次到达终点就得到最优比对。TALCO 则利用这些回溯路径的汇聚性质，把长比对安全地切成 tile。