Skip to main content

2.1 Needleman-Wunsch and Smith-Waterman algorithms

一句话概括：Needleman-Wunsch（NW）做全局比对，Smith-Waterman（SW）做局部比对；两者都是动态规划，先填一个 m×nm\times n 的分数矩阵，同时记录每个格子的“回溯指针”，最后沿指针倒着走，得到最优比对。

1. 先理解动态规划矩阵​

设参考序列 R=r1r2…rmR=r_1r_2\dots r_m，查询序列 Q=q1q2…qnQ=q_1q_2\dots q_n。

我们建一个矩阵，行对应 RR，列对应 QQ。格子 (i,j)(i,j) 表示：
“用 RR 的前 ii 个字符和 QQ 的前 jj 个字符做比对，能达到的最优分数。”

每个格子有三种可能的来源：

  • 对角线：RiR_i 和 QjQ_j 对齐，可能是匹配，也可能是错配。
  • 上方：RiR_i 和空格对齐，相当于在 QQ 中插入一个 gap。
  • 左方：空格和 QjQ_j 对齐，相当于在 RR 中插入一个 gap。

每个格子除了存分数，还存一个指针，指向“最优分数是从哪个方向来的”。这个指针就是论文里说的 traceback pointer。最后从终点沿指针往回走，就得到比对路径。

2. Needleman-Wunsch：全局比对​

NW 的目标是：把两条完整序列从头比到尾。

打分​

常用：

  • 匹配：+2+2 或 +1+1
  • 错配：−1-1
  • gap：−1-1

论文图 2 用的就是：match=2，mismatch=-1，gap=-1。

初始化​

NW 要求全局比对，所以第一行和第一列不能随便为 0，而要表示“一直插 gap”的代价：

F(0,0)=0F(0,0)=0 F(i,0)=i⋅gF(i,0)=i\cdot g F(0,j)=j⋅gF(0,j)=j\cdot g

其中 gg 是 gap 罚分。比如 g=−1g=-1，则第一行是 0,−1,−2,…0,-1,-2,\dots。

递推公式​

F(i,j)=max⁡{F(i−1,j−1)+s(Ri,Qj)F(i−1,j)+gF(i,j−1)+gF(i,j)=\max \begin{cases} F(i-1,j-1)+s(R_i,Q_j)\\ F(i-1,j)+g\\ F(i,j-1)+g \end{cases}

其中 s(Ri,Qj)s(R_i,Q_j) 是匹配或错配分数。

解释：

  • F(i−1,j−1)+sF(i-1,j-1)+s：RiR_i 和 QjQ_j 对齐。
  • F(i−1,j)+gF(i-1,j)+g：RiR_i 对 gap。
  • F(i,j−1)+gF(i,j-1)+g：QjQ_j 对 gap。

回溯​

填完矩阵后，从右下角 F(m,n)F(m,n) 开始，沿指针一直回溯到左上角 F(0,0)F(0,0)。
这样得到的比对覆盖两条完整序列。

特点：

  • 全局最优。
  • 如果两条序列只有中间一小段相似，NW 仍然会强行把两端也比对，可能插入很多 gap。
  • 时间复杂度和空间复杂度都是 O(mn)\mathcal{O}(mn)。

3. Smith-Waterman：局部比对​

SW 的目标是：只找两条序列中最相似的那一段子序列进行比对。

初始化​

SW 的第一行和第一列全部为 0：

H(i,0)=0,H(0,j)=0H(i,0)=0,\quad H(0,j)=0

这表示：局部比对可以从任意位置重新开始。

递推公式​

H(i,j)=max⁡{0H(i−1,j−1)+s(Ri,Qj)H(i−1,j)+gH(i,j−1)+gH(i,j)=\max \begin{cases} 0\\ H(i-1,j-1)+s(R_i,Q_j)\\ H(i-1,j)+g\\ H(i,j-1)+g \end{cases}

关键区别是多了那个 00。
它的意思是：如果当前分数变成负数，不如从这里重新开始一段新的局部比对。

回溯​

先找到整个矩阵中的最大值：

Hmax⁡=max⁡i,jH(i,j)H_{\max}=\max_{i,j}H(i,j)

然后从这个最大分数格子开始，沿指针回溯，直到遇到某个 H(i,j)=0H(i,j)=0 的格子停止。
这段路径就是局部最优比对。

特点：

  • 只输出最相似的局部片段。
  • 适合找保守区域、结构域、相似片段。
  • 同样时间、空间复杂度为 O(mn)\mathcal{O}(mn)。

4. 一个极简例子​

设：

  • R=AGR=AG
  • Q=AGQ=AG
  • match =+1=+1，mismatch =−1=-1，gap =−1=-1

NW 矩阵​

空AG
空0-1-2
A-110
G-202

从右下角 22 回溯：
(2,2)→(1,1)→(0,0)(2,2)\to(1,1)\to(0,0)，都是对角线，所以比对为：

A G
A G

SW 矩阵​

空AG
空000
A010
G002

最大值是 22，从它回溯到 0，同样得到：

A G
A G

如果两条序列是 TTAGCC 和 GGAGTT，SW 会倾向于只输出中间的 AG 局部比对，而 NW 会强制把两端也比对，插入很多 gap。

5. NW 和 SW 的核心区别​

项目Needleman-WunschSmith-Waterman
比对类型全局比对局部比对
初始化第一行/列累加 gap 罚分第一行/列全为 0
递推是否含 0不含含 0
回溯起点右下角 (m,n)(m,n)矩阵最大分数格子
回溯终点左上角 (0,0)(0,0)某个分数为 0 的格子
适用场景两条完整序列整体相似两条序列中只有局部相似

6. 和论文 TALCO 的关系​

论文第二节讲 NW 和 SW，是为了说明经典动态规划算法：

  1. 精度高，能给出最优比对；
  2. 但需要 m×nm\times n 的矩阵和 traceback 指针，内存和计算量都很大；
  3. 因此实际长序列比对常用 banding，比如 X-Drop，剪掉明显不可能最优的区域；
  4. 但 banding 后内存仍随序列长度增长，硬件加速困难；
  5. 所以又出现 tiling，把长比对切成小块；
  6. TALCO 的创新是：利用 traceback 指针的“收敛”现象——很多条回溯路径会在某个格子汇合。于是可以在 tile 边界找到一个确定点，保证分块计算仍然和完整比对结果一致。

所以，理解 NW 和 SW 的关键就是：

填分数矩阵 + 记录每个格子的最优来源指针 + 从终点沿指针回溯。

TALCO 后面利用的正是这些回溯指针的汇聚性质。