string - Needleman Wunsch 算法与蛮力相比如何？

Question

我想知道如何量化 Needleman-Wunsch 算法(通常用于比对核苷酸/蛋白质序列)的结果。

考虑一些固定的评分方案和两个不同长度的序列 S1 和 S2。假设我们通过蛮力计算了 S1 和 S2 的所有可能对齐方式，得分最高的对齐方式的得分为 x。当然，这比 Needleman-Wunsch 方法复杂得多。

当使用 Needleman-Wunsch 算法查找序列比对时，假设它有一个分数 y。

将 r 视为通过 Needleman-Wunsch 为两个随机序列 R1 和 R2 生成的分数。

x 与 y 相比如何？对于两个已知同源序列，y 是否总是大于 r？

总的来说，我确实理解我们使用 Needleman-Wunsch 算法来显着加快序列比对(与蛮力方法相比)，但不理解随之而来的准确性成本(如果有的话)。我尝试阅读原始论文(Needleman & Wunsch，1970 年)，但仍有这个问题。

Answer 1

Needlman-Wunsch 总能得出最佳答案 - 它比蛮力法快得多，并且不会牺牲过程中的准确性。它使用的关键见解是实际上没有必要生成所有可能的比对，因为它们中的大多数包含错误的子比对并且不可能是最佳的。 Needleman-Wunsch 算法的工作原理是慢慢地为原始链的片段建立最佳比对，然后慢慢地将那些较小的比对增长为较大的比对，并保证任何最佳比对都必须包含一个稍小的情况的最佳比对。