常用序列比对算法总结

1，全局比对算法
1.1 Needleman-Wunsch 算法 尝试找到两个完整的序列 S1 和 S2 之间的最佳比对。如S1=GCCCTAGCG S2=GCGCAATG 如果设定每个匹配字符为1分，每个空格为-2分，每个不匹配为-1分，则下面的比对就是全局最优比对：S1’=GCCCTAGCG S2’=GCGC_AATG,连字符“_”代表空格。在 S2’ 中有五个匹配字符，一个空格（或者反过来说，在 S1’ 中有一个插入项），有三个不匹配字符。这样得到的分数是 (5×1) + (1×-2) + (3×-1) = 0，这是能够实现的最佳结果。
2，局部比对算法
2.1 Smith-Waterman 算法 不必对两个完整的序列进行比对；可以在每个序列中使用某些部分来获得最大得分。使用同样的序列 S1 和 S2，以及同样的得分方案，可以得到以下局部最优比对 S1’’ 和 S2’’：S1=GCCCTAGCG S2

常用序列比对算法总结最先出现在Python成神之路。