Smith-Waterman 局部比对算法

1. 从全局到局部

Needleman-Wunsch（1970）的全局比对将两条序列从端到端对齐。但对许多生物学问题，序列只在局部区域相似（如共享功能结构域），全局比对会强行对齐不相似区域，结果误导。

Smith & Waterman 的局部比对算法只比对相似度最高的子序列片段，不相似的区域被重置为 0 而非计入负分。

一句话区别： 全局比对递推中负分向下传递，局部比对递推中负分被 0 取代——"忘记"不相似的区域。

H(i,j) = max{ 0, H(i-1,j-1) + s(a_i,b_j), E(i,j), F(i,j) } (1)

E(i,j) = max{ H(i,j-1) − q, E(i,j-1) − r } (2)

F(i,j) = max{ H(i-1,j) − q, F(i-1,j) − r } (3)

q = gap open 罚分，r = gap extension 罚分（通常 r < q）。

局部比对 DP 矩阵。H(i,j) = max{0, 对角+匹配, 插入, 删除}。最大分 4 → 回溯得最佳局部比对 "ACG" vs "ACG"。

O(mn) 时间，O(min(m,n)) 空间（优化后）。

BWA-MEM 不在全长参考上运行 SW（3Gb × 100bp 不可行），而是在种子附近的条带窗口内运行 banded DP：

场景	SW 类型	搜索空间
种子延伸	Banded affine-gap DP + Z-dropoff	种子 ±~100bp
Mate rescue	标准 SW + SSE2 向量化	[μ−4σ, μ+4σ] 窗口内

常用参数（BWA-MEM）： 匹配 +1，错配 -4，gap open -6，gap extension -1

Smith-Waterman 是理论最优（保证找到最佳局部比对），但在基因组规模需种子过滤 + 条带化来约束搜索空间。