Smith–Waterman alignment
Local alignment of two sequences, with the filled scoring matrix and traceback path.
Local alignment of two sequences, with the filled scoring matrix and traceback path.
The Smith–Waterman algorithm (1981) finds the optimal local alignment of two sequences: the best-matching segment of the first against the best-matching segment of the second. Everything outside that segment is ignored, which is what you want when only a domain, an exon, a primer site or a shared motif is expected to be similar. It is a modification ofNeedleman–Wunsch and, like it, is guaranteed to find the best alignment for the scoring scheme you set.
Write sequence 1 down the side and sequence 2 across the top, with an extra row and column for the empty prefix. The first row and the first column are all zero, not a growing gap penalty, because an alignment may start anywhere.
The zero in the maximum is the whole difference from the global algorithm. A cell that would go negative is set to zero instead, which means "start a fresh alignment here" and stops a poor stretch from being carried along. In this tool the mismatch and gap values are entered as penalties, so a penalty of 2 means a score of −2. Tap any cell to see the four candidate values it was chosen from.
The best local alignment ends at the highest cell anywhere in the matrix, not at the bottom-right corner. Start there and step back to the neighbour that produced each value, as in the global algorithm, until you reach a cell holding zero. That cell is where the alignment begins. The score of the alignment is the value of the cell you started from, and the path between the two cells gives the aligned segment and its coordinates in both sequences. If several cells share the highest score, the tool reports how many there are and traces back from the first of them.
With match +3, mismatch −3 and gap −2 (the "Try an example" input) the highest cell in the matrix holds 13, at row 6 and column 7. Tracing back from it to the first zero gives
seq1 2 GTT-AC 6
||| ||
seq2 2 GTTGAC 7Five matches score 5 × 3 = 15 and one gap column costs −2, so the alignment scores 13, with an identity of 5 of 6 columns, or 83.3 %. The aligned region is bases 2 to 6 of TGTTACGG and bases 2 to 7 of GGTTGACTA; the flanking T, the leading G and the trailing CGG and TA are left out of the alignment entirely. A global alignment of the same pair would have to include them and would score far less.
The algorithm does not care about the alphabet, only the scoring. This page scores every pair of characters as a match or a mismatch, which suits DNA and RNA and is the form taught in courses. Protein comparisons should be scored with a substitution matrix so that conservative replacements cost less than radical ones: thepairwise protein alignment uses BLOSUM62 with affine gaps. Substitution matrices are explained under thescoring matrix calculator, andidentity and similarity reports percent identity for an alignment you already have.
It finds the highest-scoring local alignment of two sequences: the pair of subsequences, one from each, that align best. The ends of the sequences are free, so unrelated flanks are simply left out. It is the same dynamic programming as Needleman–Wunsch with two changes, a floor of zero in every cell and a traceback that starts at the best cell and stops at the first zero.
Use local alignment when only part of the two sequences is expected to match: a domain inside a long protein, a primer or probe inside a template, an exon in a genomic region, or two sequences of very different length. Use global alignment when both sequences are the same thing end to end, for example two alleles of one gene.
A negative running score would drag the alignment through a badly matching stretch to reach a good one further along. Cutting the score at zero ends the alignment there instead and lets a new one start, which is exactly what makes the algorithm local. The zero cells are where an alignment may begin.
No. Smith–Waterman is exact: it is guaranteed to find the best local alignment for the scoring scheme, at a cost proportional to the product of the two lengths. BLAST and FASTA are heuristics that look for short word matches first and extend only those, which is far faster on a database but can miss an optimal alignment. SSEARCH and the Waterman–Eggert variant run the full algorithm.
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.