WFAA Traceback Path

TALCO-WFAA 的 traceback path 确定过程和 TALCO-XDrop 思路一致，但因为 WFA-Adapt 的三角矩阵结构和状态不同，具体细节有所区别。下面以你给的例子 $Q = \text{ACGTAC}$，$R = \text{AGAC}$ 为例，完整走一遍。

---

1. 总体流程

TALCO-WFAA 每个 tile 的回溯路径确定分三步：

1. Phase 1：从 tile 起点算到 marker，正常计算并存储 traceback pointer。
2. Phase 2：从 marker 往后算，传播 convergence pointer，直到收敛，确定回溯起点 $C_{tb}$。
3. Traceback Logic：从 $C_{tb}$ 出发，根据 Phase 1 存的 traceback pointer，一步步回溯，得到当前 tile 的 partial alignment。

所有 tile 的 partial alignment 拼接起来，就是完整 traceback path。

---

2. WFA-Adapt 的 traceback pointer 形式

在 WFA-Adapt 的三角矩阵中，每个格子 $(s, K)$ 存一个 traceback pointer，编码：

• 当前最远 offset 是通过哪种编辑操作得到的：
  • 错配：来自同一对角线 $K$，分数 $s-1$；
  • 插入：来自对角线 $K-1$，分数 $s-1$；
  • 删除：来自对角线 $K+1$，分数 $s-1$；
• 对于 affine gap，还要区分 gap 是打开还是延长。

所以每个指针是几个 bit 的位域，和 TALCO-XDrop 的 4-bit 指针类似，只是状态名称换成了 WFA 的 $M$、$I$、$D$。

---

3. Phase 1：存下回溯的“原材料”

以你的例子为例，WFA-Adapt 的三角矩阵按分数 $s$ 推进。

s = 0

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

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

到达 $(4,4)$，所以：

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

Phase 1 存下这个格子的指针：表示“从 $(0,0)$ 沿对角线匹配到 $(4,4)$”。

s = 1

三条对角线并行：

$k$	操作	起点	匹配延伸后	指针编码
$-1$	插入	$(4,5)$	$(5,6)$	来自 $k=0$ 的插入
$0$	错配	$(5,5)$	$(5,5)$	来自 $k=0$ 的错配
$1$	删除	$(5,4)$	$(6,5)$	来自 $k=0$ 的删除

Phase 1 把每个格子的指针存到 SRAM。

s = 2

从 $k=-1$ 的 $(5,6)$ 插入，进入 $k=-2$，起点 $(5,7)$ 越界；
从 $k=0$ 的 $(5,5)$ 错配，起点 $(6,6)$，到达终点；
从 $k=1$ 的 $(6,5)$ 删除，起点 $(6,6)$，到达终点。

所以 $(s=2, k=0)$ 和 $(s=2, k=-2)$ 附近的格子都有指针。

Phase 1 结束时，当前 tile 的 traceback 矩阵 TBTile 存好了所有需要的指针。

---

4. Phase 2：确定回溯起点 $C_{tb}$

到达 marker 后，进入 Phase 2。

4.1 初始化

Marker 上每个 cell 获得唯一 id：

ConvPr_marker = [0, 1, 2, ..., B_max-1]

4.2 传播

每往后算一行，就做一次 redirect：

$$\text{ConvPrcurr}[i] = \text{ConvPrprev}[\text{Prf}[i]]$$

即：当前格子的 convergence pointer = 它回溯到的上一行格子的 convergence pointer。

4.3 收敛判断

当当前 frontier 上所有格子的 convergence pointer 都指向 marker 上同一个格子 $C_x$ 时，判定收敛：

$$C_{tb} = C_x$$

在 WFA-Adapt 中，frontier 由两行组成，因为 affine gap 的分数依赖可能跨两行。
所以收敛判断是对这两行一起做的。

4.4 特殊情况

• 一直不收敛，到达末尾：用 ConvPrlatt，即局部最大分格子 Clast 对应的 convergence pointer 作为 $C_{tb}$。
• 局部比对最大分在收敛前更新：保存 ConvPrlatt，以备后用。
• wavefront 超过 $B_{\max}$：回退 CPU。

---

5. Traceback Logic：从 $C_{tb}$ 回溯

确定了 $C_{tb}$ 后，Traceback Logic 开始工作。

5.1 回溯规则

从 $C_{tb}$ 出发，每一步读取当前格子的 traceback pointer：

• 如果指针说“来自同一对角线的错配”，就往 $(s-1, k)$ 走；
• 如果指针说“来自 $k-1$ 的插入”，就往 $(s-1, k-1)$ 走；
• 如果指针说“来自 $k+1$ 的删除”，就往 $(s-1, k+1)$ 走；
• 如果指针说“匹配延伸”，就在同一行内沿对角线反向走，补上匹配段。

5.2 在你的例子中

假设 $C_{tb}$ 落在 $(s=2, k=0)$ 或 $(s=2, k=-2)$ 附近。

从终点 $(4,6)$ 回溯：

(4,6) ← 匹配 C-C ← (3,5) ← 匹配 A-A ← (2,4)
       ← 插入 T ← (2,3) ← 匹配 G-G ← (1,2)
       ← 插入 C ← (1,1) ← 匹配 A-A ← (0,0)

对应比对：

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

回溯过程中，每一步都根据 Phase 1 存的指针决定往哪走。

5.3 生成 compact CIGAR

Traceback Logic 每走一步，就生成一个 compact CIGAR 字符：

• =：匹配
• X：错配
• I：插入
• D：删除

最后把 compact CIGAR 送到 CPU 线程，解包成完整 CIGAR。

---

6. 多个 tile 的拼接

每个 tile 结束后：

• 用 marker 分数初始化下一个 tile；
• 下一个 tile 从当前 marker 之后开始；
• 重复 Phase 1 → Phase 2 → Traceback。

所有 tile 的 partial alignment 按顺序拼接，就是完整 traceback path。

---

7. 和 TALCO-XDrop 的区别

项目	TALCO-XDrop	TALCO-WFAA
矩阵形状	矩形 $m \times n$	三角矩阵（行=分数，列=对角线）
Frontier 定义	两条相邻 wavefront	Levenshtein：一行；affine gap：两行
Traceback pointer	4-bit，编码 $I$、$D$、对角线	类似位域，编码 $M$、$I$、$D$ 及 gap 打开/延长
回溯方向	沿 DP 矩阵往回走	沿三角矩阵往回走，同时补匹配段
收敛判断	一个 frontier 上所有指针相同	两行 frontier 上所有指针相同

---

8. 一句话总结

TALCO-WFAA 的 traceback path 确定过程是：Phase 1 正常计算并存储每个格子的 traceback pointer；Phase 2 从 marker 往后传播 convergence pointer，直到所有路径汇聚到 marker 上同一个格子 $C_x$，令 $C_{tb} = C_x$；Traceback Logic 从 $C_{tb}$ 出发，根据 Phase 1 存的指针一步步回溯，得到当前 tile 的 partial alignment；所有 tile 的 partial alignment 拼接起来，就是完整 traceback path。这个路径保证与不做 tiling 的完整 WFA-Adapt 结果一致。