Smith-Waterman 算法是一种用于生物信息学的局部比对算法,由 Temple Smith 和 Michael Waterman 在1981年提出。它主要用于找出两个DNA或蛋白质序列中最相似的部分。
该算法的基本思想是通过比较两个序列中的每一个字符,来计算它们的相似度得分。这个得分可以是基于字母替换(例如A到T在DNA中是一个合理的替换)的得分,也可以是基于其他特征(如氨基酸的化学性质)的得分。然后,算法会使用一个称为“子矩阵”的方法来追踪最高的得分路径。
具体来说,算法首先创建一个二维表格,其中行和列分别对应两个要比较的序列。然后,对于表格中的每一个单元格,算法都会计算出其左上角、上方和左侧单元格的得分,并选择最高得分作为当前单元格的得分。同时,如果当前单元格的得分低于某个阈值,那么就将其设置为0,以避免低质量的匹配影响结果。
最后,算法会回溯到最高得分的单元格,沿着得分最高的路径一直回溯到起点,从而得到两个序列中最相似的部分。
总的来说,Smith-Waterman 算法是一种强大的工具,可以帮助生物学家找到基因或蛋白质序列中的相似性,从而推断出它们可能的功能或进化关系。