史密斯-沃特曼算法 Smith–Waterman algorithm
史密斯-沃特曼算法(Smith–Waterman algorithm)是一种进行局部串行比对(相对于全局比对)的算法,用于找出两个核苷酸串行或蛋白质串行之间的相似区域。该算法的目的不是考虑全串行的比对,而是找出两个串行中具有高相似度的片段。
该算法由坦普尔·史密斯(Temple F. Smith)和迈克尔·沃特曼(Michael S. Waterman)于1981年提出。史密斯-沃特曼算法是内德曼-文施算法的一个变体,二者都是动态规划算法。这一算法的优势在于可以保证在给定的打分方法下找出两个串行的最优的局部比对(打分方法使用了置换矩阵和空位罚分)。该算法和内德曼-文施算法的主要区别在于该算法不存在负分(负分被替换为零),因此局部比对成为可能。回溯从分数最高的矩阵元素开始,直到遇到分数为零的元素停止。分数最高的局部比对结果在此过程中产生。在实际运用中,人们通常使用该算法的优化版本。