史密斯-沃特曼算法

史密斯-沃特曼算法（Smith–Waterman algorithm）是一种进行局部序列比对（相对于全局比对）的算法，用于找出两个核苷酸序列或蛋白质序列之间的相似区域。该算法的目的不是进行全序列的比对，而是找出两个序列中具有高相似度的片段。

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

算法

得分矩阵$H$的建立:

$H_{i0}=0,\;0\leq i\leq m$

$H_{0j}=0,\;0\leq j\leq n$

对于$1\leq i\leq m,1\leq j\leq n$，

$H_{ij}=\max {\begin{cases}0,\\H_{i-1,j-1}+s(a_{i},b_{j}),\\\max _{k\geq 1}\{H_{i-k,j}-\ W_{k}\},\\\max _{l\geq 1}\{H_{i,j-l}-\ W_{l}\}\end{cases}}$

其中:

• $a,b$ - 目标序列
• $m$ - $a$ 的长度
• $n$ - $b$ 的长度
• $s(a,b)$ - 基于置换矩阵的打分方法
• $W_{i}$ - 空位罚分方法
• $H_{ij}$ – 矩阵元素$H_{ij}$的得分

解释

史密斯-沃特曼算法通过字母的匹配，删除和插入操作，把两条未知的序列进行排列。实际上插入和删除都是引入空位的操作（在不同序列上）。序列1上某一位置的插入相当于在序列2上对应位置的删除。在实际计算中，只需要考虑何时引入空位即可。

该算法主要分两步，计算得分矩阵和寻找最优比对序列。可以简单描述为：

1. 确定置换矩阵及空位罚分方法。置换矩阵赋予每一碱基对或残基对匹配或错配的分数，相同或类似则赋予正值，不同或不相似赋予0分或者负分。空位罚分决定了插入或删除的分值。
2. 初始化得分矩阵。得分矩阵的长度和宽度分别为两序列的长度+1。其首行和首列所有元素均设为0。
3. 打分。对得分矩阵的每一元素进行从左到右、从上到下的打分，考虑匹配，删除和插入分别带来的结果，取最高值作为该元素的分值。如果分值低于0，则该元素分值为0。
4. 回溯。通过动态规划的方法，从得分矩阵的最大分值的元素开始回溯直至分数为0的元素。此过程可以重复，即完成首次回溯之后，从首次回溯区域之外的最高分元素开始回溯，以得到第二个局部相似片段。

置换矩阵

每一碱基对或残基对匹配或错配的分数通常用一矩阵表示，称为置换矩阵。最基本的置换矩阵为匹配则加分，错配则扣分。以核苷酸序列为例，若匹配为+1，错配为-1，则置换矩阵为：

	A	G	C	T
A	1	-1	-1	-1
G	-1	1	-1	-1
C	-1	-1	1	-1
T	-1	-1	-1	1

不同的碱基对或残基对可以有不同的分数以适应于特定的场合。

氨基酸序列比对的置换矩阵一般更加复杂。通常性质相似的残基对具有正分数，反之，不相似的具有负分数。此外，残基对的相似或不相似程度决定了分数的大小。参见PAM，BLOSUM。

空位罚分

当碱基对或残基对之间匹配会导致更低分数时，需要空位的引入，即让碱基或残基与空位匹配。空位罚分决定了插入或者删除的分值。最基本的空位罚分方式为每次插入或者删除的得分相同。然而在生物学上，两序列之间一般存在着具有不同相似度的区域。在这种情况下一个连续的较长的空位要比多个分散的小的空位要好，即使多个分散的小的空位可以产生更多匹配。这样这个大的空位就代表了这个区域只在一个序列中出现，避免了为了得到高分而过度匹配这段序列。实现该方法只需要引入空位起始罚分和空位延长罚分的概念。空位起始罚分通常远高于空位延长罚分。例如EMBOSS Water的默认参数为空位起始罚分=10，空位延长罚分=0.5。

以两序列TACGGGCCCGCTAC和TAGCCCTATCGGTCA进行比对为例，当空位起始罚分和空位延长罚分都为1.0时（置换矩阵为DNAfull，其他参数为默认），得到如下结果：

TACGGGCCCGCTA-C
||   | || ||| |
TA---G-CC-CTATC
总得分为39.0

当空位起始罚分为5.0，空位延长罚分为1.0时，得到如下结果：

TACGGGCCCGCTA
||   |||  |||
TA---GCC--CTA
总得分为27.0

得分矩阵

得分矩阵用以对两序列中两两位置进行打分。矩阵的长度和宽度分别为两序列长度+1。额外的首行和首列是为了让序列的末端可以和空位匹配。首行和首列均设为0。以CTCAA和GGTCA为例，初始得分矩阵为：

-	-	C	T	C	A	A
-	0	0	0	0	0	0
G	0
G	0
T	0
C	0
A	0

与内德曼-文施算法的比较

史密斯-沃特曼算法与内德曼-文施算法的三个区别：

	史密斯-沃特曼算法	内德曼-文施算法
初始化阶段	第一行和第一列全填充为 0	首行和首列需要考虑空位罚分
打分阶段	若得分为负，则分数为零	得分可以为负
回溯阶段	从最高分开始，回溯直至得分为 0	从右下角开始，回溯至左上角

其中打分阶段分数不为负是最重要的一点区别。它使得对序列局部的对比成为可能。当任何时候分数低于0，即表示此前的序列具有较低相似性；而此时将此元素分数设为0，即达到了“重设”的效果，使得从此位置开始的打分不受之前位置的影响。

释例

• 序列 1 = ACACACTA
• 序列 2 = AGCACACA
• $s(a,b)$ = +2，如果$a=b$（匹配）；-1，如果$a\neq b$（不匹配）
• $W_{i}=-1$

$H={\begin{pmatrix}&-&A&C&A&C&A&C&T&A\\-&\color {blue}0&0&0&0&0&0&0&0&0\\A&0&\color {blue}2&1&2&1&2&1&1&2\\G&0&\color {blue}1&1&1&1&1&1&0&1\\C&0&1&\color {blue}3&2&3&2&3&2&2\\A&0&2&2&\color {blue}5&4&5&4&4&4\\C&0&1&4&4&\color {blue}7&6&7&6&6\\A&0&2&3&6&6&\color {blue}9&8&8&8\\C&0&1&4&5&8&8&\color {blue}11&\color {blue}10&10\\A&0&2&3&6&7&10&10&10&\color {blue}12\end{pmatrix}}$

$T={\begin{pmatrix}&-&A&C&A&C&A&C&T&A\\-&\color {blue}0&0&0&0&0&0&0&0&0\\A&0&\color {blue}\nwarrow &\leftarrow &\nwarrow &\leftarrow &\nwarrow &\leftarrow &\leftarrow &\nwarrow \\G&0&\color {blue}\uparrow &\nwarrow &\uparrow &\nwarrow &\uparrow &\nwarrow &\nwarrow &\uparrow \\C&0&\uparrow &\color {blue}\nwarrow &\leftarrow &\nwarrow &\leftarrow &\nwarrow &\leftarrow &\leftarrow \\A&0&\nwarrow &\uparrow &\color {blue}\nwarrow &\leftarrow &\nwarrow &\leftarrow &\leftarrow &\nwarrow \\C&0&\uparrow &\nwarrow &\uparrow &\color {blue}\nwarrow &\leftarrow &\nwarrow &\leftarrow &\leftarrow \\A&0&\nwarrow &\uparrow &\nwarrow &\uparrow &\color {blue}\nwarrow &\leftarrow &\leftarrow &\nwarrow \\C&0&\uparrow &\nwarrow &\uparrow &\nwarrow &\uparrow &\color {blue}\nwarrow &\color {blue}\leftarrow &\leftarrow \\A&0&\nwarrow &\uparrow &\nwarrow &\uparrow &\nwarrow &\uparrow &\nwarrow &\color {blue}\nwarrow \end{pmatrix}}$

获得最优局部比对从矩阵中最高的元素$(i,j)$开始，根据建立矩阵的方向往回移动至$(i-1,j)$，$(i,j-1)$或$(i-1,j-1)$其中之一，如此反复，直到遇到分数为零的矩阵元素。

在此例子中，得分最高的元素位于矩阵$H$的(8,8)，回溯通过的路径为：(8,8)，(7,7)，(7,6)，(6,5)，(5,4)，(4,3)，(3,2)，(2,1)，(1,1) 和(0,0)。

回溯完成后，比对通过如下方法重建：从最后一个非零的元素开始（此例为(1,1)），通过回溯的路径到达$(i,j)$。对角线移动代表对两条序列进行比对（匹配或不匹配）。上下移动代表在序列1中插入空位（相当于删除序列2该位置，deletion）。左右移动代表在序列2中插入空位（insertion）。

该例的结果为：

序列 1 = A-CACACTA

序列 2 = AGCACAC-A

相关链接

• 生物信息学
• 序列比对
• 内德曼-文施算法
• 莱文斯坦距离
• BLAST

外部链接

• （英文）JAligner — 一个Java实现的史密斯-沃特曼算法的开源程序
• （英文）B.A.B.A. — 一个带源代码并且动态解释该算法的应用
• （英文）FASTA/SSEARCH — 欧洲生物信息研究所提供的在线服务
• （英文）diagonalsw — 一个C/C++实现的史密斯-沃特曼算法的程序，具有并行处理能力
• （英文）SSW — 一个C/C++实现的史密斯-沃特曼算法的程序，具有并行处理能力