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