Needleman Wunsch 算法与蛮力相比如何？
How does the Needleman Wunsch algorithm compare to brute force?
我想知道如何量化 Needleman-Wunsch 算法（通常用于比对 nucleotide/protein 序列）的结果。
考虑一些固定的评分方案和两个不同长度的序列 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 算法的工作原理是慢慢地为原始链的片段建立最佳比对，然后慢慢地将那些较小的比对增长为较大的比对，并保证任何最佳比对都必须包含一个稍小的情况的最佳比对。
我认为您的问题归结为动态规划是否找到最优解，即保证y >= x。关于这个问题的讨论，我会提到可能比我聪明的人：
https://cs.stackexchange.com/questions/23599/how-is-dynamic-programming-different-from-brute-force
基本上，它说动态规划可能会产生最优结果，即与蛮力相同，但仅适用于满足 贝尔曼最优性原则 的特定问题。
根据 Needleman-Wunsch 的维基百科页面，该问题确实满足 贝尔曼最优原则:
https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm
具体来说：
The Needleman–Wunsch algorithm is still widely used for optimal global
alignment, particularly when the quality of the global alignment is of
the utmost importance. However, the algorithm is expensive with
respect to time and space, proportional to the product of the length
of two sequences and hence is not suitable for long sequences.
同一维基百科页面的其他地方也提到了最优性。
我想知道如何量化 Needleman-Wunsch 算法（通常用于比对 nucleotide/protein 序列）的结果。
考虑一些固定的评分方案和两个不同长度的序列 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 算法的工作原理是慢慢地为原始链的片段建立最佳比对，然后慢慢地将那些较小的比对增长为较大的比对，并保证任何最佳比对都必须包含一个稍小的情况的最佳比对。
我认为您的问题归结为动态规划是否找到最优解，即保证y >= x。关于这个问题的讨论，我会提到可能比我聪明的人：
https://cs.stackexchange.com/questions/23599/how-is-dynamic-programming-different-from-brute-force
基本上，它说动态规划可能会产生最优结果，即与蛮力相同，但仅适用于满足 贝尔曼最优性原则 的特定问题。
根据 Needleman-Wunsch 的维基百科页面，该问题确实满足 贝尔曼最优原则:
https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm
具体来说：
The Needleman–Wunsch algorithm is still widely used for optimal global alignment, particularly when the quality of the global alignment is of the utmost importance. However, the algorithm is expensive with respect to time and space, proportional to the product of the length of two sequences and hence is not suitable for long sequences.
同一维基百科页面的其他地方也提到了最优性。