
_START_ARTICLE_
史密斯-沃特曼算法
_START_PARAGRAPH_
史密斯-沃特曼算法（Smith-Waterman algorithm）是一种进行局部序列比对（相对于全局比对）的算法，用于找出两个核苷酸序列或蛋白质序列之间的相似区域。该算法的目的不是进行全序列的比对，而是找出两个序列中具有高相似度的片段。_NEWLINE_该算法由坦普尔·史密斯和迈克尔·沃特曼于1981年提出。史密斯-沃特曼算法是尼德曼-翁施算法的一个变体，二者都是动态规划算法。这一算法的优势在于可以在给定的打分方法下找出两个序列的最优的局部比对（打分方法使用了置换矩阵和空位罚分）。该算法和尼德曼-翁施算法的主要区别在于该算法不存在负分（负分被替换为零），因此局部比对成为可能。回溯从分数最高的矩阵元素开始，直到遇到分数为零的元素停止。分数最高的局部比对结果在此过程中产生。在实际运用中，人们通常使用该算法的优化版本。
_START_SECTION_
历史
_START_PARAGRAPH_
生物学上一个基本问题是，一个基因或者蛋白是否和别的基因或者蛋白存在联系。蛋白质在序列层次的关联暗示了其同源性，同时暗示了它们可能有类似的功能。通过分析多个DNA或者蛋白质序列，我们可能会发现一些保守序列和区域。这种基因序列或者蛋白质序列之间关联性的分析就是通过序列比对来完成的。如今，人们完成了许多不同生物体的基因组分析，获得了大量的基因和蛋白质序列数据。序列比对能够向我们揭示某一生物体中蛋白质之间的关联以及蛋白质在不同生物体中的关联，从而进一步理解生命和进化。_NEWLINE_序列比对起源于1970年。Saul B. Needleman和Christian D. Wunsch于1970提出了一个启发式的同源算法，称为尼德曼-翁施算法。该算法使用迭代的方法计算出一个矩阵，从而达到全局比对的效果。一些其他的启发式分析方法也在70年代被提出。Sankoff，Reichert，Beyer等人提出了一些严谨的数学的算法用来分析序列。然而这些方法通常难以揭示序列的生物学意义。 Sellers提出了一套测量序列距离的方法。沃特曼等于1976年在该方法的基础上，增加了插入和删除任意长度片段的方法。该方法解决了如何用最小的基因突变的次数将一个序列转变成另一个序列的问题。之后，坦普尔·史密斯和迈克尔·沃特曼于1981年提出了史密斯-沃特曼算法，解决了局部比对问题。
_START_SECTION_
空位罚分
_START_PARAGRAPH_
当碱基对或残基对之间匹配会导致更低分数时，需要空位的引入，即让碱基或残基与空位匹配。空位罚分决定了插入或者删除的分值。最基本的空位罚分方式为每次插入或者删除的得分相同。然而在生物学上，两序列之间一般存在着具有不同相似度的区域。另外，单个基因突变事件可能导致一长串空位的插入。因此，一个连续的较长的空位优于多个分散的小的空位。虽然多个分散的小的空位可以产生更多匹配，但一个连续的较长的空位代表这个区域只在一个序列中出现，使用后者可以避免为了得到高分而过度匹配这段序列。实现该方法只需要引入空位起始罚分和空位延长罚分的概念。空位起始罚分通常高于空位延长罚分。例如EMBOSS Water的默认参数为空位起始罚分=10，空位延长罚分=0.5。_NEWLINE_实际应用中空位罚分方法有多种（参见空位罚分），此处详细介绍这两种最常见的方法。设为空位罚分函数，其中为空位长度：
_START_SECTION_
空位权值恒定模型
_START_PARAGRAPH_
该模型空位的罚分正比于空位的长度。为单个空位的罚分。使用该模型时，原史密斯-沃特曼算法可简化为：_NEWLINE_此时该算法步数为，和分别为两序列的长度。在对某一位置考虑空位罚分时，只需考虑相邻的上方的和左侧的位置，而不需考虑整列和整行。
_START_SECTION_
空位延伸罚分模型
_START_PARAGRAPH_
该模型考虑空位起始罚分和空位延长罚分，其中为开始空位的罚分，为每次延长空位的罚分。例如，一个长度为2的空位的罚分为。未经优化的该模型的算法步数为。Gotoh将该算法的步数优化至，然而，优化后的方法只能找出一个局部比对结果，并且并不保证能成功获得结果。Altschul进一步优化了Gotoh的算法，在保持复杂度不变的情况下解决了Gotoh算法的不足。Myers和Miller指出，Gotoh和Altschul的算法忽视了Hirschberg在1975年提出的在线性空间内进行序列比对的方法，并在改进的算法中运用了该方法。Myers和Miller的算法仅使用空间，为较短的序列的长度。
_START_SECTION_
空位罚分例子
_START_PARAGRAPH_
以两序列TACGGGCCCGCTAC和TAGCCCTATCGGTCA进行比对为例，分别考虑两种模型。_NEWLINE_当使用空位权值恒定模型时，即不考虑空位起始和延长的区别，得到如下结果（置换矩阵为DNAfull，空位起始和延长均为1.0，其他参数为默认）：_NEWLINE_TACGGGCCCGCTA-C||   | || ||| |TA---G-CC-CTATC_NEWLINE_总得分为39.0_NEWLINE_当使用空位延伸罚分模型时，设空位起始罚分为5.0，空位延长罚分为1.0时，得到如下结果：_NEWLINE_TACGGGCCCGCTA||   |||  |||TA---GCC--CTA_NEWLINE_总得分为27.0_NEWLINE_可以看出，空位延伸罚分模型虽然总分略低，但考虑空位起始罚分和空位延长罚分能够有效避免多个小的空位。