Introduction

A protein begins life as a floppy chain of amino acids — a string of chemical "beads." Within moments it collapses into a precise, intricate 3D shape, and that shape is everything: it decides whether the protein becomes an enzyme, a sensor, a motor, or, when folding goes wrong, the cause of a disease.

So here's the dream: given just the sequence of beads, predict the shape it will fold into. The rules are physics — the chain settles into its lowest-energy arrangement. Why not just compute that?

Because the number of possible shapes is astronomical. A modest protein has more conformations than there are atoms in the universe — yet it folds in microseconds. That clash between "too many shapes to search" and "nature does it instantly" is Levinthal's paradox. And in simplified models, finding the best fold is provably NP-hard.

Fold It

Try it — with a classic toy version, the HP model. The chain has two bead types: H (hydrophobic, "oily") and P (polar). H beads like to huddle together away from water, so every time two H beads end up neighbors on the grid (without being neighbors in the chain), the fold gets one unit more stable.

<p class="hint">The chain has <span class="h">H</span> (oily) and <span class="p">P</span> (polar)
    beads. Click a bead to bend the chain there. Pack the <span class="h">H</span> beads so they
    touch on the grid — each H–H contact lowers the <b>energy</b>.</p>
<svg id="plot" viewBox="0 0 300 240" class="plot"></svg>
<div class="meter">
  <div>Energy: <b id="energy" class="en">0</b></div>
  <div>H–H contacts: <b id="contacts">0</b></div>
  <div id="state" class="state"></div>
</div>
<div class="btns">
  <button id="best" type="button">Best fold</button>
  <button id="reset" type="button" class="ghost">Straighten</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.hint .h { color: #c0392b; font-weight: 800; } .hint .p { color: #457b9d; font-weight: 800; }
.plot { width: 100%; max-width: 380px; background: #f4f7f9; border: 1px solid #e2e6eb; border-radius: 10px; display: block; }
.bond { stroke: #6a7b88; stroke-width: 3; }
.contact { stroke: #e9b44c; stroke-width: 3; stroke-dasharray: 3 3; }
.bead { cursor: pointer; stroke: #fff; stroke-width: 2; }
.bead.h { fill: #c0392b; } .bead.p { fill: #457b9d; }
.blbl { fill: #fff; font: 800 11px ui-monospace, monospace; text-anchor: middle; dominant-baseline: central; pointer-events: none; }
.meter { display: flex; gap: 1.3rem; align-items: center; margin: .8rem 0 .6rem; font-size: 1rem; flex-wrap: wrap; }
.meter b { color: #1d3557; font-family: ui-monospace, monospace; }
.en { color: #0a7d33 !important; }
.state { font-weight: 700; }
.state.bad { color: #c0392b; }
.btns { display: flex; gap: .5rem; }
button { font: 600 14px system-ui, sans-serif; padding: .5rem 1rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #457b9d; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// HP lattice model of protein folding. Beads are H (hydrophobic) or P (polar).
// Energy = -(number of H-H lattice contacts that aren't chain neighbors).
// Finding the minimum-energy fold is NP-hard; here we brute-force a length-12 chain.
const SEQ = 'HPHPPHHPHPPH';
const N = SEQ.length;
const DIRS = [[1, 0], [0, -1], [-1, 0], [0, 1]]; // E, N, W, S
let turns = new Array(N - 2).fill(0); // 0 straight, 1 left, 2 right

function positions(turns) {
  const pos = [[0, 0]]; let d = 0; // start East
  for (let k = 0; k < N - 1; k++) {
    if (k >= 1) { const t = turns[k - 1]; if (t === 1) d = (d + 1) % 4; else if (t === 2) d = (d + 3) % 4; }
    const [x, y] = pos[pos.length - 1]; pos.push([x + DIRS[d][0], y + DIRS[d][1]]);
  }
  return pos;
}
function valid(pos) { const seen = new Set(); for (const [x, y] of pos) { const k = x + ',' + y; if (seen.has(k)) return false; seen.add(k); } return true; }
function contacts(pos) {
  let c = 0;
  for (let i = 0; i < N; i++) for (let j = i + 2; j < N; j++) {
    if (SEQ[i] === 'H' && SEQ[j] === 'H' && Math.abs(pos[i][0] - pos[j][0]) + Math.abs(pos[i][1] - pos[j][1]) === 1) c++;
  }
  return c;
}

function render() {
  const pos = positions(turns);
  const ok = valid(pos);
  // fit to view
  const xs = pos.map(p => p[0]), ys = pos.map(p => p[1]);
  const minX = Math.min(...xs), maxX = Math.max(...xs), minY = Math.min(...ys), maxY = Math.max(...ys);
  const span = Math.max(maxX - minX, maxY - minY, 1);
  const S = Math.min(200 / span, 40); const ox = 150 - (minX + maxX) / 2 * S, oy = 120 - (minY + maxY) / 2 * S;
  const sx = x => ox + x * S, sy = y => oy + y * S;
  let s = '';
  for (let k = 0; k < N - 1; k++) s += '<line class="bond" x1="' + sx(pos[k][0]) + '" y1="' + sy(pos[k][1]) + '" x2="' + sx(pos[k + 1][0]) + '" y2="' + sy(pos[k + 1][1]) + '"/>';
  if (ok) for (let i = 0; i < N; i++) for (let j = i + 2; j < N; j++) if (SEQ[i] === 'H' && SEQ[j] === 'H' && Math.abs(pos[i][0] - pos[j][0]) + Math.abs(pos[i][1] - pos[j][1]) === 1) s += '<line class="contact" x1="' + sx(pos[i][0]) + '" y1="' + sy(pos[i][1]) + '" x2="' + sx(pos[j][0]) + '" y2="' + sy(pos[j][1]) + '"/>';
  pos.forEach(([x, y], i) => { s += '<circle class="bead ' + (SEQ[i] === 'H' ? 'h' : 'p') + '" cx="' + sx(x) + '" cy="' + sy(y) + '" r="' + (S * 0.32) + '" data-i="' + i + '"/>'; s += '<text class="blbl" x="' + sx(x) + '" y="' + sy(y) + '">' + SEQ[i] + '</text>'; });
  document.getElementById('plot').innerHTML = s;
  document.getElementById('plot').querySelectorAll('.bead').forEach(el => el.addEventListener('click', () => { const i = +el.dataset.i; if (i >= 1 && i <= N - 2) { turns[i - 1] = (turns[i - 1] + 1) % 3; render(); } }));
  const c = ok ? contacts(pos) : 0;
  document.getElementById('contacts').textContent = c;
  document.getElementById('energy').textContent = ok ? (-c) : '—';
  const st = document.getElementById('state');
  if (!ok) { st.className = 'state bad'; st.textContent = '✗ chain crosses itself — invalid'; }
  else if (c === BEST) { st.className = 'state'; st.style.color = '#0a7d33'; st.textContent = '✓ optimal fold!'; }
  else { st.className = 'state'; st.style.color = '#777'; st.textContent = fmt('best possible is %v% (click beads to bend)', { v: -BEST }); }
}

let BEST = 0, BESTTURNS = null;
(function solve() {
  const tot = Math.pow(3, N - 2); const t = new Array(N - 2).fill(0);
  for (let m = 0; m < tot; m++) {
    let mm = m; for (let i = 0; i < N - 2; i++) { t[i] = mm % 3; mm = Math.floor(mm / 3); }
    const pos = positions(t); if (!valid(pos)) continue; const c = contacts(pos);
    if (c > BEST) { BEST = c; BESTTURNS = t.slice(); }
  }
})();

document.getElementById('best').addEventListener('click', () => { turns = BESTTURNS.slice(); render(); });
document.getElementById('reset').addEventListener('click', () => { turns = new Array(N - 2).fill(0); render(); });
render();
Result
Console

Click a joint to bend the chain; keep it from crossing itself. Try to pack the H beads together to make the energy as low (negative) as possible, then hit Best fold to see the optimum. Even on this tiny grid, finding it by hand is fiddly — and the real problem, in 3D with 20 amino acids, is NP-hard.

The Hard Part

Folding is hardness with a famous plot twist:

  • The search space is astronomical. A chain of n residues has exponentially many conformations — Levinthal's paradox: sampling them one by one would take longer than the universe has existed.
  • It's NP-hard. Even in stripped-down lattice HP models, finding the minimum-energy fold is provably NP-hard. The real 3D, full-chemistry problem is at least as hard.
  • Yet nature folds instantly. Proteins don't search; physics funnels them down an energy landscape to the right shape in microseconds. The paradox is resolved by the shape of that landscape, not by brute force.
  • The AlphaFold revolution. In 2020, DeepMind's AlphaFold predicted structures with near-experimental accuracy — not by solving the NP-hard optimization, but by learning patterns from ~150,000 known structures with deep neural networks. It was hailed as solving a 50-year grand challenge.
  • What's left. Folding dynamics, misfolding, protein design and interactions remain open — prediction got dramatically easier, but the physics isn't fully "solved."

So protein folding is the rare hard problem where the breakthrough came from sidestepping the computation entirely — letting learned intuition do what optimization couldn't.

Where It Matters

Knowing a protein's shape unlocks much of modern biomedicine:

  • Drug discovery: designing molecules that fit a target protein's exact shape.
  • Disease: misfolding underlies Alzheimer's, Parkinson's, cystic fibrosis and more.
  • Enzyme and protein design: engineering new catalysts and materials from scratch.
  • Vaccines: designing antigens by understanding viral protein structures.
  • Basic biology: AlphaFold has predicted structures for nearly every known protein, a vast public resource.

A problem once measured in years-per-protein in the lab is now, for prediction, often minutes on a computer — reshaping how biology is done.

Conclusion

Protein folding is the hard-problem story with the most dramatic ending so far. The search space is beyond astronomical, the optimization NP-hard, the paradox baked right in — and yet nature folds proteins in a blink, and now, so do machines. The twist is how: AlphaFold didn't conquer the NP-hard search; it learned the answer's shape from data, the same move that powers neural-network training.

It's the most hopeful note this site can strike. A problem feared unsolvable for half a century gave way — not to a faster brute-force, but to a different kind of intelligence. Sometimes the path past a hard problem isn't a better algorithm for the answer, but a machine that has seen enough answers to guess the next one right.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/protein-folding/Content licensed under CC BY-NC 4.0.