Skip to main content

4.3 Traceback

你问的 Traceback，简单说就是：

分数矩阵只告诉你“最优比对得了多少分”，但不告诉你“具体怎么比”。
Traceback 就是沿着之前存好的“指针”倒着走，把最优比对的具体路径还原出来。

没有 traceback，你只知道两条序列相似度是 100 分，但不知道哪个碱基对哪个碱基、哪里插了 gap、哪里发生了替换。
对生物分析来说，具体比对结果才是最终要的东西。

下面以 TALCO-XDrop 为例，从最基础讲起。

1. 先看经典 DP：为什么需要 traceback？​

假设两条短序列：

R = A C
Q = A G

用 Needleman-Wunsch 打分：匹配 +2，错配 -1，gap -1。

填分数矩阵时，每个格子 (i,j)(i,j) 会算出最优分数，同时记录这个最优分数是从哪个邻居来的：

  • 从左上角来 → 表示 RiR_i 和 QjQ_j 对齐（匹配或错配）
  • 从上方来 → 表示 RiR_i 对 gap
  • 从左方来 → 表示 QjQ_j 对 gap

这个“从哪来”的记录就是 traceback pointer。

矩阵填完后，右下角是最终最优分数。
然后从右下角开始，沿着指针一步步往回走，直到左上角。
走出来的路径就告诉你每一步是匹配、错配、插入还是删除。

比如这个例子，回溯路径是：

(2,2) → (1,1) → (0,0)

对应：

R: A C
Q: A G

第一步 (2,2)(2,2) 来自 (1,1)(1,1)，表示 CC 和 GG 错配；
(1,1)(1,1) 来自 (0,0)(0,0)，表示 AA 和 AA 匹配。

最终比对：

A C
A G

所以 traceback 的作用就是：把分数变成具体比对。

2. TALCO-XDrop 里面，traceback 为什么不能一次性做？​

经典 DP 会把整个 m×nm \times n 矩阵的指针都存下来，最后从终点一次回溯到起点。
但长序列的矩阵太大，片上内存根本放不下。

TALCO 的做法是 切 tile：

  • 每个 tile 只覆盖矩阵的一小块。
  • 每个 tile 只存自己这一小块的 traceback 指针。
  • 算完一个 tile，就从这个 tile 的某个起点回溯，得到这一段的 partial alignment。
  • 然后滑动到下一个 tile，继续算、继续回溯。
  • 最后把所有 tile 的 partial alignment 拼起来，就是完整比对。

所以 TALCO-XDrop 里的 traceback 不是全局一次回溯，而是 每个 tile 内部分别回溯，最后拼接。

3. TALCO-XDrop 硬件里的 traceback 具体在做什么？​

回顾图 7a 的硬件结构：

  • PE 阵列算分数；
  • 每个 PE 算出一个格子时，除了分数，还会生成一个 4-bit traceback pointer；
  • 这些指针存到每个 PE 专用的 Traceback Pointer SRAM；
  • 同时，每个 stripe 的起始和结束位置存到 Start/Stop SRAM；
  • 到达 marker 后，Phase 2 检测收敛，确定这个 tile 的回溯起点 CtbC_{tb}；
  • 然后 Traceback Logic 从 CtbC_{tb} 开始，根据 SRAM 里的指针一步步走，走出这个 tile 的 partial alignment。

4-bit 指针是什么？​

每个格子的最优分数 Hi,jH_{i,j} 可能来自三个地方：

  • 对角线：Hi−1,j−1+W(Ri,Qj)H_{i-1,j-1} + W(R_i,Q_j)
  • 插入状态 Ii,jI_{i,j}
  • 删除状态 Di,jD_{i,j}

所以需要 2 bits 表示 HH 来自哪里。
然后 II 和 DD 各自还需要 1 bit 表示它们是从同状态延长还是从 HH 打开。
总共 4 bits。

回溯时：

  • 如果 HH 来自对角线，就知道这一步是匹配或错配；
  • 如果 HH 来自 II，就知道这一步是插入；
  • 如果 HH 来自 DD，就知道这一步是删除；
  • 再看 II 或 DD 的 bit，决定是继续延长 gap 还是打开新 gap。

这样一步步走，就能还原出这一段的比对。

4. 一个 TALCO-XDrop 的类比例子​

假设整个长矩阵被切成两个 tile。

Tile 1​

  • Phase 1：正常算，存指针。
  • 到达 marker，Phase 2 检测到所有回溯路径汇聚到 marker 上的格子 CxC_x。
  • Traceback Logic 从 CxC_x 开始，沿指针回溯，得到 Tile 1 的 partial alignment，比如：
R: A C G T
Q: A C - T

这一段表示：前三个碱基匹配，第三个位置有一个删除。

Tile 2​

  • 用 Tile 1 的 marker 分数初始化。
  • 继续算，再找到收敛点，回溯得到 Tile 2 的 partial alignment，比如：
R: A C
Q: A A

拼接​

把两段拼起来，就是完整比对：

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

如果没有 traceback，你只知道总分数是多少，但拼不出这个具体结果。

5. 为什么 TALCO 要分 Phase 1 和 Phase 2 来配合 traceback？​

  • Phase 1：正常算，存 traceback 指针。这些指针是回溯的“原材料”。
  • Phase 2：不存指针，只传播 convergence pointer，目的是找到所有路径的汇聚点 CxC_x。
  • 找到 CxC_x 后，就知道：无论最优路径从后面哪里来，它回溯到这个 tile 时一定经过 CxC_x。
  • 于是从 CxC_x 开始回溯，就能保证这个 tile 的 partial alignment 一定包含在完整最优比对中。

如果像 GACT 那样贪心选边界最高分，可能选错起点，回溯出来的路径就不是最优的。
TALCO 用收敛点作为回溯起点，保证了正确性。

6. 一句话总结​

Traceback 就是把“分数矩阵”变成“具体比对”的过程。
在 TALCO-XDrop 中，每个 PE 算分时顺便生成 4-bit 指针并存到 SRAM；到达 marker 后，Phase 2 找到所有回溯路径的汇聚点 CxC_x；Traceback Logic 从 CxC_x 出发，根据 SRAM 里的指针一步步倒着走，走出当前 tile 的 partial alignment；多个 tile 的 partial alignment 拼起来，就是最终完整比对。没有 traceback，你只有分数，得不到具体的碱基对应关系。