Skip to main content

2.4 GACT

下面详细讲解论文中的 GACT，包括它为什么出现、核心思想、参数、工作流程、一个直观例子、优缺点，以及它和 TALCO 的关系。

1. GACT 是什么？为什么需要它？​

在 GACT 之前，长序列比对面临一个根本矛盾：

  • Banding 技术（如 X-Drop）虽然剪掉了大量格子，但保留的“带子”仍然要沿着整条序列延伸，内存需求随序列长度线性增长。
  • 硬件加速器（ASIC/FPGA）的片上内存很小，放不下整条带子。
  • 如果放在片外内存，带宽又不够，无法实现大幅加速。

于是，Darwin 协处理器 [7] 提出了一种 tiling 启发式，叫做 GACT。
它的目标是：

把长比对切成一系列固定大小、互相重叠的小块（tile），每次只在片上计算一个 tile，从而让内存需求固定为 O(T2)O(T^2)，与序列总长度无关。
这样就能在硬件上加速任意长的序列比对。

后来，GACT 被多个加速器采用，比如 GACT-X [8]、GenASM [9]、Scrooge [10]、SeGraM [22] 等。

2. 核心思想：重叠 tile + 贪心锚点​

GACT 的核心可以概括为两句话：

  1. 把 DP 矩阵切成一系列重叠的方形 tile，每个 tile 大小由参数 TT 决定，相邻 tile 的重叠区域由参数 OO 决定。
  2. 每个 tile 计算完后，贪心地选择一个边界点作为下一个 tile 的起点，然后滑动到下一个 tile，继续计算。

换句话说，GACT 不是一次性算完整个矩阵，而是像用放大镜一样，一个窗口一个窗口地沿着对角线方向推进。

论文图 2f 展示了 GACT 的 tiling 方式：

  • 参数 T=3T = 3，O=1O = 1。
  • 每个 tile 是 3×33 \times 3 的方块。
  • 相邻 tile 在行和列方向各重叠 11 个格子（黄色区域）。
  • 整个矩阵被这些重叠的方块覆盖。

3. 两个关键参数：TT 和 OO​

  • TT：tile 的大小。每个 tile 是一个 T×TT \times T 的 DP 子矩阵。

    • TT 越大，每个 tile 覆盖的区域越大，越不容易丢失最优路径，但片上内存需求也越大（O(T2)O(T^2)）。
    • TT 越小，内存越省，但可能切掉最优路径，导致结果变差。

  • OO：相邻 tile 之间的重叠大小。

    • 重叠区域的作用是：给最优路径一个“缓冲区”，让它在 tile 边界处有更多机会被下一个 tile 接上。
    • OO 越大，越安全，但冗余计算也越多。
    • OO 越小，计算越省，但更容易丢失路径。

GACT 要求：

O<TO < T

通常 OO 取 TT 的一个比例，比如 T/4T/4 或 T/2T/2。

4. GACT 的工作流程​

假设我们要比对参考序列 RR 和查询序列 QQ，矩阵大小为 m×nm \times n。

GACT 按以下步骤进行：

步骤 1：从左上角开始​

第一个 tile 从 (0,0)(0,0) 开始，覆盖一个 T×TT \times T 的区域。
在这个 tile 内，用经典的 DP（比如 Needleman-Wunsch）或带 banding 的 DP（比如 X-Drop）计算分数和 traceback 指针。

步骤 2：计算 tile 内的 DP​

在 tile 内部，正常填充分数矩阵，记录每个格子的 traceback 指针。
因为 tile 很小，这些数据可以全部放在片上内存中。

步骤 3：贪心选择下一个起点​

一个 tile 计算完后，GACT 需要决定下一个 tile 从哪里开始。
它采用贪心策略：

在当前 tile 的右下边界（或某个指定边界）上，选择分数最高的那个格子，作为下一个 tile 的起始锚点。

为什么是贪心？
因为 GACT 假设：真正的最优路径在穿过 tile 边界时，最有可能经过当前边界上分数最高的格子。
所以它直接选最高分点，而不是检查所有可能的路径。

步骤 4：滑动到下一个 tile​

下一个 tile 的起始位置由锚点决定，并且与当前 tile 有 OO 的重叠。
然后重复步骤 2 和 3，直到到达矩阵右下角。

步骤 5：保存 traceback 路径​

每个 tile 内计算出的 traceback 路径，会按顺序保存到片外内存。
因为路径总长度是 O(n)O(n)，片外内存足够大，但只用于存储，不参与计算，所以不影响加速。

最终，把所有 tile 的 traceback 路径拼接起来，就得到完整的比对。

5. 一个直观例子​

为了便于理解，我们用一个小矩阵来说明。

设：

  • 矩阵大小为 6×66 \times 6。
  • T=3T = 3，O=1O = 1。

GACT 会把矩阵切成这样的 tile：

Tile 1: 行 0-2, 列 0-2
Tile 2: 行 2-4, 列 2-4   （与 Tile 1 重叠 1 行 1 列）
Tile 3: 行 4-6, 列 4-6   （与 Tile 2 重叠 1 行 1 列）

注意：实际 GACT 是沿对角线方向排列 tile，这里简化成正方形。

计算过程：

  1. Tile 1：从 (0,0)(0,0) 到 (2,2)(2,2)，算出所有格子的分数和指针。
  2. 在 Tile 1 的右下边界（行 2 或列 2）上，找到分数最高的格子，假设是 (2,2)(2,2)。
  3. Tile 2：从 (2,2)(2,2) 开始，覆盖到 (4,4)(4,4)。它和 Tile 1 在 (2,2)(2,2) 附近重叠。
  4. 在 Tile 2 的右下边界上，再找最高分格子，假设是 (4,4)(4,4)。
  5. Tile 3：从 (4,4)(4,4) 开始，覆盖到 (6,6)(6,6)。
  6. 最后从 (6,6)(6,6) 回溯，把三个 tile 的路径拼起来。

如果真正的最优路径在 Tile 1 边界上经过的是 (2,1)(2,1) 而不是 (2,2)(2,2)，那么 GACT 就会选错起点，后续 tile 就会沿着错误路径走，最终得到的比对可能不是最优的。

这就是 GACT 不保证最优的根本原因。

6. GACT-X：加入 X-Drop​

在 Darwin-WGA [8] 中，作者把 X-Drop banding 融入了 GACT，称为 GACT-X。

GACT-X 的做法是：

  • 在每个 tile 内部，用 X-Drop 算法计算分数和 traceback 指针。
  • 也就是说，tile 内部会动态剪掉分数低于 Hmax⁡−XH_{\max} - X 的格子。
  • 但 tile 边界仍然用 GACT 的贪心策略选择下一个起点。

这样，GACT-X 比纯 GACT 更快、更省内存，但仍然不能保证与完整的 X-Drop 算法结果完全一致。

论文中提到：

“the GACT-X heuristic is not guaranteed to provide equivalent alignments to X-Drop and the performance is sensitive to properties of the input sequences, and the choice of TT and OO.”

也就是说，GACT-X 的结果受输入序列和参数选择影响很大。

7. 为什么 GACT 不保证最优？​

总结起来，GACT 不保证最优有三个原因：

  1. 贪心选择边界点：
    它只选当前边界上分数最高的格子，但最优路径可能经过边界上另一个分数稍低、但后续能走得更远的格子。

  2. 固定 tile 大小和重叠：
    如果最优路径在某个地方偏离了预设的 tile 重叠区域，就可能被切掉，无法接上。

  3. X-Drop 本身的剪枝：
    GACT-X 在 tile 内部还用了 X-Drop，这又增加了一层启发式，可能进一步降低质量。

论文图 15 显示：

  • 在 1% 错误率时，GACT、GACT-X、Scrooge 还能接近 100% 最优。
  • 但随着错误率升高到 30%，它们产生最优比对的百分比明显下降，而 TALCO-XDrop 几乎保持 100%。

8. GACT 的优点和缺点​

优点：

  • 片上内存固定为 O(T2)O(T^2)，与序列长度无关。
  • 可以处理任意长的序列比对。
  • 实现相对简单，容易集成到硬件加速器中。
  • 在 Darwin 等加速器中实现了三到四个数量级的加速。

缺点：

  • 不保证最优：结果可能比不 tiling 的软件算法差。
  • 对参数敏感：TT 和 OO 的选择影响很大。
  • 对输入敏感：错误率高、序列差异大时，质量下降明显。
  • 无法保证与软件 counterpart 等价：这在临床诊断等关键应用中是不可接受的。
  • 冗余计算：重叠区域会被重复计算，效率通常只有 75% 或更低。

9. GACT 与 TALCO 的关系​

TALCO 也是在长比对中做 tiling，但它和 GACT 有本质区别：

特性GACT / GACT-XTALCO
内存固定 O(T2)O(T^2)固定 O(M×Bmax⁡)O(M \times B_{\max})
切 tile固定大小、固定重叠按 frontier 和 marker 切
选择下一个起点贪心选边界最高分利用 traceback 收敛，找唯一汇聚点
是否保证最优否是（在 banding 约束下）
对参数敏感是低
对输入敏感是低
与完整算法等价不保证保证

TALCO 的核心创新是：

不贪心选边界点，而是等待所有回溯路径在 marker 上收敛到同一个格子，再从这个格子开始回溯。
这样就能保证每个 tile 的比对与完整算法完全一致。

因此，TALCO 可以替换 GACT 的贪心 tiling 策略，在保持固定内存的同时，保证比对质量。

论文中 TALCO-XDrop 比 GACT-X 快了 1.1×1.1\times，同时产生更高质量的比对，部分原因就是 GACT-X 有约 37% 的冗余计算，而 TALCO 利用快速收敛减少了冗余。

10. 一句话总结​

GACT 是第一个用于长序列比对的 tiling 启发式：它把 DP 矩阵切成固定大小、互相重叠的 tile，每个 tile 在片上计算，计算完后贪心地选择边界最高分点作为下一个 tile 的起点，从而把内存固定在 O(T2)O(T^2)，实现任意长序列的硬件加速。但它不保证最优，对参数和输入敏感。TALCO 继承了 tiling 的固定内存优点，但用 traceback 收敛替代贪心选择，保证了在 banding 约束下的最优性。