我想知道如何量化 Needleman-Wunsch 算法的结果（通常用于比对核苷酸/蛋白质序列）。
考虑一些固定的评分方案和两个不同长度S1和的序列S2。假设我们通过蛮力计算所有可能的对齐方式，S1并且得分最高的对齐方式有一个 score 。当然，这比 Needleman-Wunsch 方法的复杂性要高得多。S2x
当使用 Needleman-Wunsch 算法查找序列比对时，假设它有一个 score 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
具体来说：
Needleman-Wunsch 算法仍然广泛用于最佳全局对齐，特别是当全局对齐的质量至关重要时。然而，该算法在时间和空间方面成本高，与两个序列长度的乘积成正比，因此不适用于长序列。
在同一个维基百科页面的其他地方也提到了最优性。