就全局最优序列比对而言，Needleman-Wunsch 和 Hirschberg 的算法仍然是最先进的吗？或者这些算法自发布以来是否有任何改进，或者任何更新的算法？
全局最优序列比对算法
计算科学
算法
计算生物学
2021-11-29 00:52:34
1个回答
根据 Wing-Kin Sung 的优秀“Algorithms in Bioinformatics”（2010，pp 30-39），最快的算法是 Masek 和 Paterson 在 1980 年发现的，可以解决全局对齐问题时间，这仅比 Needleman-Wunsch 算法好一点：
WJ 马塞克和帕特森女士。1980. “计算字符串编辑距离的更快算法。” 计算机与系统科学杂志20(1):18-31。
Sung 的书中有一个简短但写得很好的关于全球一致性的部分。