Lesson 2 of 9
Module 4 · Comparing sequences
Before a computer can find the best alignment, it needs a way to score one. Draw a dot plot in plain Python, then learn how match, mismatch and gap scores work, and why affine gaps match real evolution.
What an alignment claims
An alignment writes two sequences one above the other so that each column holds letters thought to descend from the same position in the common ancestor. It is a hypothesis about history. Where the letters agree, nothing has changed. Where they differ, there has been a substitution, one letter replaced by another. Where one sequence has a letter and the other a dash, there has been an indel: an insertion in one sequence or a deletion in the other. From the alignment alone you cannot tell which, so the neutral word indel covers both. A dash is called a gap.
Because it is a hypothesis, an alignment can be wrong, and sometimes several are equally good. Take CATTTTG and CATTTG. One T has been lost, but which one? The dash can sit under any of the four T's and every version has the same matches and the same single gap. Nothing in the sequences can decide between them. Programs settle such ties by a fixed rule, and variant files in VCF format, which you met in File formats you will meet: FASTA, GenBank, GFF, VCF, PDB, usually place the indel at the leftmost possible position so that the same change is always written the same way.
There are a huge number of ways to place gaps in two sequences, and most of them are nonsense. To choose the best one, a computer needs two things: a way to give every possible alignment a number, the score, and a quick way to find the alignment with the highest score. This lesson covers the first and gives a picture of the problem; Global and local alignment, without heavy maths covers the second. This lesson needs only plain Python, with nothing to install.
Dot plots: seeing similarity before aligning
A dot plot is the simplest comparison of all, and it needs no scores. Write one sequence down the side of a grid and the other across the top. Put a dot in every cell where the row letter and the column letter are the same. Then step back and look at the pattern.
Where the two sequences are similar, the dots line up into a diagonal running from top left to bottom right, because consecutive letters match consecutive letters. Random single matches are scattered about and form no line. The figure shows the three patterns you will meet most often.
How to read this figure
- Panel 1. A single diagonal from corner to corner means the two sequences are similar all the way along, with no indels. Short breaks in the line are single substitutions.
- Panel 2. The diagonal stops, moves sideways and carries on. A sideways jump means the sequence across the top has extra letters at that point that the side sequence lacks; a jump downwards would mean the opposite. The length of the jump is the length of the indel.
- Panel 3. A sequence plotted against itself. The main diagonal is trivially complete. Short lines parallel to it show a repeat: one stretch matches another stretch further along. Repeats are common in proteins made of repeated units and in many parts of genomes.
Real dot plots of long sequences are noisy, because with only 4 letters in DNA a quarter of all cells match by chance. Tools therefore use a window: they compare short runs, say 10 letters at a time, and draw a dot only if most of them match. This removes the scattered noise and leaves the lines.
One more pattern is worth knowing. A stretch made of one letter repeated, such as a run of A's in DNA or of glutamines in a protein, matches itself at every offset, so it shows up as a filled square or rectangle of dots rather than a line. Such blocks say nothing about shared ancestry; they only show that both sequences contain a repetitive patch. Dot plots are best used as a first look, to see whether two sequences are related along their length, whether there are large indels, and whether an alignment is worth building at all.
Go deeper: inversions and the other strand
A protein dot plot has only one direction to read. DNA has two strands, and a stretch of chromosome can be flipped round, an inversion, so that it now reads backwards on the opposite strand. Compare such a region with the original and the diagonal simply vanishes.
Plot the first sequence against the reverse complement of the second, that is, the second read backwards with each base swapped for its partner (A with T, C with G), and the matching run reappears. Programs that draw both strands on one plot place these matches back at their original positions, where they form a line running the other way, from bottom left to top right. Dot plots of two bacterial strains, or of two assemblies of one genome, use this to show rearrangements at a glance: forward lines are regions in the same order, reverse lines are inversions, and breaks show where pieces have moved.
A dot plot in plain Python
The code compares a fragment of human haemoglobin beta with a fragment of human haemoglobin alpha, its paralogue from Why compare sequences: homology, similarity and identity. Residues are numbered from the starting methionine, as UniProt does.
def dot_plot(a, b):
print(" " + " ".join(b)) # sequence b across the top
for x in a: # one row per letter of a
row = ["*" if x == y else "." for y in b]
print(x + " " + " ".join(row))
# Haemoglobin fragments: human beta (P68871, residues 15-31)
# and human alpha (P69905, residues 14-32)
beta = "LWGKVNVDEVGGEALGR"
alpha = "AWGKVGAHAGEYGAEALER"
dot_plot(beta, alpha)What this does
def dot_plot(a, b):defines a small function that takes two sequences. The firstprintwrites sequencebacross the top, with spaces between the letters.for x in a:goes down sequenceaone letter at a time. For each letter, the line startingrow =compares it with every letter ofband builds a list of*for a match and.for no match.- Each row is printed with its letter at the start, so the result is a grid of 17 rows and 19 columns.
Reading the output
Look for stars that line up diagonally. The first diagonal runs from W in row 2 to V in row 5: WGKV is shared. The rows for N and D have no stars at all. Further down, a second diagonal starts at E in row 9, column 11, and passes through the G in row 11, the E, A and L in rows 13 to 15, and ends at R in the bottom right corner. It sits two columns to the right of where the first diagonal would have gone, so alpha has two extra residues in this region: an indel of length 2. The other stars, mostly in the rows for G, E and A, are chance matches of common letters. You have found by eye the gap that the aligner placed in Why compare sequences: homology, similarity and identity.
What a score is
A dot plot shows that two sequences are similar, but it does not give a single best alignment or a number to compare. For that, every column of an alignment gets points, and the points are added up. The simplest scheme has three values:
- a match score, a reward for the same letter in both sequences, for example +2;
- a mismatch score, a penalty for two different letters, for example −1;
- a gap penalty, a cost for each dash, for example −2.
The best alignment is the one with the highest total. The values are a choice, not a law of nature, and different values can give different best alignments. They are chosen so that the score reflects how likely the alignment is to show real shared ancestry rather than chance. For proteins, a single mismatch score is too crude: some swaps happen often in evolution and some almost never. Scoring matrices: PAM and BLOSUM replaces it with a table of scores for every pair of amino acids.
Gaps are penalised more than mismatches because indels are rarer than substitutions, and because, if gaps were cheap, an aligner could line up almost any two sequences by adding dashes until letters matched. A gap penalty stops that.
The balance between the values matters as much as the values themselves. Line up two unrelated sequences and some columns will match by chance. If the match reward is large compared with the mismatch penalty, those chance matches add up, and the score keeps rising with length even when nothing is related. A sensible scheme is set so that, on average, a column of two random letters scores below zero. Then only a real run of agreement can build up a high score. This property becomes essential for local alignment in Global and local alignment, without heavy maths, which looks for the best-scoring stretch anywhere in the two sequences.
Affine gaps: one long gap beats many short ones
The plain scheme charges the same for every dash, so three separate one-letter gaps cost the same as one gap three letters long. That is a linear gap penalty. Biologically it is wrong. A single mutation event can insert or delete several letters at once, so one gap of three is far more likely than three independent gaps of one.
Most aligners therefore use an affine gap penalty, which has two parts: a large gap opening penalty for starting a gap, and a small gap extension penalty for each further position. With an opening penalty of −4 and an extension penalty of −1, a gap of one costs −4, a gap of two −5 and a gap of three −6. Long gaps get cheaper per letter, and many small gaps become expensive.
- Every dash costs the same, for example −2
- A gap of 3 costs −6
- Cannot tell one long gap from scattered short ones
- Opening −4, then −1 per extra position
- A gap of 3 costs −4 −1 −1 = −6
- Three gaps of 1 cost −12, so they are avoided
Note the convention. Here, and in Biopython, the opening penalty is the cost of the first gap position. Some tools, BLAST among them, describe the same thing as a cost for opening plus a cost for every position including the first. The arithmetic differs; the idea is the same. The next block scores two alignments of the same pair both ways.
def score(top, bottom, match=2, mismatch=-1, gap_open=-4, gap_extend=-1):
total, in_gap = 0, False
for x, y in zip(top, bottom):
if x == "-" or y == "-":
total += gap_extend if in_gap else gap_open
in_gap = True
else:
total += match if x == y else mismatch
in_gap = False
return total
# Two ways to align the same pair (made up for teaching)
one_gap = ("CATTTTTG", "CA---TTG")
two_gaps = ("CATTTTTG", "CAT-T--G")
for name, (top, bottom) in [("one gap ", one_gap), ("two gaps", two_gaps)]:
linear = score(top, bottom, gap_open=-2, gap_extend=-2)
affine = score(top, bottom)
print(name, "linear:", linear, " affine:", affine)What this does
scoretakes the two rows of an alignment, with dashes for gaps, and walks along them column by column. The values after=in the first line are defaults, used unless others are given.in_gapremembers whether the previous column was a gap. The first dash of a gap is chargedgap_open; each following dash is chargedgap_extend.- Columns without a dash get the match or mismatch score.
- The two alignments are of the same made-up DNA pair, CATTTTTG and CATTG. Both have five matches and three dashes. In the first the dashes form one gap; in the second they form a gap of one and a gap of two.
- Calling
scorewithgap_open=-2, gap_extend=-2makes every dash cost −2, which is a linear penalty. Calling it with no extra values uses the affine defaults.
Reading the output
With linear gaps both alignments score 4: the scheme cannot tell them apart. With affine gaps the single gap still scores 4, but the split version drops to 1, because it pays the opening penalty twice. An aligner using affine gaps will choose the first alignment, which is also the biologically simpler story: one deletion of three letters in a run of T's.
Worked example · scoring an alignment by hand
CAT-T--G
matches 5 × (+2) = +10
gap of 1: −4 · gap of 2: −4 −1 = −5
total = 10 − 4 − 5 = 1
Match +2, mismatch −1, gap opening −4, gap extension −1. Made-up sequences.
Step by step. Go along the columns. C over C, A over A and T over T are matches: +6 so far. Column 4 has T over a dash; it starts a gap, so it costs −4. Column 5 is T over T, another match, +2. Columns 6 and 7 are both dashes in the bottom row, one gap of length two: −4 for the first, −1 for the second. Column 8 is G over G, +2. Adding up: 5 matches give +10, and the gaps give −4 and −5, so the total is 1.
What the answer means. The same five matches and three dashes score 4 when the dashes form one gap and 1 when they are split. Scores have no meaning on their own; they are for comparing alignments of the same pair under the same scheme. A score from one scheme cannot be compared with a score from another.
Dot plots were introduced by Gibbs and McIntyre (1970), 'The diagram, a method for comparing sequences', European Journal of Biochemistry 16:1–11. The efficient way to align with affine gap penalties is due to Gotoh (1982), 'An improved algorithm for matching biological sequences', Journal of Molecular Biology 162:705–708. A clear textbook account of scores, gaps and log-odds is Durbin, Eddy, Krogh and Mitchison (1998), Biological Sequence Analysis (Cambridge University Press). Because tools count gap costs differently, as this lesson shows, a methods section should name the program and its version, the match and mismatch scores or matrix, and both gap values, and say which convention they follow.
Where the numbers come from
The values used here are round numbers for teaching. Real scoring schemes are built from data. In outline, a good score for a pair of letters is high when that pair is seen in true alignments of related sequences more often than chance would predict, and negative when it is seen less often. Scores of this kind are called log-odds scores, and adding them up along an alignment measures how much more likely the alignment is under "these are related" than under "this is chance". Scoring matrices: PAM and BLOSUM shows how such a table was built for proteins. For DNA, simple match and mismatch scores are usually good enough, and they are what read aligners such as those in Module 5 use.
The idea behind log-odds is simpler than the name. For each pair of letters, compare two frequencies: how often the pair is seen in columns of trusted alignments, and how often it would turn up if the two letters were picked at random. If a pair is seen four times as often as chance predicts, its score is the logarithm of 4, a positive number. If it is seen only a quarter as often, the score is the logarithm of a quarter, a negative number of the same size. Logarithms are used so that the evidence from separate columns can be added rather than multiplied. Published tables round these values to whole numbers, which is why scores are usually integers.
Even for DNA, a single mismatch value hides some biology. Swaps between the two purines (A and G) or between the two pyrimidines (C and T), called transitions, happen more often than swaps between a purine and a pyrimidine, called transversions. Some DNA scoring schemes and many models used for trees, the subject of Trees from sequences, treat the two kinds differently for this reason.
Key point
A dot plot shows similarity as diagonals, indels as sideways jumps and repeats as parallel lines. An alignment score adds up match, mismatch and gap values column by column, and affine gaps make one long gap cheaper than several short ones, as in real evolution.
A second example: two alignments of the same protein pair match the same letters, but one has a single gap of six and the other three gaps of two. With affine penalties the second pays the opening cost three times, so it scores lower, and the aligner reports the first: one indel event is a simpler story than three.
Further reading · Module 4Biopython tutorial: pairwise sequence alignment, including how gap scores are set. · EMBL-EBI Job Dispatcher: pairwise sequence alignment tools. · All reading for this course
Check your understanding
1. In a dot plot of two proteins, the diagonal runs for a while, then continues five columns further to the right. What does this suggest?
2. Why do most aligners use affine rather than linear gap penalties?
3. Alignment X scores 40 with one set of scores and alignment Y of a different pair scores 55 with another. What can you conclude?
Up next
Lesson 3
Global and local alignment, without heavy maths