我想知道如何量化 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)，但仍然留有这个问题。
最佳答案
Needlman-Wunsch 总是会产生最佳答案 - 它比蛮力快得多，并且不会在此过程中牺牲准确性。它使用的关键见解是实际上没有必要生成所有可能的对齐方式，因为它们中的大多数包含错误的子对齐方式并且不可能是最佳的。 Needleman-Wunsch 算法的工作原理是缓慢地为原始链的片段建立最佳比对，然后使用保证任何最佳比对必须包含针对稍小的情况的最佳比对，将这些较小的比对缓慢增长为更大的比对。
关于string - Needleman Wunsch 算法与蛮力相比如何？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/40615299/