The idea: align everything, or only the part that matches?

To compare two DNA strings, write one above the other and slide gaps (-) in so that equal letters line up. That is an alignment, and a score rates it: here +1 per match, −1 per mismatch and −2 per gap. A global alignment (the Needleman–Wunsch algorithm, 1970) lines up both strings from the first letter to the last. A local alignment (Smith–Waterman, 1981) looks for the best-scoring pair of substrings and ignores everything around them.

CCCGATTACACC against TTGATTACATTT. Globally every letter is aligned: 7 matches, 4 mismatches and 2 gaps give score −1. Locally only GATTACA over GATTACA is kept, score 7, and the C and T flanks are ignored.
The same pair of strings: the global alignment pays for the unrelated flanks, the local one keeps only the shared GATTACA.

The page runs both on the same two strings, side by side: the left matrix is global, the right one local. The same cell fills in both at the same step, so you can see exactly where they differ. Under each matrix the alignment is shown with | under a match, . under a mismatch and - for a gap.

One recurrence, three differences

Both algorithms fill a score matrix H: A runs down the rows, B across the columns, and H[i][j] is the best score of an alignment of the first i letters of A with the first j letters of B. Like edit distance, the last column of that alignment is one of three things, but here we take the maximum score instead of the minimum cost:

H[i][j] = max( H[i-1][j-1] + s(A[i], B[j]),    ↖ match +1 / mismatch −1
               H[i-1][j]   − 2,                 ↑ A[i] over a gap
               H[i][j-1]   − 2 )                ← a gap over B[j]
Needleman–Wunsch (global)Smith–Waterman (local)
bordersH[i][0] = −2i, H[0][j] = −2jall 0
each cellmax of the threemax of the three and 0
scorethe bottom-right cell H[m][n]the largest cell anywhere
tracebackfrom H[m][n] to H[0][0]from the largest cell until a cell is 0
The cell for G against C filled in both matrices. Globally the borders are 0, −2, −4, −6 and the cell is max(−2 − 1, −4 − 2, 1 − 2) = −1. Locally the borders are 0 and the cell is max(0, 0 − 1, 0 − 2, 1 − 2) = 0.
The same cell: the global matrix keeps the −1, the local matrix clamps it to 0 and drops the bad prefix.

The extra 0 means "start a new alignment here": a prefix that scores below zero only hurts, so local alignment throws it away. That is why local cells are never negative and why most of a local matrix is grey zeros when the strings are unrelated. (Demo: GATTACA vs GCATGCU)

Traceback: where it starts, where it stops

Each traceback step moves to a neighbour that produced the cell's value (↖ first, then ↑, then ←) and adds one column to the alignment, right to left. The global walk must reach the corner H[0][0], so every letter of both strings ends up in the alignment, with end gaps if the lengths differ. The local walk starts at the largest cell and stops at the first 0, so the alignment is a substring of A over a substring of B.

  • Shared motif in unrelated flanks: CCCGATTACACC and TTGATTACATTT share GATTACA. The local score is 7; the global score is only −1, because the flanks add mismatches and gaps. (Demo: shared motif)
  • Identical strings: the best local stretch is the whole string, so both answers are the same GATTACA, score 7. (Demo: identical strings)
  • Completely different: AAAAAAA and CCCC have no common letter. Global must still align them, −4 for mismatches and −6 for three gaps = −10; every local cell is 0, so the local alignment is empty. (Demo: completely different)

The scores decide what is found

A local alignment extends across a gap only if the matches on the other side pay for it. With match +1, the gap in CCGATTACACC vs TTGATACATT (−2) costs as much as two matches, so the local answer is just TACA (score 4). With match +2, GATTACA over GA-TACA scores 6 × 2 − 2 = 10 and wins. (Demo: match +2) Real tools use substitution matrices (BLOSUM, PAM) for proteins and affine gaps (open −10, extend −1) so one long gap is cheaper than many short ones.

Which one to use

questionuse
Two versions of the same gene, similar lengthglobal
Find a short motif or domain inside a long sequencelocal
Search a read against a whole genome databaselocal (BLAST is a fast heuristic for it)
Two strings that may share nothing at alllocal: score 0 says so honestly

Both take Θ(mn) time and space for the full matrix. Two rows are enough for the score alone, and Hirschberg's method recovers a global alignment in linear space.

See also Edit Distance, the same table with costs instead of scores, and Longest Common Subsequence, which is global alignment with match +1 and mismatches and gaps scoring 0.

What the page leaves out

Strings are limited to 12 letters so both matrices fit. The page leaves out affine gap penalties (Gotoh), substitution matrices such as BLOSUM62, semi-global ("glocal") alignment with free end gaps, listing every optimal alignment instead of one, the second-best local alignments, banded and linear-space versions, and heuristics like BLAST that skip most of the matrix.