Skip to main content

2.3 Banding technology

Banding 的核心思想是：

不填整个 m×nm \times n 的 DP 矩阵，只计算主对角线附近一条“带子”里的格子。
因为真正的最优比对通常不会偏离主对角线太远。

Banding 技术有很多种，论文里重点提到的是 X-Drop 和 WFA-Adapt。下面按类别整理。

1. 静态/固定对角线带​

最朴素的 banding。

  • 以主对角线 k=i−j=0k = i - j = 0 为中心；
  • 只计算满足 ∣i−j∣≤w|i-j| \le w 的格子；
  • ww 是带宽，固定或预先设定。

矩阵形状像一条沿着主对角线前进的带子。
时间复杂度从 O(mn)O(mn) 降到 O(nw)O(nw)。

缺点：

  • 如果真实差异导致最优路径偏离主对角线超过 ww，就会丢结果；
  • ww 不好选，太大失去加速意义，太小质量下降。

代表：

  • 经典 banded Needleman-Wunsch / Smith-Waterman；
  • 一些短读段比对工具。

2. Ukkonen 的指数增长带​

Ukkonen 算法 [60] 是一种更聪明的 banding。

  • 它仍然只考虑主对角线附近的格子；
  • 但带宽不是固定，而是指数增长；
  • 保证最终结果和完整 DP 等价；
  • 平均运行时间 O(ns)O(ns)，其中 ss 是两条序列的编辑距离。

因为编辑距离 ss 通常远小于 nn，所以平均很快。
但它主要用于 Levenshtein 距离，打分方式比较受限。

后续发展：

  • Myers 的 BitVector 算法 [61]：用位并行加速 Ukkonen；
  • Edlib [48]：在 Ukkonen/Myers 基础上加入 traceback 和更多比对选项。

3. X-Drop：自适应 banding​

论文里最常提到的 banding 技术。

核心：

  • 按反对角线或 wavefront 计算 DP；
  • 维护当前最高分 Hmax⁡H_{\max}；
  • 如果某个格子分数满足：
score<Hmax⁡−X\text{score} < H_{\max} - X

就剪掉，不再计算。

XX 是用户参数：

  • XX 越大，带越宽，越安全，但越慢；
  • XX 越小，带越窄，越快，但可能丢最优。

优点：

  • 动态适应序列差异；
  • 实现简单；
  • 被 BLAST、minimap2、Libgaba 等广泛采用。

缺点：

  • 不保证最优；
  • 内存仍随序列长度线性增长；
  • 对 XX 敏感。

代表：

  • BLAST [34]；
  • minimap2 [5]；
  • Libgaba [47]；
  • GACT-X [8] 把 X-Drop 和 tiling 结合。

4. WFA-Adapt：WFA 中的自适应 banding​

WFA-Adapt（WFAA）[38] 是 WFA 库里的启发式版本。

WFA 的三角矩阵：

  • 行 = 分数 ss；
  • 列 = 对角线 kk。

WFA-Adapt 的做法：

  • 每一行只保留在 kmin⁡k_{\min} 和 kmax⁡k_{\max} 之间的对角线；
  • 丢弃“落后太多”的外侧对角线；
  • 根据最远到达位置动态调整 kmin⁡k_{\min} 和 kmax⁡k_{\max}。

优点：

  • 适合 WFA 的波前推进；
  • 在序列差异小的时候非常快；
  • 支持 affine gap。

缺点：

  • 也是启发式，不保证最优；
  • 参数和打分方式影响大；
  • 长而 noisy 的比对内存仍然可能很大。

代表：

  • WFA-Adapt [38]；
  • TALCO-WFAA 就是把 TALCO tiling 作用在 WFA-Adapt 上。

5. 其他 banding / 相关技术​

5.1 GenASM​

  • 基于 Bitap 算法；
  • 使用类似 GACT 的 tiling 策略；
  • 也做 banding，但不保证最优。

5.2 GACT-X​

  • GACT 的扩展；
  • 在每个 tile 内部使用 X-Drop banding；
  • 是 tiling + banding 的结合，不是单纯 banding。

5.3 Scrooge​

  • 使用固定 tile 和 banding 参数；
  • 也是启发式，不保证最优。

5.4 两段式 affine gap + X-Drop​

  • minimap2 使用 two-piece affine gap；
  • 需要 5 个 DP 矩阵；
  • 结合 X-Drop banding。

6. 对比表​

技术类型是否保证最优代表工具
固定对角线带静态 banding否经典 banded NW/SW
Ukkonen 指数带精确 banding是（在编辑距离下）Ukkonen, Myers, Edlib
X-Drop自适应 banding否BLAST, minimap2, Libgaba
WFA-Adapt自适应 banding否WFA-Adapt, WFA2-lib
GACT-Xtiling + X-Drop否Darwin-WGA
TALCOtiling + 收敛，不是 banding是（在 banding 约束下）TALCO-XDrop, TALCO-WFAA

7. 和 TALCO 的关系​

论文强调：

  • X-Drop 和 WFA-Adapt 都是 banding 技术；
  • 它们降低内存和计算，但不保证最优；
  • TALCO 不是替代 banding，而是 在 banding 约束下做安全 tiling；
  • 所以 TALCO-XDrop 保证和完整 X-Drop 结果一致；
  • TALCO-WFAA 保证和完整 WFA-Adapt 结果一致。

一句话：

Banding 负责缩小搜索空间，TALCO 负责把缩小后的空间安全地切成 tile。