WFAA example

下面用一个具体的例子，完整走一遍 extend 模块和 compute 模块如何配合，把 WFA-Adapt 的一行行波前推进下去。

---

1. 先明确两个模块的分工

模块	输入	做什么	输出
compute	上一行的 $M$、$I$、$D$ 状态，当前对角线 $K$	用 WFA 递推公式算出 $X_{s,K}$，即编辑操作后、匹配延伸前的起始 offset	一个起始 offset
extend	起始 offset + $K$	从该位置出发，比较 $R$ 和 $Q$ 的碱基，直到不匹配	新的最远 offset

流程是：

compute → 算出 X[s,K] → extend → 得到 M[s,K] → 下一行 compute 再用

---

2. 例子设置

• 参考序列 $R = \text{A C G T A C}$（长度 6）
• 查询序列 $Q = \text{A C G T C A}$（长度 6）
• 打分：错配 = 1，插入 = 1，删除 = 1（Levenshtein 距离）
• 对角线定义：$k = i - j$

目标：找到把 $R$ 变成 $Q$ 的最优编辑距离。

---

3. s = 0：只有主对角线 k = 0

3.1 compute 模块

这是起始波前，没有编辑操作。

$$X_{0,0} = 0$$

起始 offset = 0，位置 $(0,0)$。

3.2 extend 模块

从 $(0,0)$ 出发，沿对角线 $k=0$ 匹配：

R: A C G T A C
Q: A C G T C A
   ✓ ✓ ✓ ✓ ✗

• $R[1]=A$ 对 $Q[1]=A$ → 匹配
• $R[2]=C$ 对 $Q[2]=C$ → 匹配
• $R[3]=G$ 对 $Q[3]=G$ → 匹配
• $R[4]=T$ 对 $Q[4]=T$ → 匹配
• $R[5]=A$ 对 $Q[5]=C$ → 不匹配，停止

extend 返回新 offset = 4，位置 $(4,4)$。

$$M_{0,0} = 4$$

结果： 波前 $s=0$ 记录 $k=0$ 上最远到达 $(4,4)$。

---

4. s = 1：compute + extend 对三条对角线并行

现在要对 $k = -1, 0, 1$ 分别 compute + extend。
它们互相独立，可以并行。

4.1 k = -1：来自删除

compute：

$$X_{1,-1} = D_{1,-1} = M_{0,0} = 4$$

起始 offset = 4。位置：$i=4$，$j = i - k = 4 - (-1) = 5$，即 $(4,5)$。

extend：

从 $(4,5)$ 出发：

• $R[5]=A$ 对 $Q[6]=A$ → 匹配
• $R[6]=C$ 对 $Q[7]$ → 越界，停止

返回 offset = 5，位置 $(5,6)$。

$$M_{1,-1} = 5$$

---

4.2 k = 0：来自错配

compute：

$$X_{1,0} = M_{0,0} + 1 = 4 + 1 = 5$$

起始 offset = 5。位置：$i=5$，$j = 5 - 0 = 5$，即 $(5,5)$。

extend：

从 $(5,5)$ 出发：

• $R[6]=C$ 对 $Q[6]=A$ → 不匹配，停止

返回 offset = 5，位置 $(5,5)$。

$$M_{1,0} = 5$$

---

4.3 k = 1：来自插入

compute：

$$X_{1,1} = I_{1,1} = M_{0,0} + 1 = 4 + 1 = 5$$

起始 offset = 5。位置：$i=5$，$j = 5 - 1 = 4$，即 $(5,4)$。

extend：

从 $(5,4)$ 出发：

• $R[6]=C$ 对 $Q[5]=C$ → 匹配
• $Q[6]=A$ 对 $R[7]$ → 越界，停止

返回 offset = 6，位置 $(6,5)$。

$$M_{1,1} = 6$$

---

4.4 s = 1 的波前汇总

$k$	compute 得到 $X$	extend 起点	extend 终点	$M_{1,k}$
$-1$	4	$(4,5)$	$(5,6)$	5
$0$	5	$(5,5)$	$(5,5)$	5
$1$	5	$(5,4)$	$(6,5)$	6

终点 $(6,6)$ 还没到。

---

5. s = 2：到达终点

5.1 k = 0 的 compute

对 $k=0$，有三个候选来源：

插入：

$$I_{2,0} = M_{1,-1} + 1 = 5 + 1 = 6$$

位置 $(6,6)$ —— 到达终点！

删除：

$$D_{2,0} = M_{1,1} = 6$$

位置 $(6,6)$ —— 到达终点！

错配：

$$M_{1,0} + 1 = 5 + 1 = 6$$

位置 $(6,6)$ —— 到达终点！

所以：

$$X_{2,0} = 6$$

起始 offset = 6，位置 $(6,6)$。

5.2 extend

已经在终点，没有可匹配的碱基。

$$M_{2,0} = 6$$

第一次到达终点 $(6,6)$ 的分数是 $s=2$，所以：

$$d = 2$$

---

6. 回溯路径

从 $(6,6)$ 回溯：

(6,6) ← (6,5) ← (5,5) ← (4,4) ← (3,3) ← (2,2) ← (1,1) ← (0,0)

对应比对：

R: A C G T A C -
Q: A C G T - C A

操作：删除 $R[5]=A$，插入 $Q[6]=A$，共 2 次编辑。

---

7. 这个例子展示了什么？

1. compute 模块：根据上一行的状态，算出编辑操作后的起始 offset。
   例如 $X_{1,-1} = 4$，$X_{1,0} = 5$，$X_{1,1} = 5$。

2. extend 模块：从起始 offset 出发，沿对角线做匹配延伸。
   例如从 $(4,5)$ 延伸到 $(5,6)$，从 $(5,4)$ 延伸到 $(6,5)$。

3. 两者交替配合：
   compute 算起点 → extend 算终点 → 下一行 compute 用上一行的终点作为输入。

4. 并行性：
   $s=1$ 时三条对角线 $k=-1,0,1$ 的 compute 和 extend 互相独立，可以同时用 $N_{ext}$ 和 $N_{comp}$ 个模块并行处理。

---

8. 一句话总结

compute 模块负责“算从哪里开始匹配延伸”，extend 模块负责“沿对角线一直匹配到不能匹配为止”。两者交替工作，一行一行推进 WFA-Adapt 的三角矩阵，直到第一次到达终点 $(m,n)$，此时的分数就是最优编辑距离。