Coevolution and contacts
A profile treats each column on its own. Pairs of columns hold more: when two residues touch in the folded protein, a change at one is often followed, over evolutionary time, by a compensating change at the other. Detect enough of those pairs and you have a contact map of the structure from sequences alone. This is the signal that first made accurate structure prediction from sequence possible, and it remains central to AlphaFold and to protein language models.
Residues that change together
Another sequence-based approach for the prediction of protein structure and molecular complexes is based on the detection of correlated mutations in multiple sequence alignments and their use as distance constraints between residues belonging to the same or different proteins. Correlated mutations correspond to pairs of positions with a clear pattern of covariation. The underlying evolutionary model for explaining their relation with spatial neighbors assumes that part of the detected correlated pairs correspond to compensatory mutations, where in particular sequences of the multiple sequence alignment the mutation of one residue was compensated along the evolution by a mutation of a neighbor residue, most likely to keep proteins (or protein complexes) in permissible limits of protein stability.
Picture a buried salt bridge. If a lysine on one side mutates to glutamate, the pair now has two negative charges facing each other and the protein is destabilized, unless the aspartate on the other side mutates to lysine or arginine. The pair can flip as a unit, and neither residue can change freely alone. In a big core, a large residue on one side can be traded for a smaller one if its neighbor grows to fill the space.
Look at real pairs. The cell below loads the full Pfam alignment of the ubiquitin family, about 90,000 sequences, and tabulates which residue combinations occur at two pairs of columns:
import gzip
import urllib.request
from collections import Counter
import numpy as np
from primer import CACHE, display_html
def pfam(accession, kind="full"):
"""A Pfam family alignment as {name: aligned sequence}, downloaded once."""
path = CACHE / f"{accession.lower()}-{kind}.sto.gz"
if not path.exists():
url = f"https://www.ebi.ac.uk/interpro/api/entry/pfam/{accession}/?annotation=alignment:{kind}"
request = urllib.request.Request(url, headers={"User-Agent": "study-bioprimer"})
path.write_bytes(urllib.request.urlopen(request, timeout=300).read())
rows = {}
for line in gzip.open(path, "rt"):
if line.strip() and not line.startswith(("#", "//")):
name, seq = line.split()
rows[name] = rows.get(name, "") + seq
return rows
# Keep the family model's match columns (upper case and "-"); insertions are lower case and ".".
family = ["".join(c for c in seq if c.isupper() or c == "-") for seq in pfam("PF00240").values()]
AA = "ACDEFGHIKLMNPQRSTVWY-"
X = np.array([[AA.index(c) if c in AA else 20 for c in s] for s in family], dtype=np.int8)
X = X[(X == 20).mean(axis=1) < 0.2] # drop fragments that are mostly gaps
L = X.shape[1] # 72 columns: ubiquitin residues 3-74
ubq = "MQIFVKTLTGKTITLEVEPSDTIENVKAKIQDKEGIPPDQQRLIFAGKQLEDGRTLSDYNIQKESTLHLVLRLRGG"
print(f"{len(X)} sequences x {L} columns")
def pair_table(i, j, top=6):
"""The most common residue combinations at ubiquitin positions i and j."""
counts = Counter(zip(X[:, i - 3], X[:, j - 3])).most_common(top)
cells = "".join(f"<tr><td>{AA[a]}{i} with {AA[b]}{j}</td><td>{n / len(X):.1%}</td></tr>" for (a, b), n in counts)
return f"<table class='w-table' style='display:inline-table;margin-right:2em'>{cells}</table>"
display_html(pair_table(27, 52) + pair_table(19, 57))
79374 sequences x 72 columns
| K27 with D52 | 79.5% |
| K27 with N52 | 5.7% |
| R27 with D52 | 3.0% |
| K27 with E52 | 2.5% |
| K27 with S52 | 1.5% |
| R27 with N52 | 1.3% |
| P19 with S57 | 13.7% |
| S19 with A57 | 13.2% |
| S19 with S57 | 8.8% |
| P19 with A57 | 4.4% |
| P19 with E57 | 2.8% |
| A19 with S57 | 2.7% |
The first table is ubiquitin's buried Lys27–Asp52 salt bridge (lesson 5.3 found both positions conserved). Four sequences in five keep exactly that pair, and the common variants keep a base at 27 (Arg) or an acidic or amide partner at 52 (Glu, Asn). The second is a packing pair, Pro19 against Ser57: families with Pro at 19 tend to have Ser at 57, and families with Ser at 19 tend to have Ala at 57. Neither column alone shows that.
Mutual information, and why it misleads
The standard measure of how much one column tells you about another is mutual information, the divergence between the observed pair frequencies and what independence would predict, :
It is zero for independent columns and grows with dependence. Compute it for every pair and rank the pairs, and the top of the list should be contacts. In practice the top of the list is polluted, for three reasons:
- The sequences in an alignment are not independent samples. They descend from common ancestors, so two columns can co-vary because a whole clade inherited the same residues at both, with no physical coupling.
- Contacts chain. If residue A touches B and B touches C, then A and C co-vary through B even when they're far apart, and mutual information can't tell a direct coupling from a relayed one.
- Samples are finite. With 21 symbols there are 441 joint frequencies per pair, and even independent columns show some spurious mutual information unless the alignment is deep.
The first and third are easy to demonstrate. Simulate sequences evolving down a binary tree in which every site mutates independently, so no pair is coupled, and compare their mutual information with the same columns shuffled independently, which keeps each column's composition and destroys all shared history:
import matplotlib.pyplot as plt
rng = np.random.default_rng(0)
def evolve_on_tree(sites=30, depth=11, rate=0.12):
"""2**depth sequences from a random root; each branch mutates each site independently."""
seqs = rng.integers(0, 20, (1, sites))
for _ in range(depth):
seqs = np.repeat(seqs, 2, axis=0)
hit = rng.random(seqs.shape) < rate
seqs[hit] = rng.integers(0, 20, hit.sum())
return seqs
def mutual_information(S, q=21):
n, m = S.shape
onehot = np.eye(q)[S].reshape(n, -1)
fij = (onehot.T @ onehot / n).reshape(m, q, m, q)
fi = onehot.mean(0).reshape(m, q)
mi = np.zeros((m, m))
for i in range(m):
for j in range(i + 1, m):
p, e = fij[i, :, j, :], np.outer(fi[i], fi[j])
nz = p > 0
mi[i, j] = mi[j, i] = (p[nz] * np.log(p[nz] / e[nz])).sum()
return mi
tree = evolve_on_tree()
shuffled = np.column_stack([rng.permutation(col) for col in tree.T])
upper = np.triu_indices(tree.shape[1], 1)
fig, ax = plt.subplots(figsize=(6.4, 3))
ax.hist(mutual_information(shuffled, 20)[upper], bins=30, alpha=0.8, label="same columns, shuffled")
ax.hist(mutual_information(tree, 20)[upper], bins=30, alpha=0.8, label="evolved on a tree")
ax.set_xlabel("mutual information between two independent sites (nats)")
ax.set_ylabel("pairs")
ax.legend()
plt.show()
No pair of sites is coupled in either case. The shuffled columns still show some mutual information from finite sampling, and shared ancestry adds much more. A real alignment has both effects on top of the true couplings.
A cheap correction for the background is the average product correction (APC, Dunn and colleagues, 2008). Columns that are highly variable or sit in big clades have high mutual information with everything, so subtract the part explained by each column's average:
where is column 's mean over all partners and is the overall mean.
A global model separates direct from indirect
Chains of contacts need a different idea. Instead of scoring pairs one at a time, fit one model of the whole sequence and ask which pairs it needs. The model is a Potts model, a distribution over sequences with a field for every position and a coupling for every pair:
This is the Boltzmann distribution of unit 4 with an "energy" , and it is the maximum-entropy distribution that reproduces the alignment's single-column and pair frequencies and assumes nothing else. If A–B and B–C are coupled, the model can explain the A–C correlation through them, so it doesn't need a direct . Ranking pairs by the strength of is called direct coupling analysis (DCA).
Fitting exactly is expensive (computing sums over sequences), so methods approximate. The simplest, mean-field DCA, reads the couplings off the inverse of the covariance matrix of the one-hot encoded alignment, . If you know Gaussian graphical models, this is the same move: correlations in the covariance matrix include indirect paths, while the inverse (the precision matrix) holds conditional dependencies, the direct links. Better approximations (pseudo-likelihood methods such as plmDCA and GREMLIN) are more accurate, but the mean-field version fits in a few lines and is enough to see the effect:
from primer import structure, display_widget
# Weight each sequence by 1 / (number of sequences at least 80% identical to it), on a random subsample.
S = X[rng.choice(len(X), 20000, replace=False)]
onehot = np.eye(21, dtype=np.float32)[S].reshape(len(S), -1)
neighbors = np.concatenate([(onehot[k:k + 2000] @ onehot.T / L >= 0.8).sum(1) for k in range(0, len(S), 2000)])
w = 1 / neighbors
print(f"{len(S)} sequences, effective number {w.sum():.0f}")
W = w / w.sum()
fi = (W @ onehot).reshape(L, 21)
fij = ((onehot.T * W) @ onehot).reshape(L, 21, L, 21)
def apc(M):
M = M.copy()
np.fill_diagonal(M, 0)
row = M.sum(1) / (L - 1)
out = M - np.outer(row, row) / (M.sum() / (L * (L - 1)))
np.fill_diagonal(out, 0)
return out
mi = np.zeros((L, L))
for i in range(L):
for j in range(i + 1, L):
p, e = fij[i, :, j, :], np.outer(fi[i], fi[j])
nz = p > 0
mi[i, j] = mi[j, i] = (p[nz] * np.log(p[nz] / e[nz])).sum()
# Mean-field DCA: pseudocounts, covariance of the one-hot columns (gap state dropped), invert.
lam = 0.5
f1 = (1 - lam) * fi + lam / 21
f2 = (1 - lam) * fij + lam / 21**2
for i in range(L):
f2[i, :, i, :] = np.diag(f1[i])
C = (f2 - np.einsum("ia,jb->iajb", f1, f1))[:, :20, :, :20].reshape(L * 20, L * 20)
J = np.zeros((L, 21, L, 21))
J[:, :20, :, :20] = -np.linalg.inv(C).reshape(L, 20, L, 20)
J -= J.mean(1, keepdims=True) + J.mean(3, keepdims=True) - J.mean((1, 3), keepdims=True)
dca = apc(np.sqrt((J**2).sum((1, 3))))
# The truth: Cβ-Cβ distances in 1UBQ (Cα for glycine), residues 3-74.
chain = structure("1UBQ")[0]["A"]
beta = np.array([(chain[r]["CB"] if "CB" in chain[r] else chain[r]["CA"]).coord for r in range(3, 75)])
dist = np.linalg.norm(beta[:, None] - beta[None], axis=-1)
def precision(score, k=L // 2, sep=6, cutoff=8.0):
pairs = sorted(((score[i, j], i, j) for i in range(L) for j in range(i + sep, L)), reverse=True)[:k]
return np.mean([dist[i, j] < cutoff for _, i, j in pairs])
base = np.mean([dist[i, j] < 8 for i in range(L) for j in range(i + 6, L)])
print(f"fraction of top-scoring pairs that are contacts (random pairs: {base:.0%})")
print(f"{'':15s}" + "".join(f" top {k:3d}" for k in (L // 5, L // 2, L)))
for name, score in [("MI", mi), ("MI + APC", apc(mi)), ("mean-field DCA", dca)]:
print(f"{name:15s}" + "".join(f" {precision(score, k):7.0%}" for k in (L // 5, L // 2, L)))
rounded = lambda M: [[round(float(x), 4) for x in row] for row in M]
display_widget(
"coevolution-map",
"Ubiquitin's contacts (lower left) against the top-scoring column pairs from its family alignment (upper "
"right). Switch statistics and slide the number of pairs. Pairs fewer than six residues apart are left out, "
"since neighbors in sequence are always close. Hover a dot to see the residues and their real distance.",
sequence=ubq[2:74], first=3, dist=rounded(dist),
scores={"MI": rounded(mi), "MI + APC": rounded(apc(mi)), "Mean-field DCA": rounded(dca)},
)
20000 sequences, effective number 4939
fraction of top-scoring pairs that are contacts (random pairs: 6%)
top 14 top 36 top 72
MI 36% 28% 24%
MI + APC 64% 56% 43%
mean-field DCA 71% 56% 51%Ubiquitin's contacts (lower left) against the top-scoring column pairs from its family alignment (upper right). Switch statistics and slide the number of pairs. Pairs fewer than six residues apart are left out, since neighbors in sequence are always close. Hover a dot to see the residues and their real distance.
Against a 6% base rate, raw mutual information gets 24–36% of its top pairs right, APC lifts that to 43–64%, and even crude mean-field DCA reaches 51–71%, with its clearest lead on the strongest pairs. Pseudo-likelihood fits of the same model do better still on most families. The wrong predictions are instructive. Some sit a residue or two off a true contact. One DCA favorite links residue 3 with residue 74, the two ends of the domain, about 26 Å apart: many sequences in the family are fragments missing both ends, so the gaps co-occur. Gap correlations are a known artifact, and real pipelines filter for it.
From contacts to AlphaFold and language models
Predicted contacts turned out to be enough to fold proteins. In 2011 Debora Marks, Chris Sander, and colleagues fed the top couplings from deep family alignments as distance restraints into a structure builder and recovered correct folds for proteins of unknown structure. Through the late 2010s, deep networks learned to map coupling statistics to contact and then distance maps, and the accuracy of structure prediction rose sharply.
AlphaFold 2, presented in 2020, takes the multiple sequence alignment itself as input, not precomputed couplings. Its main module keeps two representations: one for the alignment (sequences × positions) and one for pairs of positions (positions × positions). Attention runs along the rows and columns of the alignment, and information flows from the alignment into the pair representation, which ends up encoding which residues are close. A structure module then turns the pair features into 3D coordinates. The network learns to extract the coevolution signal, which is why its accuracy drops for proteins with few relatives in the databases.
Protein language models such as ESM-2 skip the alignment. They are trained to predict masked residues across hundreds of millions of individual sequences. To do that well, a model has to learn which positions constrain which others across each family it sees, which is the same coevolution signal, learned implicitly. Contacts can be read off its attention maps with a simple linear model, and ESMFold builds structures from its internal representations. What these models learn is the distribution of sequences that evolution produced (lesson 5.1), so they are most accurate for families with many diverse members.
Check yourself
Two columns in an alignment are perfectly correlated: wherever column 12 has K, column 40 has E, and wherever column 12 has E, column 40 has K. All the K–E sequences come from one clade and all the E–K sequences from another. Is this strong evidence that residues 12 and 40 touch?
Reasoning
Not by itself. The pattern is what a compensatory salt-bridge swap would produce, but it is also what a single split in the tree would produce: one clade inherited K/E, the other E/K, and the correlation could come from shared ancestry even if the residues are far apart. The evidence is much stronger if the same paired switch happened independently in several separate branches, which is what phylogeny-aware methods, and to a lesser extent sequence weighting and APC, try to credit. Checking that both are surface or interface residues of opposite charge in a related structure would also help.
In a protein, residue 10 contacts residue 30 and residue 30 contacts residue 50, but 10 and 50 are 25 Å apart. Which method would you expect to rank the 10–50 pair higher, mutual information or DCA, and why?
Reasoning
Mutual information. It measures total dependence between two columns, including dependence relayed through residue 30, so 10–50 can score high. DCA fits all pairwise couplings at once: the correlation between 10 and 50 is explained by the couplings 10–30 and 30–50, so the model doesn't need a direct 10–50 coupling, and that pair's stays small. This is the precision-matrix idea: indirect correlations show up in the covariance but not in its inverse.
You want to predict the structure of a protein from a recently discovered virus. A database search finds only eight homologs, all over 90% identical to your sequence. What would you expect from coevolution-based contact prediction and from AlphaFold run with this alignment?
Reasoning
Little from coevolution. Eight near-identical sequences contain almost no substitutions, so there's nothing to correlate, and the effective number of sequences is about one. AlphaFold relies on the same signal and is typically much less accurate on such "orphan" proteins, though it can still do well when a related structure or a common fold gives it something to recognize. Protein language models face the same limit if the family is absent from their training data.