How does the Needleman Wunsch algorithm compare to brute force?

3
votes

I'm wondering how you can quantify the results of the Needleman-Wunsch algorithm (typically used for aligning nucleotide/protein sequences).

Consider some fixed scoring scheme and two sequences of varying length S1 and S2. Say we calculate every possible alignment of S1 and S2 by brute force, and the highest scoring alignment has a score x. And of course, this has considerably higher complexity than the Needleman-Wunsch approach.

When using the Needleman-Wunsch algorithm to find a sequence alignment, say that it has a score y.

Consider r to be the score generated via Needleman-Wunsch for two random sequences R1 and R2.

How does x compare to y? Is y always greater than r for two sequences of known homology?

In general, I do understand that we use the Needleman-Wunsch algorithm to significantly speed up sequence alignment (vs a brute-force approach), but don't understand the cost in accuracy (if any) that comes with it. I had a go at reading the original paper (Needleman & Wunsch, 1970) but am still left with this question.

2
stringalgorithmbioinformaticssequence-alignmentneedleman-wunsch
An algorithm that may return a non-optimal result for improved performance is called a heruistic (en.wikipedia.org/wiki/Heuristic). The Needleman-Wunsch returns an optimal result and so is not a herusitic (en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm). - RBarryYoung

2 Answers

5
votes

Needlman-Wunsch always produces an optimal answer - it's much faster than brute force and doesn't sacrifice accuracy in the process. The key insight it uses is that it's not actually necessary to generate all possible alignments, since most of them contain bad sub-alignments and couldn't possibly be optimal. The Needleman-Wunsch algorithm works by instead slowly building up optimal alignments for fragments of the original strands and then slowly growing those smaller alignments into larger alignments using the guarantee that any optimal alignment must contain an optimal alignment for a slightly smaller case.

2
votes

I think your question boils down to whether dynamic programming finds the optimal solution ie, garantees that y >= x. For a discussion on this I would refer to people who are likely smarter than me:

https://cs.stackexchange.com/questions/23599/how-is-dynamic-programming-different-from-brute-force

Basically, it says that dynamic programming will likely produce optimal result ie, same as brute force, but only for particular problems that satisfy the Bellman principle of optimality.

According to Wikipedia page for Needleman-Wunsch, the problem does satisfy Bellman principle of optimality:

https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm

Specifically:

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.

There is also mention of optimality elsewhere in the same Wikipedia page.