Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 49 ยท Sequence Alignment

Global alignment: Needleman-Wunsch

Learn the Needleman-Wunsch global alignment algorithm: the dynamic programming recurrence, filling the score matrix, traceback, complexity and a Python implementation.

How do you find the best alignment of two sequences without trying every possibility? In 1970 Saul Needleman and Christian Wunsch published an answer that is still taught in every bioinformatics course: dynamic programming. The trick is to notice that the best alignment of two long sequences is built from the best alignments of shorter prefixes. By solving the small problems first and reusing their answers, a task with astronomically many candidates becomes a table-filling exercise that finishes in seconds.

A filled dynamic programming matrix for ACGTGA and AGTTA with the traceback path in pink and the resulting alignment
Caption: each cell holds the best score of aligning the prefixes ending there; the dotted pink path traces back the optimal alignment.

What you will learn

  • The idea of optimal substructure and why it permits dynamic programming.
  • The recurrence, initialization, fill order and traceback of Needleman-Wunsch.
  • The time and memory cost of the algorithm and when ties matter.
  • How to implement it in Python and how scoring parameters change the result.

Key terms

  • Global alignment: an alignment that covers both sequences from end to end.
  • Dynamic programming: solving a problem by combining solutions of overlapping subproblems, stored in a table.
  • Traceback: following the choices recorded during the fill backwards, from the last cell to the first.
  • Prefix: the first i letters of a sequence.
  • Optimal substructure: the best solution contains best solutions of its parts.

The idea: look only at the last column

Consider two sequences, a (length m) and b (length n). Whatever the best alignment is, its last column must be one of three kinds. Either the last letters of a and b are aligned with each other (a match or a mismatch), or the last letter of a is aligned to a gap, or the last letter of b is aligned to a gap. Whichever it is, what remains is an alignment of two shorter prefixes, and for the whole to be optimal that remainder must itself be optimal. That is optimal substructure.

Define H(i, j) as the best score of aligning the first i letters of a with the first j letters of b. Then:

Text
H(i, j) = max(
    H(i-1, j-1) + s(a_i, b_j),     # align a_i with b_j (match or mismatch)
    H(i-1, j)   + gap,             # a_i against a gap
    H(i,   j-1) + gap              # b_j against a gap
)

Here s is +1 for a match and -1 for a mismatch in our examples, and gap is -2. The boundary conditions come from aligning a prefix against nothing: H(i, 0) = i * gap and H(0, j) = j * gap. The answer, the score of the best global alignment, is H(m, n).

Filling the matrix by hand

Take a = ACGTGA down the side and b = AGTTA across the top. Row 0 is 0, -2, -4, -6, -8, -10 and column 0 is 0, -2, -4, -6, -8, -10, -12. Now fill cell (1, 1), where A meets A. The three options are the diagonal H(0,0) + 1 = 1, up H(0,1) - 2 = -4 and left H(1,0) - 2 = -4. The maximum is 1. For (2, 1), where C meets A, the diagonal is H(1,0) - 1 = -3, the up option is H(1,1) - 2 = -1 and the left option is H(2,0) - 2 = -6, so the cell is -1. Continue row by row, left to right. Every cell needs only its three neighbors to the upper left, so the fill order is guaranteed to work.

When you finish, the bottom-right cell holds 1. That is the score of the best global alignment under these parameters.

Traceback

The score alone is not the alignment. To recover the alignment, start at the bottom-right cell and ask which of the three options produced its value. If it came from the diagonal, add the pair a_i, b_j to the alignment and move diagonally. If it came from above, add a_i aligned to a gap and move up. If it came from the left, add b_j aligned to a gap and move left. Continue until you reach the top-left corner, then reverse what you collected (you built it from the end). For the example the path gives:

Text
A C G T G A
A - G T T A

Check the score: A/A is +1, C against a gap is -2, G/G is +1, T/T is +1, G/T is -1 and A/A is +1, a total of 1, matching the corner cell.

Sometimes two options give the same value; then more than one optimal alignment exists. Implementations choose by a fixed order (for example diagonal first), but you should know that "the" optimal alignment is often one of several equally good ones. Some tools can report them all.

Cost and refinements

The matrix has (m + 1)(n + 1) cells and each takes constant time, so the algorithm runs in O(mn) time. Memory is also O(mn) if you keep the whole matrix for the traceback. Aligning two 5,000-base sequences needs 25 million cells, which is fine; aligning two 3-billion-base human chromosomes this way is impossible, which is why genome aligners use heuristics. If only the score is needed, two rows suffice. Hirschberg's algorithm recovers the alignment itself in linear memory by divide and conquer. And with affine gap penalties, Gotoh's extension keeps three matrices (one for each way the alignment can end), still in O(mn) time.

Global alignment is right when the sequences are expected to be related along their whole length, such as two versions of the same gene. When they may share only a region (a domain in a long protein), the local alignment of the next lesson is the better tool.

Scores, ties and what the algorithm really optimizes

It is worth pausing on what the algorithm actually optimizes. It maximizes a sum of local scores, so the answer is exactly as good as your scoring scheme. With +1, -1 and -2 the algorithm trades one gap (-2) against two mismatches (-2), so it will happily insert a gap to rescue two matching bases. Change the gap penalty to -1 and you will see gaps appear in the example above, as the second code example demonstrates; make it -4 and the algorithm prefers mismatches. Neither answer is wrong; they answer different questions about how costly an insertion is compared with a substitution.

A second point concerns ties. When two predecessor cells give the same value, the traceback can follow either one, and both alignments have the same score. Production software often reports one at random or by a fixed rule, and a careful analysis checks whether the biological conclusion depends on the choice. Finally, remember that the matrix computes the best score for every pair of prefixes, not just the whole sequences. This by-product is useful: the last row and column tell you how well each prefix of one sequence aligns with the whole other sequence, which is the starting point for semi-global alignment used in read mapping.

Common misconceptions

  • "The algorithm tries every alignment." It does not; it reuses the answers of smaller subproblems.
  • "The traceback is unique." Ties produce several equally optimal alignments.
  • "Global alignment is always the right choice for two homologous proteins." If only a domain is shared, forcing end-to-end alignment adds meaningless gaps and mismatches.
  • "The matrix values are scores of single cells." Each cell is the best score for two whole prefixes.

Try it

Python Needleman-Wunsch in Python

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Python Heat map of the matrix with traceback

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Interactive aligner

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does H(i, j) represent in Needleman-Wunsch?

    Each cell holds the optimal score for two prefixes, built from smaller cells.
  2. 2. What is the time complexity of Needleman-Wunsch for sequences of length m and n?

    There are (m+1)(n+1) cells, each computed in constant time.
  3. 3. How are the first row and column initialized with a linear gap penalty g?

    Aligning a prefix against nothing costs one gap per letter, so H(i,0) = ig and H(0,j) = jg.
  4. 4. In the traceback, a move straight up from cell (i, j) means:

    Moving up consumes a letter of a (the row sequence) without consuming one of b, so it is paired with a gap.
  5. 5. When is global alignment a poor choice?

    Forcing an end-to-end alignment adds meaningless gaps and mismatches when only a region is shared.

Summary

  • Needleman-Wunsch finds the best global alignment by dynamic programming over prefixes.
  • Each cell is the maximum of a diagonal, an up and a left option; the first row and column are multiples of the gap penalty.
  • Traceback recovers the alignment; ties can give several optimal alignments.
  • Time and memory are O(mn); heuristics are needed for very long sequences.

Next: Local alignment: Smith-Waterman