史密斯-沃特曼算法

史密斯-沃特曼算法（英語：Smith–Waterman algorithm）是一种进行局部序列比对（相对于全局比对）的算法，用于找出两个核苷酸序列或蛋白质序列之间的相似区域。这个算法不是直接考虑全序列的相似性，而是把所有可能长度的片段进行对比，以找出具有高相似度的片段。

该算法由坦普尔·史密斯和迈克尔·沃特曼于1981年提出。史密斯-沃特曼算法是内德曼-文施算法的一个变体，二者都是动态规划算法。这一算法的优势在于可以保证在给定的打分方法下找出两个序列的最优的局部比对（打分方法使用了置换矩阵和空位罚分）。该算法和内德曼-文施算法的主要区别在于该算法不存在负分（负分被设为零），因此局部比对成为可能。回溯从分数最高的矩阵元素开始，直到遇到值为零的元素停止。此过程中，分数最高的局部比对结果就产生了。在实际运用中，人们通常使用该算法的优化版本。

解释

建立矩阵 $H$ :

$H(i,0)=0,\;0\leq i\leq m$

$H(0,j)=0,\;0\leq j\leq n$

$H(i,j)=\max {\begin{Bmatrix}0\\H(i-1,j-1)+\ s(a_{i},b_{j})&{\text{Match/Mismatch}}\\\max _{k\geq 1}\{H(i-k,j)+\ W_{k}\}&{\text{Deletion}}\\\max _{l\geq 1}\{H(i,j-l)+\ W_{l}\}&{\text{Insertion}}\end{Bmatrix}},\;1\leq i\leq m,1\leq j\leq n$

其中，

$a,b$ = Strings over the Alphabet $\Sigma$
$m={\text{length}}(a)$
$n={\text{length}}(b)$
$s(a,b)$ 基于字母a,b的打分方法
$H(i,j)$ – is the maximum Similarity-Score between a suffix of a[1...i] and a suffix of b[1...j]
$W_{i}$ is the gap-scoring scheme