Lesson 3 of 9
Module 4 · Comparing sequences
A grid filled one cell at a time finds the best alignment without trying every option. See how Needleman–Wunsch and Smith–Waterman work, then run both modes in Biopython and learn which question each one answers.
Finding the best alignment
Pairwise alignment: dot plots, scores and gaps gave every alignment a score. The task now is to find the alignment with the highest score. Trying every possibility is out of the question: for two sequences of a few hundred letters, the number of ways to place gaps is astronomically large. Yet a computer finds the best one in a fraction of a second. This lesson shows the trick with pictures rather than formulas, and then runs it in Biopython. You need Biopython, installed as in Why compare sequences: homology, similarity and identity.
The trick is to build the answer from smaller answers. Write one sequence down the side of a grid and the other across the top, as in a dot plot. Each cell will hold one number: the best score for aligning the letters up to that row with the letters up to that column. Fill the grid from the top left, and the last cell holds the best score for both sequences in full. This step-by-step filling of a table is called dynamic programming; it is a general method of calculation, not a kind of computer program.
Three moves into every cell
There are only three ways to arrive at a cell, and each one is a different last column of the alignment:
- Diagonally from the cell up and to the left: the row letter and the column letter are paired. Add the match or mismatch score.
- Down from the cell above: the row letter is paired with a gap. Add the gap penalty.
- Right from the cell to the left: the column letter is paired with a gap. Add the gap penalty.
Work out all three and keep the largest, remembering which move won. When the grid is full, follow the winning moves back from the finishing cell to the start. That walk, the traceback, spells out the best alignment column by column, from the end backwards.
Why can the computer get away with keeping only the best of three? Because any alignment, however long, has to end in one of those three ways: two letters paired, or a letter in the row sequence against a gap, or a letter in the column sequence against a gap. Whatever came before that last column must itself be the best alignment of the shorter pieces, and that number is already in the neighbouring cell. So no possibility is ever thrown away; the grid simply avoids working out the same smaller answers again and again.
With the affine gaps of Pairwise alignment: dot plots, scores and gaps there is one complication. The cost of a gap now depends on whether the previous column was already a gap, so one number per cell is not enough. Aligners keep three numbers in each cell, one for each kind of last column, and that is the method Gotoh described in 1982. The idea of filling the grid and tracing back is unchanged.
Global: Needleman–Wunsch
A global alignment lines up two sequences from first letter to last. The method for it, published in 1970, is named after its authors, Needleman and Wunsch. The top row and left column are filled first: they hold the cost of starting with nothing but gaps, so they fall by the gap penalty at each step. The answer is in the bottom-right corner, because that cell covers both sequences in full.
Global alignment charges for every gap, including gaps at the very start or end. That is right when both sequences are expected to run the whole way, such as two orthologues of the same length. It is a trap when one sequence is much longer than the other, or when one record is a fragment: the unmatched ends are paid for gap by gap, and the score falls even though the part that overlaps may match perfectly. The second Biopython block below shows how bad this can get. A global score also grows with the length of the sequences, so a score of 200 for one pair and 100 for another does not mean the first pair is more closely related unless both pairs are about the same length.
The two methods come from Needleman and Wunsch (1970), 'A general method applicable to the search for similarities in the amino acid sequence of two proteins', Journal of Molecular Biology 48:443–453, and Smith and Waterman (1981), 'Identification of common molecular subsequences', Journal of Molecular Biology 147:195–197. The grid filling taught today is a tidied form worked out in later papers; the 1970 procedure differs in detail. Cite the originals for the ideas, and describe the method you actually ran. Biopython is cited as Cock et al. (2009), Bioinformatics 25:1422–1423, with its version. Report the mode, the scores and the gap penalties: change any of them and the best alignment can change.
Local: Smith–Waterman
A local alignment finds the best-matching stretch within the two sequences and ignores the rest. The method, published in 1981 by Smith and Waterman, changes just two things. First, a fourth option is added to every cell: zero. A cell can never go negative, which means "start afresh here rather than drag along a poor stretch". Second, the answer is the highest number anywhere in the grid, not the corner, and the traceback stops as soon as it reaches a zero. The figure fills both grids for the same small pair.
The zero only works if the scores are balanced in the way Pairwise alignment: dot plots, scores and gaps described, with a column of two random letters scoring below zero on average. Then a poor stretch drags the running total down to zero and the alignment restarts. If chance columns scored above zero on average, the running total would rarely fall, and a local alignment would spread across almost the whole of both sequences, much like a global one. Substitution tables such as BLOSUM62, the subject of Scoring matrices: PAM and BLOSUM, are built with this balance.
How to read this figure
- The extra row and column marked - stand for "no letters yet". The top-left cell is 0: aligning nothing with nothing scores nothing.
- In the global grid, the top row reads 0, −2, −4 and so on: setting the first one, two or three letters of GATCA against gaps costs −2 each. The left column does the same for GTCA.
- Follow the shaded path in the global grid from the top left. A diagonal step to 1 pairs G with G. A step right to −1 pairs the A of GATCA with a gap. Three diagonal steps then pair T, C and A, rising to 0, 1 and 2. As an alignment: GATCA over G-TCA, score 2.
- In the local grid, every negative number has become 0. The highest cell is 3, and the path runs back through 2 and 1 to a zero. The alignment is TCA over TCA, score 3. The G at the start is left out, because keeping it would cost a gap of −2 and earn only +1.
Both methods are exact: with the scores you choose, they are guaranteed to find the best alignment, not just a good one. The price is time. The grid has one cell for every pair of letters, so comparing one protein with a database of hundreds of millions of proteins this way would mean filling an enormous number of cells. Search tools such as BLAST therefore take shortcuts: they first look for short, high-scoring matching words and only extend the promising ones. They are much faster, and very occasionally miss what an exact method would find.
Worked example · filling one cell
diagonal: −1 (cell up-left) + 1 (T matches T) = 0
down: −3 (cell above) − 2 (gap) = −5
right: 0 (cell to the left) − 2 (gap) = −2
best = 0, reached diagonally
Every cell in both grids is filled with the same three sums. The local grid adds a fourth option, 0.
Step by step. Find the cell in the row for T and the column for T. The cell diagonally up and to the left, in the G row and A column, holds −1; T against T is a match, so the diagonal route gives −1 + 1 = 0. The cell directly above, in the G row and T column, holds −3; coming down means a gap, so −3 − 2 = −5. The cell to the left, in the T row and A column, holds 0, and moving right means a gap, so 0 − 2 = −2. The largest of 0, −5 and −2 is 0, and the winning move is diagonal.
What the answer means. The 0 says that the best way to align GA with GT scores 0 and ends with T paired with T. Because the move was diagonal, the traceback will pair those two letters. The same three sums for the corner cell give diagonal 1 + 1 = 2, down −1 − 2 = −3 and right −1 − 2 = −3, so the corner holds 2: the global score.
Go deeper: ties, memory and long sequences
The best score can often be reached by more than one path, because two moves into a cell can tie. Each path is a different alignment with the same score, and all are equally 'best'. Biopython keeps them all: len(aligner.align(a, b)) tells you how many there are. Which one a tool shows first is a convention, so two programs can report different alignments with the same score.
The grid also grows with the product of the two lengths. Two proteins of 300 residues need 90,000 cells, which is nothing. Two bacterial genomes of 5 million bases each would need 25 million million cells, far too many to store for a traceback. A method first published by Hirschberg in 1975, and later adapted to alignment, finds the same answer while keeping only a few rows at a time, at the cost of extra computing. Genome aligners take faster shortcuts instead.
The same pair in Biopython
Biopython's PairwiseAligner fills these grids for you. It does global alignment unless told otherwise. The first block aligns the pair from the figure in both modes, with the same scores.
from Bio import Align
aligner = Align.PairwiseAligner(match_score=1, mismatch_score=-1, gap_score=-2)
for mode in ["global", "local"]:
aligner.mode = mode
best = aligner.align("GATCA", "GTCA")[0]
print(mode, "score:", best.score)
print(best)What this does
PairwiseAligner(...)makes an aligner with match +1, mismatch −1, and −2 for every gap position (gap_scoresets both the opening and extension penalties to the same value, a linear penalty).- The loop runs twice.
aligner.mode = modeswitches between"global"and"local". aligner.align(...)returns the best alignments;[0]takes the first. The first sequence given is called the target and the second the query.print(best)draws the alignment with a line of marks between the sequences.
Reading the output
The scores match the grids: 2 for global and 3 for local. In the marks line, | is an identical pair, - a gap and . a mismatch. The numbers either side are positions, counted from 0 as Python does: target 2 TCA 5 means the local alignment starts after the first two letters of GATCA and ends after the fifth. In everyday counting from 1, that is letters 3 to 5. The local alignment simply drops the G at the start of each sequence.
Which one to use
The choice depends on the question, not on which gives the higher score.
- Two sequences expected to match end to end
- Orthologues of similar length, such as human and mouse haemoglobin beta
- Two versions of the same gene
- Web: EMBOSS Needle at EMBL-EBI
- A shared region inside longer, different sequences
- One domain shared by two otherwise different proteins
- A short peptide or read against a long sequence
- Database searches; BLAST is local
- Web: EMBOSS Water at EMBL-EBI
A domain is a part of a protein that folds and works as a unit, and many proteins are built from several. Two proteins may share one domain and nothing else; a global alignment would force the unrelated parts together and hide the real match. A middle way, sometimes called semi-global alignment, aligns end to end but does not charge for gaps at the ends; Biopython can do this by setting the end gap scores to zero.
Semi-global alignment suits a short sequence that should be used in full but may sit anywhere along a longer one. A typical case is a sequencing read placed on a reference genome: the whole read should be accounted for, but the genome on either side of it should cost nothing. Read aligners in Module 5 work in this spirit, with shortcuts for speed. A practical rule for all three modes: if the two scores are very different, look at the alignments themselves before trusting either number.
The second block shows what goes wrong when the wrong mode is used. It takes a 26-residue stretch of human haemoglobin beta, the kind of short peptide a mass spectrometer might report (Module 1), and aligns it with the whole of human haemoglobin alpha, written into the code from UniProt P69905. The scoring is the BLAST protein setting from Why compare sequences: homology, similarity and identity, which Scoring matrices: PAM and BLOSUM explains.
alpha = ("MVLSPADKTNVKAAWGKVGAHAGEYGAEALERMFLSFPTTKTYFPHFDLSHGSAQVKGHG"
"KKVADALTNAVAHVDDMPNALSALSDLHAHKLRVDPVNFKLLSHCLLVTLAAHLPAEFTP"
"AVHASLDKFLASVSTVLTSKYR") # human haemoglobin alpha, P69905
peptide = "LWGKVNVDEVGGEALGRLLVVYPWTQ" # human beta, P68871, residues 15-40
aligner = Align.PairwiseAligner(scoring="blastp")
for mode in ["global", "local"]:
aligner.mode = mode
best = aligner.align(alpha, peptide)[0]
print(mode, "score:", best.score)
print(best)What this does
- The alpha sequence is split over three lines inside brackets; Python joins strings written side by side into one, here of 142 residues.
scoring="blastp"sets the aligner to BLAST's protein scores. The same loop as before aligns the peptide globally and then locally.
Reading the output
- Global, score −80. The aligner had to use every residue of both sequences, so the peptide is stretched across the whole of alpha with long runs of gaps. Look at the ends: the peptide's first letter, L, has been pulled to alpha's first residue, M, and its last letter, Q, to alpha's last, R. Those pairs score slightly better than leaving them in a gap, so the method does it, although it makes no biological sense. The middle part, from WGKV onwards, is sensible, but the overall score is dominated by gap penalties and tells you nothing useful.
- Local, score 54. Only the region that genuinely matches is reported: residues 15 to 41 of alpha against residues 2 to 26 of the peptide. It is the same WGKV stretch and the same two-residue gap that the dot plot showed in Pairwise alignment: dot plots, scores and gaps. Of its 27 columns, 12 are identical.
For finding where a short sequence sits in a long one, local alignment gives a clean, positive answer; global alignment gives a misleading one. For two whole orthologues of similar length, the two modes usually agree.
Key point
Both methods fill a grid in which each cell keeps the best of three moves, then trace back the winning path. Global (Needleman–Wunsch) must use both sequences end to end and reads its score from the corner. Local (Smith–Waterman) never lets a cell drop below zero and reports the best stretch anywhere. Choose the mode from the question.
A second example: you want to know whether a 120-residue domain from a fly protein is present in a 900-residue human protein. Use local alignment. A global alignment would spread the domain across all 900 residues, and its large negative score could make you wrongly conclude there is no match.
Further reading · Module 4Biopython tutorial: pairwise sequence alignment, including global, local and end-gap settings. · EMBOSS Needle at EMBL-EBI (global). · EMBOSS Water at EMBL-EBI (local). · All reading for this course
Check your understanding
1. You want to find where a 30-residue peptide sits inside a 600-residue protein. Which approach fits?
2. What is the one rule that makes a Smith–Waterman grid different when each cell is filled?
3. Why do search tools such as BLAST not run Smith–Waterman against every sequence in a large database?
Up next
Lesson 4
Scoring matrices: PAM and BLOSUM