Alignment and substitution matrices

Lesson 5.2 of Biology Primer for Computer Scientists. Download the code as a notebook.

Before a structure can be borrowed from a relative, you have to find the relative and decide which residue matches which. Template search, homology modeling, and the alignments AlphaFold reads all start with pairwise alignment. You already know the algorithm: edit distance by dynamic programming, except that the costs come from evolution.

Similarity as evidence of homology

Since protein sequences first became available, researchers realized that sequences of homologous proteins from related organisms are very similar. The difference grows with an increasing evolutionary distance between species. This observation led to the development of sequence alignment methods, which attempt to find an optimal alignment between the sequences of two (or more) proteins being compared. Since homologous proteins by definition evolved from a common ancestor, we expect that a series of mutations, deletions, and insertions lead from the common ancestor to both modern sequences. A list of such elementary steps is equivalent to a unique alignment. When possible homology between two proteins is considered, the null hypothesis is that the two sequences do not come from the common ancestor. The comparison of their sequences should be similar to that of a comparison between two random strings of letters. Therefore, if a larger than random similarity is found, it is generally assumed that such proteins are homologous. This connection is so strong that sequence similarity is de facto used as a synonym of homology, despite the fact that homology is a much stronger concept and the two are not equivalent. At the same time, two proteins may be homologous despite lack of an easily recognizable sequence similarity.

Once the homology is established, we can predict the structure and function of new proteins by analogy, assuming that in evolution at least some aspects of function are conserved. To apply analogy reasoning, two problems must be solved. First, the similarity must be recognized, which for distant homologues may not be trivial. Second, the detailed alignment, that is, the residue-by-residue equivalence table between the two proteins, must be constructed.

The similarity between two sequence strings is usually defined as the sum of similarities between residues in both proteins at equivalent positions. A scoring matrix, giving a numerical score for aligning any two amino acids, defines a similarity. The similarity score ranges from large and positive (for the same residue in both positions) to smaller and positive (for residues with similar features, such as valine and leucine) to large and negative (for very different residues):

S=∑iM(Ai,Bj(i))

where M is the scoring matrix and Bj(i) is the residue of sequence B aligned to position i of A. An important feature of this scoring function is that it is additive or local: the score for one position does not depend on the alignment (or on residues) in another position.

Gaps and insertions in both sequences are necessary for the optimal alignment. The optimal alignment with gaps can be found by dynamic programming. Alternatively, similar sequences can be identified by searching for high-scoring fragments, uninterrupted alignment fragments. Software tools, such as BLAST or FASTA, became standards in searching for similar sequences in protein databases.

Alignment is dynamic programming

To identify a template, a program compares the query sequence to all the sequences of known structures in the PDB mainly using two matrices:

  • A residue exchange matrix. This matrix defines the likelihood that any 2 of the 20 amino acids ought to be aligned. Exchanges between different residues with similar physicochemical properties (e.g., F → Y) get a better score than exchanges between residues that widely differ in their properties. Conserved residues generally obtain the highest score.
  • An alignment matrix. The axes of this matrix correspond to the two sequences to be aligned, and the matrix elements are simply the values from the residue exchange matrix for a given pair of residues. During the alignment process, one tries to find the best path through this matrix, starting from a point near the top left and going down to the bottom right. To make sure that no residue is used twice, one must always take at least one step to the right and one step down.

By comparing thousands of sequences and sequence families, it became clear that the opening of gaps is about as unlikely as at least a couple of nonidentical residues in a row. The alignment algorithm therefore subtracts an "opening penalty" for every new gap and a much smaller "gap extension penalty" for every residue that is additionally skipped once the gap has already been made. The gap extension penalty is much smaller than the gap open penalty because one gap of three residues is much more likely than three gaps of one residue each.

The best path is found with the recurrence you'd write for edit distance, maximizing instead of minimizing. With a linear gap penalty g, let F(i,j) be the best score for aligning the first i residues of A with the first j of B:

F(i,j)=max⁡{F(i−1,j−1)+M(Ai,Bj)align Ai with BjF(i−1,j)−gAi against a gapF(i,j−1)−gBj against a gap

Filling the table takes O(mn) time, and following each cell's choice back from the end recovers the alignment. The global version (Needleman–Wunsch) starts from F(i,0)=−gi and ends at the bottom-right corner, so every residue of both sequences is used. The local version (Smith–Waterman) adds a fourth option, 0, so a poor stretch can be abandoned. It starts from zeros and ends at the best cell anywhere, finding the best-matching segments. Use local alignment to find a domain inside a longer protein. Affine gaps (an opening cost plus a smaller per-residue extension cost) need three such tables, one for each kind of last step, and keep the O(mn) bound.

Loading the interactive figure…

The table F for two short sequences with BLOSUM62 and a linear gap penalty. The orange cells trace the optimal path back from the end. Hover any cell to see the three candidates it took the best of. Edit the sequences, switch to local alignment, or make gaps cheaper and watch the path change.

Where the scores come from

A substitution score is a log-odds ratio. Suppose amino acids a and b occur with background frequencies pa and pb, and in alignments of true relatives they are found paired with frequency qab. Then

s(a,b)=1λlog⁡qabpapb,

positive when relatives pair a with b more often than chance and negative when less often. Because alignment columns are scored independently, the alignment score is the log of a likelihood ratio, the probability of the aligned pairs if the sequences are related over the probability if they're unrelated. It is the same quantity a naive Bayes classifier sums.

The most widely used matrix, BLOSUM62, was built by Steven and Jorja Henikoff in 1992. They took the BLOCKS database, about 2,000 gap-free aligned segments from some 500 protein families, and counted every pair of residues sharing a column. To keep large clusters of near-identical sequences from dominating the counts, sequences more than 62% identical to each other were grouped and counted as one; the 62 in the name is that threshold. The log-odds were then scaled to half-bit units (λ=ln⁡22, so a score of 2 means the pair is twice as common as chance) and rounded to integers. BLOSUM80 (clustered at 80%) suits close relatives and BLOSUM45 distant ones.

Loading the interactive figure…

BLOSUM62. Blue cells are pairs seen together in true alignments more often than chance, red less often. Ordered by chemistry, the blocks show the families of interchangeable residues: the small residues, the acids and amides, the bases, and the large hydrophobics. Hover a cell for the odds.

The matrix encodes the structural rules from lesson 5.1. Isoleucine and valine score +3 because both are branched, hydrophobic, and nearly the same size, so they swap freely in protein cores. Tryptophan with tryptophan scores 11, the highest entry: Trp is rare and hard to replace, so an aligned Trp–Trp pair is strong evidence. Cysteine (9), often locked in a disulfide, and glycine and proline (6 and 7), with their special backbone roles, are also conserved. Undo the log to see what the numbers mean:

from Bio.Align import substitution_matrices

B62 = substitution_matrices.load("BLOSUM62")
# Background frequencies of the 20 amino acids in the BLOCKS data behind BLOSUM62
P = dict(A=.074, R=.052, N=.045, D=.054, C=.025, Q=.034, E=.054, G=.074, H=.026, I=.068,
         L=.099, K=.058, M=.025, F=.047, P=.039, S=.057, T=.051, W=.013, Y=.032, V=.073)

for a, b in [("W", "W"), ("I", "V"), ("L", "L"), ("D", "E"), ("W", "G")]:
    print(f"{a}-{b}: score {B62[a][b]:+.0f}, seen {2 ** (B62[a][b] / 2):5.2f}x as often as chance")

# Given a W in one sequence, how often is its partner in a true alignment also W?
for a in "WCGL":
    print(f"P(partner is {a} | {a}) = {P[a] * 2 ** (B62[a][a] / 2):.2f}")

expected = sum(P[a] * P[b] * B62[a][b] for a in P for b in P)
print(f"expected score of a random pair: {expected:.2f}")
W-W: score +11, seen 45.25x as often as chance
I-V: score +3, seen  2.83x as often as chance
L-L: score +4, seen  4.00x as often as chance
D-E: score +2, seen  2.00x as often as chance
W-G: score -2, seen  0.50x as often as chance
P(partner is W | W) = 0.59
P(partner is C | C) = 0.57
P(partner is G | G) = 0.59
P(partner is L | L) = 0.40
expected score of a random pair: -1.00

Local alignment depends on the last line. A random pair scores about −1 on average, so a random stretch drifts downward and Smith–Waterman abandons it. If the expected score were positive, the best local alignment of two unrelated sequences would just keep growing to cover them both.

Is the score significant?

With increasing evolutionary distance, sequence similarity between homologous proteins fades. Using simple alignment tools and mutation matrix scoring, it is increasingly difficult to distinguish the homology from the null hypothesis of random similarity. This is referred to as the "twilight zone" of sequence similarities and corresponds to about 25% of identical amino acids in an optimal alignment between protein pairs. This value strongly depends on the length of the alignment, as illustrated by well-known examples of identical pentapeptides with different structures.

Lesson 5.1 showed that percent identity can't separate myoglobin and hemoglobin α from shuffled sequences. The alignment score does better, provided you measure it against the right null distribution. Shuffle one sequence many times (same composition, no shared history), align each shuffle, and see where the real score falls:

import random
import matplotlib.pyplot as plt
import numpy as np
from Bio.Align import PairwiseAligner
from primer import structure, sequence

aligner = PairwiseAligner(mode="local", open_gap_score=-11, extend_gap_score=-1)
aligner.substitution_matrix = B62
mb = sequence(structure("1A6M")[0]["A"])   # sperm whale myoglobin
hb = sequence(structure("4HHB")[0]["A"])   # human hemoglobin α

random.seed(1)
real = aligner.score(mb, hb)
null = np.array([aligner.score(mb, "".join(random.sample(hb, len(hb)))) for _ in range(1000)])
z = (real - null.mean()) / null.std()
print(f"real score {real:.0f}; shuffled {null.mean():.0f} ± {null.std():.0f} (max {null.max():.0f}); z = {z:.1f}")

fig, ax = plt.subplots(figsize=(6.4, 3))
ax.hist(null, bins=30, color="#9ec5f4", label="1,000 shuffles of hemoglobin α")
ax.axvline(real, color="#eb6834", lw=2, label="the real pair")
ax.set_xlabel("local alignment score (BLOSUM62, gaps −11/−1)")
ax.set_ylabel("count")
ax.legend()
plt.show()
real score 109; shuffled 31 ± 6 (max 63); z = 13.5
20 40 60 80 100 local alignment score (BLOSUM62, gaps −11/−1) 0 25 50 75 100 125 150 count 1,000 shuffles of hemoglobin α the real pair

The real score, 109, sits 13.5 standard deviations above the shuffles (31 ± 6, none above 63), though identity put the same pair inside the range of chance. Scores of optimal local alignments between random sequences follow an extreme-value (Gumbel) distribution, which is the distribution of a maximum. Database search tools use it to report an E-value, the expected number of hits scoring at least this well by chance in a search of that size, E=Kmne−λS for sequence lengths m and n (the database's total length in a search) and constants K and λ fitted to the scoring system. Each extra 1/λ of score cuts E by a factor of e. An E-value of 10−5 means one such hit by chance in 100,000 searches. E-values around 1 or larger mean the hit is consistent with chance.

Check yourself

Two proteins of length 300 align globally at 30% identity, and two peptides of length 12 align at 50% identity. Which result is stronger evidence of homology, and why?

Reasoning

The 300-residue alignment. Identity is a fraction, and short alignments reach high fractions by luck: with only 12 positions, six matches can happen by chance in an optimized alignment (identical pentapeptides turn up in unrelated proteins with different structures). The score of a long alignment sums hundreds of positions, so a sustained excess over random is very unlikely. That is why E-values depend on length and why the twilight-zone threshold rises for shorter alignments.

In the DP widget, set the gap penalty to 1. What happens to the alignment, and why would a real alignment program never use such a low penalty?

Reasoning

The alignment fills with gaps: skipping a residue costs almost nothing, so the algorithm dodges every mismatch by gapping around it, lining up identical letters anywhere along both sequences. Real indels are rarer than substitutions and usually remove or add several residues at once in a loop, which is why gaps get a large opening penalty and a small extension penalty. With cheap gaps, unrelated sequences also reach high scores, so the null distribution shifts up and the score no longer separates relatives from strangers.

BLOSUM62 scores W–W at +11 but L–L at only +4, yet both are "identical residue" matches. Explain the difference using the log-odds definition.

Reasoning

The score is log2⁡ of observed over expected, doubled. Tryptophan is rare (about 1.3% of residues), so two tryptophans landing in the same column by chance is very unlikely (pW2≈0.00017), while true relatives keep Trp paired with Trp far more often than that, so the ratio is large. Leucine is the most common residue (about 10%), so Leu–Leu pairs arise often by chance and the ratio is smaller. Matching a rare, conserved residue is better evidence than matching a common one.

A colleague runs a local alignment with a home-made scoring matrix in which the average score of a random pair is +0.5. Every query returns alignments covering nearly the entire length of both sequences. Explain.

Reasoning

With a positive expected score, extending an alignment through random sequence gains score on average, so the best local alignment keeps growing until it hits the sequence ends. Local alignment works only when random pairs score negative on average (about −1 for BLOSUM62), so unrelated stretches lose score and get cut off. The matrix needs to be shifted or rebuilt as a proper log-odds matrix against the right background frequencies.