Skip to main content

2.1 BSW

Banded Smith-Waterman（BSW）可以理解为 “带状的 Smith-Waterman 算法”。它是在经典 Smith-Waterman（SW）序列比对算法基础上，加了一个“带状区域”限制，从而大幅减少计算量。论文里 BSW 主要用于 短读测序的 read alignment（读段比对），也就是把一条测序读段和参考基因组序列进行局部相似性比对。

下面按层次解释。

1. BSW 要解决什么问题？​

在基因组测序中，测序仪产生的 reads 是一小段 DNA 序列，比如 100–150 bp。参考基因组是已知的长序列。
read alignment 的目标是：这条 read 来自参考基因组的哪个位置？它和参考序列有多相似？

由于测序错误、真实变异、插入、缺失等原因，read 和参考序列不会完全一样。所以需要一种算法，允许：

  • 错配（mismatch）
  • 插入（insertion）
  • 缺失（deletion）

并且找出它们之间最相似的局部区域。Smith-Waterman 就是做这件事的经典动态规划算法。

2. Smith-Waterman 的基本思想​

Smith-Waterman 是一种 局部序列比对 算法。它不要求两条序列从头比到尾，而是寻找两条序列中得分最高的局部相似片段。

它用一个二维 DP 表来记录相似性得分。表中的每个单元格通常记作：

H(i,j)H(i,j)

表示：序列 XX 的前 ii 个字符和序列 YY 的前 jj 个字符之间，某个局部比对的最大相似性得分。

为了处理插入和缺失，Smith-Waterman 通常还会维护两个辅助矩阵：

  • E(i,j)E(i,j)：表示以插入结束的得分；
  • F(i,j)F(i,j)：表示以缺失结束的得分。

论文中说 BSW 计算三个矩阵 H、E、F，对应三种编辑类型：

  • match：匹配；
  • insertion：插入；
  • deletion：缺失。

其中：

  • SS 是碱基 X(i)X(i) 和 Y(j)Y(j) 之间的相似性得分；
  • H(i,j)H(i,j) 表示子串 X(0,i)X(0,i) 和 Y(0,j)Y(0,j) 的相似性得分；
  • 打分通常使用 affine-gap penalty，也就是“打开一个 gap 罚一次，延长 gap 再按长度罚”的机制。

一个典型的 Smith-Waterman affine-gap 递推形式大致是：

H(i,j)=max⁡{0, H(i−1,j−1)+S(X(i),Y(j)), E(i,j), F(i,j)}H(i,j)=\max\{0,\ H(i-1,j-1)+S(X(i),Y(j)),\ E(i,j),\ F(i,j)\} E(i,j)=max⁡{H(i−1,j)−α, E(i−1,j)−β}E(i,j)=\max\{H(i-1,j)-\alpha,\ E(i-1,j)-\beta\} F(i,j)=max⁡{H(i,j−1)−α, F(i,j−1)−β}F(i,j)=\max\{H(i,j-1)-\alpha,\ F(i,j-1)-\beta\}

这里 α\alpha 是 gap opening 罚分，β\beta 是 gap extension 罚分。
论文 Figure 2a 展示的就是类似的目标函数。

3. 为什么叫“Banded”？​

标准 Smith-Waterman 要填满整个 m×nm \times n 的 DP 表，复杂度是 O(mn)O(mn)。
但在实际 read alignment 中，真正合理的比对路径通常不会偏离主对角线太远。也就是说，如果 read 和参考序列大部分是对应的，那么插入和缺失的总数不会特别大。

于是 Banded Smith-Waterman 只计算主对角线附近的一条“带”，而不是整个矩阵。

论文中说：

BSW is applied with a maximum of ww insertions or deletions, illustrated as the region between black cells in Figure 2a.

意思是：只允许最多 ww 个插入或缺失，因此只计算满足 ∣i−j∣≤w|i-j| \le w 的单元格。
Figure 2a 中的黑色格子就是这条带状区域。白色格子不计算，灰色格子是已经算过的，绿色格子是当前波前正在并行计算的。

这样做的好处是：

  • 计算量从 O(mn)O(mn) 降到大约 O(w⋅max⁡(m,n))O(w \cdot \max(m,n))；
  • 内存访问也大幅减少；
  • 更适合硬件并行加速。

4. 论文中 BSW 的具体特征​

论文 Table 1 给出了 BSW 的特征：

特征值
维度2D DP 表
大小约 100×60100 \times 60
依赖最后 2 个 wavefront
精度8-bit / 16-bit 整数

解释一下：

  • 2D DP 表：因为要同时沿 read 和 reference 两个方向递推；
  • 约 100×60100 \times 60：短读比对中，read 长度约 100，参考窗口约 60，所以表不大；
  • 依赖最后 2 个 wavefront：DP 表中同一条反对角线上的单元格可以并行计算，因为它们只依赖前两个波前的数据，这为 systolic array 提供了并行性；
  • 8-bit / 16-bit 整数：BSW 不需要浮点，整数运算就够。短序列常用 8-bit，长一点可能需要 16-bit。整数精度使硬件更简单、更省面积。

论文评估时，BSW 使用 8-bit SIMD，四个 DP 表映射到四个 SIMD lane，并行度很高。

5. GenDP 如何加速 BSW？​

GenDP 把 BSW 的 2D DP 表映射到 PE 阵列上：

  • 每一行映射到同一个 PE；
  • 目标序列元素静态存在 PE 中；
  • query 序列流经 PE；
  • 每个单元格依赖左、上、左上三个邻居；
  • 左边结果存在 PE 内，上方和对角线结果从上一个 PE 传过来；
  • FIFO 连接首尾 PE，实现跨行依赖传递。

因为 BSW 的依赖模式很规则，带状区域又进一步缩小了计算范围，所以它非常适合用 systolic array 做波前并行。GenDP 还支持 8-bit SIMD，让四个 DP 表同时计算，提高吞吐。

6. 一句话理解 BSW​

Banded Smith-Waterman 就是“只在对角线附近计算”的 Smith-Waterman 局部比对算法。
它允许少量插入、缺失和错配，用整数打分，在二维 DP 表上按波前并行推进，是短读测序 read alignment 中最核心的动态规划 kernel 之一。论文用它来代表规则、带状、整数精度的 DP 负载，并展示 GenDP 对这类负载的加速能力。