Needleman–Wunsch alignment
Global alignment of two sequences, with the filled scoring matrix and traceback path.
Global alignment of two sequences, with the filled scoring matrix and traceback path.
The Needleman–Wunsch algorithm (1970) computes the optimal global alignment of two sequences: both are aligned over their whole length, and gaps are inserted so that the total score of matches, mismatches and gaps is as high as possible. It was the first application of dynamic programming to biological sequences. Instead of trying every possible alignment, it solves the problem for every pair of prefixes once and stores the answers in a matrix, which takes time proportional to the product of the two lengths.
Write sequence 1 down the side and sequence 2 across the top, with one extra row and column for the empty prefix. Cell F(i, j) holds the best score for aligning the first icharacters of sequence 1 with the first j characters of sequence 2.
Here s(aᵢ, bⱼ) is the match score when the two characters are equal and the mismatch score otherwise, and gap is a negative number. The three terms correspond to the three ways an alignment can end: the two characters aligned to each other (diagonal move), aᵢ aligned to a gap (move down), or bⱼ aligned to a gap (move right). The bottom-right cell holds the score of the best global alignment. In this tool the mismatch and gap values are entered as penalties, so a penalty of 1 means a score of −1. Tap any cell of the matrix to see the three candidate values it was chosen from.
Start in the bottom-right cell and repeatedly step to a neighbour that produced the current value: a diagonal step writes aᵢ over bⱼ, a step up writes aᵢ over a gap, and a step left writes a gap over bⱼ. The walk ends in the top-left cell, and the columns read in reverse are the alignment. The small arrows in each cell mark every neighbour that gives the maximum. Where a cell has more than one arrow the path can fork, and every route is an equally good alignment. This tool follows the diagonal first, then up, then left, and counts the number of co-optimal alignments.
With match +1, mismatch −1 and gap −1 (the "Try an example" input), the first row and column are 0, −1, −2, … −7. Cell F(1, 1) compares G with G: the diagonal gives 0 + 1 = 1, and both gap moves give −1 − 1 = −2, so F(1, 1) = 1. Cell F(2, 2) compares C with A: the diagonal gives 1 − 1 = 0, up gives 0 − 1 = −1 and left gives 0 − 1 = −1, so F(2, 2) = 0. The bottom-right cell is 0, the optimal score. The traceback shown by the tool is
GCA-TGCU | | |.|. G-ATTACA
with 4 matches, 2 mismatches and 2 gap columns: 4 − 2 − 2 = 0, and an identity of 4/8 = 50 %. Two other alignments reach the same score, which the tool reports as "one of 3".
A linear penalty charges the same for every gap column. Real insertions and deletions usually span several residues in one event, so an affine penalty charges more for opening a gap than for extending it:
Affine scoring needs three matrices (Gotoh's algorithm): M for alignments ending in an aligned pair, X for those ending with a gap in sequence 2, and Y for those ending with a gap in sequence 1. In affine mode the matrix shown here is the maximum of the three in each cell, and tapping a cell lists the three values. With open equal to extend the result is identical to the linear model.
The algorithm is the same for any alphabet; only the scoring function changes. This page scores every pair of characters as match or mismatch, which is the usual choice for DNA and RNA and the form taught in courses. Protein alignments are normally scored with a substitution matrix so that conservative replacements such as I/L cost less than W/G. For that, use the pairwise protein alignment, which runs Needleman–Wunsch with BLOSUM62 and affine gaps. The matrices themselves are explained in thescoring matrix calculator, and theidentity and similarity calculator reports percent identity for an alignment you already have.
It finds the highest-scoring global alignment of two sequences, meaning both sequences are aligned from their first to their last character, with gaps inserted where needed. It does this by dynamic programming: a matrix is filled with the best score of every pair of prefixes, and the alignment is read off by tracing back from the bottom-right cell to the top-left cell.
The textbook scheme is match +1, mismatch −1, gap −1, which this tool uses by default. For DNA, BLAST-like schemes such as match +2, mismatch −3 with gap open −5 and gap extend −2 are common. The alignment depends on the ratio of the values, so change them and watch the matrix and the traceback path respond.
A cell of the matrix can reach its maximum from more than one neighbour. Every such tie is a fork in the traceback, and each route through the forks is an alignment with the same optimal score. The tool reports how many co-optimal alignments exist and shows one of them, preferring the diagonal, then a gap in sequence 2, then a gap in sequence 1.
With a linear penalty every gap column costs the same, so a gap of length k costs k × gap. With an affine penalty the first column of a gap costs the gap open penalty and each further column the smaller gap extend penalty, so a gap of length k costs open + (k − 1) × extend. Affine penalties favour one long gap over several short ones and need three matrices instead of one (Gotoh, 1982).
Time and memory grow with the product of the two lengths. The filled matrix is drawn when both sequences are 50 characters or shorter. The alignment itself is computed for up to 25 million cells, for example two sequences of 5,000 characters; beyond that the tool stops and asks for shorter input.