A lattice protein

Lab 4 of Biology Primer for Computer Scientists. Download the code as a notebook.

A real protein's conformation space is continuous and far too large to enumerate, so its partition function, density of states, and folding funnel can only be estimated. A lattice model makes all of them exact. In this lab you fold a 14-residue chain on a square grid, enumerate every conformation it can take, compute its thermodynamics from the partition function, sample it with Metropolis Monte Carlo, and then evaluate a simple force field on ubiquitin (1UBQ) to see what a real energy function rewards.

The model is the HP model of Ken Dill. Each residue is either hydrophobic (H) or polar (P). The chain occupies one lattice site per residue, can't cross itself, and gains energy −1 (in units of some interaction energy ε) for every pair of H residues that touch without being neighbors in the chain. It is the hydrophobic effect of lesson 1.5 reduced to a counting rule. Exhaustive search is an option here only because the model is so small:

A fully deterministic approach is an exhaustive search in which all of the investigated structural space is assessed in the same level of detail. Such a computationally intensive search is possible only for a small search space. Examples include highly simplified representations of structural space such as two-dimensional lattice models, where questions such as sequence designability can be approached analytically.

Task 1: represent a fold

Write a conformation as a string of moves, R, L, U, or D, one per bond, so a chain of n residues is a string of n−1 letters. Write a function that turns moves into coordinates, one that checks the chain doesn't cross itself, and an energy function that counts H–H contacts.

Solution
import numpy as np
import matplotlib.pyplot as plt

SEQ = "HPHPHPPHHHPHHH"
STEP = {"R": (1, 0), "L": (-1, 0), "U": (0, 1), "D": (0, -1)}

def coords(moves):
    pts = [(0, 0)]
    for m in moves:
        dx, dy = STEP[m]
        pts.append((pts[-1][0] + dx, pts[-1][1] + dy))
    return pts

def self_avoiding(pts):
    return len(set(pts)) == len(pts)

def energy(seq, pts):
    """-1 for each H-H pair on adjacent lattice sites that are not chain neighbors."""
    where = {p: i for i, p in enumerate(pts)}
    e = 0
    for i, (x, y) in enumerate(pts):
        if seq[i] != "H":
            continue
        for q in ((x + 1, y), (x, y + 1)):          # each pair counted once
            j = where.get(q)
            if j is not None and abs(i - j) > 1 and seq[j] == "H":
                e -= 1
    return e

straight = "R" * (len(SEQ) - 1)
hairpin = "RRRRRRUULLLLLL"[: len(SEQ) - 1]
for name, moves in [("straight", straight), ("hairpin", hairpin)]:
    pts = coords(moves)
    print(f"{name:8s} {moves}  self-avoiding={self_avoiding(pts)}  E={energy(SEQ, pts)}")
straight RRRRRRRRRRRRR  self-avoiding=True  E=0
hairpin  RRRRRRUULLLLL  self-avoiding=True  E=0

Task 2: enumerate every conformation

Generate every self-avoiding walk of 14 residues by depth-first search. A fold rotated or reflected is the same fold, so fix the first move to R and require the first move that isn't R to be U. That removes the 8-fold symmetry. Count the folds and compare with 413, the number of move strings. Then find the lowest energy and how many folds reach it.

Solution
import time

def enumerate_folds(n):
    out, moves = [], ["R"]
    pts, used = [(0, 0), (1, 0)], {(0, 0), (1, 0)}

    def grow(turned):
        if len(pts) == n:
            out.append("".join(moves))
            return
        x, y = pts[-1]
        for m, (dx, dy) in STEP.items():
            if not turned and m in "LD":            # symmetry: first turn is up
                continue
            p = (x + dx, y + dy)
            if p in used:
                continue
            pts.append(p); used.add(p); moves.append(m)
            grow(turned or m == "U")
            pts.pop(); used.discard(p); moves.pop()

    grow(False)
    return out

t = time.time()
folds = enumerate_folds(len(SEQ))
energies = np.array([energy(SEQ, coords(f)) for f in folds])
print(f"{len(folds):,} distinct folds (of 4^13 = {4**13:,} move strings), {time.time() - t:.1f} s")
E_min = energies.min()
native = [f for f, e in zip(folds, energies) if e == E_min]
print(f"lowest energy {E_min}, reached by {len(native)} fold(s): {native}")
110,188 distinct folds (of 4^13 = 67,108,864 move strings), 0.5 s
lowest energy -7, reached by 1 fold(s): ['RUULULDLDDRUR']

The count grows by a factor of about 2.64 per residue on a square lattice (and about 4.68 on a cubic one), so the same enumeration for 100 residues would need around 1042 folds: Levinthal's arithmetic, on a lattice. Below, the native fold is shown with one fold from each of the next two energy levels; draw your own and try to beat it.

Code
from primer import display_widget

def example(e):
    return next(f for f, x in zip(folds, energies) if x == e)

display_widget(
    "hp-lattice",
    "The native fold of HPHPHPPHHHPHHH and two folds from the next energy levels. "
    "“Draw your own” places beads one at a time, starting from the N-terminal bead; try to find the native fold.",
    sequence=SEQ,
    presets=[[f"native (E = {E_min})", native[0]],
             [f"E = {E_min + 1}", example(E_min + 1)],
             [f"E = {E_min + 2}", example(E_min + 2)]],
)

Loading the interactive figure…

The native fold of HPHPHPPHHHPHHH and two folds from the next energy levels. “Draw your own” places beads one at a time, starting from the N-terminal bead; try to find the native fold.

Task 3: the density of states

Count how many folds have each energy. This density of states g(E) is the landscape of lesson 4.4, reduced to a histogram: what fraction of the space is near the bottom?

Solution
levels, counts = np.unique(energies, return_counts=True)
for e, c in zip(levels, counts):
    print(f"E = {e:3d}: {c:7,d} folds")

fig, ax = plt.subplots()
ax.bar(levels, counts, color="#2a78d6", width=0.8)
ax.set_yscale("log")
ax.set_xlabel("energy (ε)")
ax.set_ylabel("number of folds (log scale)")
plt.show()
E =  -7:       1 folds
E =  -6:       9 folds
E =  -5:     132 folds
E =  -4:     646 folds
E =  -3:   2,778 folds
E =  -2:  11,967 folds
E =  -1:  31,726 folds
E =   0:  62,929 folds
−7 −6 −5 −4 −3 −2 −1 0 energy (ε) 1 0 0 1 0 1 1 0 2 1 0 3 1 0 4 1 0 5 number of folds (log scale)

One fold sits at the bottom, nine one step up, and 57% of all folds have no H–H contact at all. A funnel is this histogram plus the fact that low-energy folds resemble each other.

Task 4: thermodynamics from the partition function

With every state enumerated, the partition function is exact: Z(T)=∑Eg(E)e−E/T in reduced units (kB=1, energies in ε). Compute the native fraction against temperature, which is the melting curve, and the heat capacity C=Var(E)/T2, which peaks where the chain melts.

Solution
T = np.linspace(0.05, 2.0, 400)

def thermo(T):
    w = counts * np.exp(-(levels - E_min) / T)       # shift by E_min for numerical stability
    Z = w.sum()
    p_native = w[0] / Z                              # levels[0] is E_min: the native fold
    mean = (levels * w).sum() / Z
    var = (levels**2 * w).sum() / Z - mean**2
    return p_native, var / T**2

p_native, heat = np.array([thermo(t) for t in T]).T
T_peak = T[np.argmax(heat)]
T_half = T[np.argmin(abs(p_native - 0.5))]
print(f"native fraction is 1/2 at T = {T_half:.2f}; heat capacity peaks at T = {T_peak:.2f}")

fig, ax = plt.subplots()
ax.plot(T, p_native, label="fraction in the native fold")
ax.plot(T, heat / heat.max(), label="heat capacity (scaled to 1)")
ax.set_xlabel("temperature (ε / k)")
ax.set_ylabel("value")
ax.legend()
plt.show()
native fraction is 1/2 at T = 0.34; heat capacity peaks at T = 0.43
0.00 0.25 0.50 0.75 1.00 1.25 1.50 1.75 2.00 temperature (ε / k) 0.0 0.2 0.4 0.6 0.8 1.0 value fraction in the native fold heat capacity (scaled to 1)

The melting is gradual because 14 residues is tiny. Real proteins have thousands of times more unfolded states, which makes their transitions sharp and cooperative.

Task 5: Metropolis Monte Carlo

Pretend you can't enumerate, and sample the chain with Metropolis moves instead. Use two kinds of move: a pivot, which rotates or reflects everything after a random residue about that residue, and a local move, which flips one residue across a corner or swings a chain end to another free site. Reject any move that makes the chain cross itself, and otherwise accept it with probability min⁡(1,e−ΔE/T). Run three independent chains at each of several temperatures and compare their native fractions with the exact ones from Task 4.

Solution
TRANSFORMS = [lambda x, y: (-y, x), lambda x, y: (-x, -y), lambda x, y: (y, -x),   # rotations
              lambda x, y: (x, -y), lambda x, y: (-x, y)]                          # reflections

def pivot(pts, rng):
    i = rng.integers(1, len(pts) - 1)
    f = TRANSFORMS[rng.integers(len(TRANSFORMS))]
    cx, cy = pts[i]
    tail = [f(x - cx, y - cy) for x, y in pts[i + 1:]]
    return pts[: i + 1] + [(cx + dx, cy + dy) for dx, dy in tail]

def local(pts, rng):
    i = rng.integers(len(pts))
    new = list(pts)
    if i in (0, len(pts) - 1):                       # end move: next to its neighbor, any direction
        nx, ny = pts[1 if i == 0 else -2]
        dx, dy = list(STEP.values())[rng.integers(4)]
        new[i] = (nx + dx, ny + dy)
        return new
    (ax, ay), (bx, by) = pts[i - 1], pts[i + 1]
    if ax == bx or ay == by:                         # straight segment: no corner to flip
        return pts
    new[i] = (ax + bx - pts[i][0], ay + by - pts[i][1])
    return new

def metropolis(T, steps, seed):
    rng = np.random.default_rng(seed)
    pts, e = coords(straight), 0
    native_steps = 0
    for _ in range(steps):
        new = local(pts, rng) if rng.random() < 0.5 else pivot(pts, rng)
        if self_avoiding(new):
            e_new = energy(SEQ, new)
            if e_new <= e or rng.random() < np.exp(-(e_new - e) / T):
                pts, e = new, e_new
        native_steps += e == E_min
    return native_steps / steps

for temp in (0.3, 0.5, 1.0):
    runs = [metropolis(temp, 100_000, seed) for seed in range(3)]
    print(f"T = {temp}: exact native fraction {thermo(temp)[0]:.3f}; three runs give "
          + ", ".join(f"{r:.3f}" for r in runs))
T = 0.3: exact native fraction 0.656; three runs give 0.000, 0.000, 0.000
T = 0.5: exact native fraction 0.126; three runs give 0.209, 0.078, 0.001
T = 1.0: exact native fraction 0.003; three runs give 0.005, 0.005, 0.002

At T = 1.0 the runs agree with the exact answer. At 0.5 they disagree with each other by more than a factor of ten. At 0.3, where the chain should spend two-thirds of its time native, no run ever gets there: each settles into a near-native trap, and uphill moves out of it are almost never accepted. This is the sampling problem of lesson 4.2, on a system small enough that you know the right answer. Simulated annealing is the standard fix when the goal is the minimum rather than the distribution: start hot and cool slowly.

Solution
def anneal(steps, seed, T_hot=1.5, T_cold=0.15):
    rng = np.random.default_rng(seed)
    pts, e, best = coords(straight), 0, 0
    for s in range(steps):
        T = T_hot * (T_cold / T_hot) ** (s / steps)  # geometric cooling
        new = local(pts, rng) if rng.random() < 0.5 else pivot(pts, rng)
        if self_avoiding(new):
            e_new = energy(SEQ, new)
            if e_new <= e or rng.random() < np.exp(-(e_new - e) / T):
                pts, e = new, e_new
        best = min(best, e)
    return e, best

results = [anneal(100_000, seed) for seed in range(6)]
print("final energies:", [r[0] for r in results])
print("best energies: ", [r[1] for r in results])
final energies: [-6, -6, -6, -6, -6, -7]
best energies:  [-7, -6, -7, -7, -7, -7]

Five of the six runs visit the native energy at some point, and only one ends there. The cooling schedule is still too fast for the chain to settle reliably, and in practice annealing protocols keep the best structure seen, not the last one.

Task 6: a force field on a real protein

Now leave the lattice. A force field (lesson 4.4) rewards close packing through its Lennard-Jones term and punishes clashes. Evaluate a minimal version on ubiquitin's heavy atoms (every atom except hydrogen, which most crystal structures leave out): one Lennard-Jones type for every atom, formal charges (a whole +1 or −1 on each charged group) on the charged side chains and chain ends, and a distance-dependent dielectric (ϵ=4r, a cheap stand-in for the screening by water of lesson 1.4). Compare the native structure with two decoys: every atom jittered by 0.5 Å, and the whole protein expanded by 10%. Then minimize the jittered decoy by gradient descent, holding bonded atoms at their native separations with stiff springs, and see what minimization can and can't recover.

Solution
from primer import structure

atoms = [a for a in structure("1UBQ")[0].get_atoms()
         if a.get_parent().id[0] == " " and a.element != "H"]
X0 = np.array([a.coord for a in atoms], dtype=float)
CHARGES = {("LYS", "NZ"): 1.0, ("ARG", "NH1"): 0.5, ("ARG", "NH2"): 0.5,
           ("ASP", "OD1"): -0.5, ("ASP", "OD2"): -0.5, ("GLU", "OE1"): -0.5, ("GLU", "OE2"): -0.5}
q = np.array([CHARGES.get((a.get_parent().get_resname(), a.get_id()), 0.0) for a in atoms])
q[[i for i, a in enumerate(atoms) if a.get_id() == "N"][0]] += 1.0       # N-terminus
q[[i for i, a in enumerate(atoms) if a.get_id() == "OXT"][0]] -= 1.0     # C-terminus

# Covalent graph from native distances. Like real force fields, leave atoms 1, 2, or 3 bonds apart out of
# the nonbonded sum; springs on the 1-2 and 1-3 pairs keep bond lengths and angles during minimization.
D0 = np.linalg.norm(X0[:, None] - X0[None], axis=-1)
bonded = (D0 < 1.9) & ~np.eye(len(X0), dtype=bool)
hops = lambda m: (m.astype(int) @ bonded.astype(int)) > 0
near13 = bonded | hops(bonded)
near14 = near13 | hops(near13)
I, J = np.nonzero(np.triu(~near14, k=1))
B_i, B_j = np.nonzero(np.triu(near13, k=1))
B_len = D0[B_i, B_j]

SIGMA, EPS = 3.2, 0.1                                                      # Å, kcal/mol

def nonbonded(X):
    d = X[I] - X[J]
    r = np.linalg.norm(d, axis=1)
    sr6 = (SIGMA / r) ** 6
    lj = 4 * EPS * (sr6**2 - sr6)
    coul = 332 * q[I] * q[J] / (4 * r * r)                                 # dielectric 4r
    dE_dr = 4 * EPS * (-12 * sr6**2 + 6 * sr6) / r - 2 * 332 * q[I] * q[J] / (4 * r**3)
    return lj.sum(), coul.sum(), d, r, dE_dr

def total(X, k=300.0):
    lj, coul, d, r, dE_dr = nonbonded(X)
    b = X[B_i] - X[B_j]
    bl = np.linalg.norm(b, axis=1)
    spring = k * ((bl - B_len) ** 2).sum()
    grad = np.zeros_like(X)
    g = (dE_dr / r)[:, None] * d
    np.add.at(grad, I, g); np.add.at(grad, J, -g)
    gb = (2 * k * (bl - B_len) / bl)[:, None] * b
    np.add.at(grad, B_i, gb); np.add.at(grad, B_j, -gb)
    return lj + coul + spring, lj, coul, grad

def rmsd(X):
    return np.sqrt(((X - X0) ** 2).sum(axis=1).mean())

rng = np.random.default_rng(0)
jittered = X0 + rng.normal(0, 0.5, X0.shape)
center = X0.mean(axis=0)
expanded = center + 1.10 * (X0 - center)

X = jittered.copy()
for _ in range(500):                                                       # steepest descent with a step cap
    _, _, _, grad = total(X)
    step = 0.002 * grad
    norms = np.linalg.norm(step, axis=1, keepdims=True)
    X -= step * np.minimum(1.0, 0.1 / np.maximum(norms, 1e-9))

print(f"{'structure':22s} {'LJ':>12s} {'Coulomb':>9s} {'RMSD (Å)':>9s}   (kcal/mol)")
for name, Y in [("native", X0), ("jittered 0.5 Å", jittered), ("expanded 10%", expanded), ("jittered, minimized", X)]:
    _, lj, coul, _ = total(Y)
    print(f"{name:22s} {lj:12.1f} {coul:9.1f} {rmsd(Y):9.2f}")
structure                        LJ   Coulomb  RMSD (Å)   (kcal/mol)
native                       -262.7     -31.9      0.00
jittered 0.5 Å              10204.8     -29.2      0.86
expanded 10%                 -217.0     -26.4      1.17
jittered, minimized          -298.8     -37.3      0.62

Read the table row by row. Jittering by half an ångström wrecks the Lennard-Jones energy, because a few atoms now overlap and the r−12 wall dominates. Expanding the protein by 10% costs about 45 kcal/mol of van der Waals attraction from the packed core. Minimization removes the clashes, and with this crude force field it goes further: it finds a structure that scores better than native and is still 0.6 Å away from it. The minimum of this energy function is not the native structure. One atom type, no hydrogens, no hydrogen-bond geometry, and no solvent (so charged groups attract each other as if water weren't there) are enough to move the minimum. Real force fields have atom-specific parameters and solvation terms and do much better, but the same gap, smaller, is why structures predicted by minimizing an energy function drift away from the experimental ones.

Ubiquitin as space-filling atoms, colored by residue class. The tight packing you see is what the Lennard-Jones attraction rewards, and what both decoys destroyed in different ways.

Open 1UBQ in Mol*

In Mol* or ChimeraX, open 1UBQ and display the surface. Compare the surface with the space-filling view above, and look for places in the core where no probe sphere fits. Those well-packed regions are where the Lennard-Jones energy is most favorable.

Self-check

In the HP sequence used here, which single H→P mutation would you expect to destabilize the native fold most? How would you check your guess with the code above?

Reasoning

The H residue with the most H–H contacts in the native fold. Changing it to P removes all of those contacts, so the native energy rises by that number, while competing folds that didn't use that residue's contacts are unaffected. The gap between native and the next level shrinks or vanishes, and the native fold may stop being unique. To check: for each H position, rebuild the sequence with a P there, recompute energies over folds, and compare the new native energy, the number of folds at it, and the gap to the next level. That is a lattice ΔΔG calculation.

The heat-capacity curve peaks at a temperature. What is happening to the chain at that temperature, and why does a sharper peak mean a more cooperative, two-state protein?

Reasoning

C=Var(E)/T2 is largest where the energy fluctuates most, which is where low-energy (folded) and high-energy (unfolded) states are both well populated and the chain flips between them: the melting transition. If folding is two-state, the population jumps from mostly native to mostly unfolded over a narrow temperature range, so the variance spikes there and the peak is narrow and tall. A broad peak means many intermediate energies are populated along the way, which is gradual, non-cooperative melting, as in this 14-mer.

A buried leucine in a real protein's core is mutated to alanine. Predict the sign and rough size of ΔΔG (stability of mutant minus wild type), and say which terms of the force field above account for it.

Reasoning

Destabilizing, typically by 2–5 kcal/mol. Alanine's side chain is three carbons shorter, so the mutation leaves a cavity in the core. In force-field terms, the Lennard-Jones attraction between the lost atoms and their neighbors disappears; this is the expanded decoy's problem in miniature. In free-energy terms, a buried hydrophobic group no longer hides from water in the unfolded state, so the hydrophobic driving force (a solvation term) drops too.

Two mutations are proposed for the middle of a long α-helix on the surface: glycine to alanine, and alanine to proline. Predict the direction of each ΔΔG and explain using both energy and entropy.

Reasoning

Gly→Ala usually stabilizes the helix, by up to about 1 kcal/mol. Glycine has no side chain, so its backbone is unusually flexible in the unfolded state (lesson 3.2). Fixing it in the helix costs more conformational entropy than fixing alanine does, so replacing it lowers the entropy penalty of folding. Ala→Pro in the middle of a helix destabilizes it strongly, typically by 3 kcal/mol or more. Proline's ring locks its φ angle and its nitrogen has no hydrogen to donate, so it breaks the i→i+4 hydrogen bond and clashes with the preceding turn. That is an energy cost, which no entropy gain makes up.

Your Metropolis run at low temperature reports a native fraction of 0.0, while the exact calculation says 0.9. The code has no bugs. What happened, and what would you change?

Reasoning

The run never reached the native fold, or reached it late and too briefly to matter. At low temperature, uphill moves are almost never accepted, so a walker that settles into a near-native trap stays there; the sampler isn't ergodic on the time scale of the run. Run longer, start several runs from different folds, or use annealing or replica exchange (run several temperatures and swap configurations) so the walker can cross barriers while hot and settle while cold. The exact answer is only available because the model is small enough to enumerate. For a real protein, disagreement between independent runs is the warning sign.