Needleman–Wunsch algorithm

The Needleman–Wunsch algorithm, published by Saul Needleman and Christian Wunsch in 1970, was one of the first computer methods for comparing biological sequences. It produces a global alignment, matching two protein or nucleic acid sequences from their first residue to their last, and it is guaranteed to find the highest-scoring alignment for a chosen scheme of match rewards, mismatch costs and gap penalties.

It relies on dynamic programming, which solves a large problem by building up answers to smaller overlapping ones. One sequence is written across the top of a grid and the other down the side. Each cell receives the best score for aligning the two sequences up to that point, taken from one of three neighbors: the diagonal cell plus a match or mismatch score, or the cell above or to the left minus a gap penalty. When the grid is full, the bottom-right cell holds the optimal score, and tracing the chosen steps back to the top-left corner recovers the alignment.

The time and memory needed grow with the product of the two sequence lengths, which is fine for genes and proteins but too slow for searching large databases, where heuristic tools such as BLAST are used instead. The method suits related sequences of similar length; the Smith–Waterman algorithm adapts it to find local matches.