Introduction

RNA is life's busy middle-manager: a single strand spelled from just four letters — A, U, G, C — that carries genetic instructions and runs countless tasks inside the cell. Unlike its double-stranded cousin DNA, RNA floats around alone, and a lonely strand does something remarkable: it folds back onto itself.

The folding follows one simple rule. Certain letters like to stick together — A pairs with U, G pairs with C — so the strand bends and zips up wherever complementary letters can meet. The resulting pattern of pairs is called the secondary structure, and it largely decides what the molecule actually does.

Here is the catch. A strand of length n can fold in an astronomical number of ways — the count grows faster than exponentially. Searching them all by hand is hopeless. So how does a computer find the best fold — the one with the most base pairs — without checking them one by one?

Fold a Strand

Type a short RNA strand below (letters A, U, G, C). The demo runs Nussinov's algorithm: it builds a table where each cell holds the most base pairs achievable on one sub-stretch of the strand. Bigger stretches are built from smaller ones already solved — so the table fills from the diagonal outward, and the top-right corner is the answer.

<p class="hint">Type a short RNA strand (letters A, U, G, C). Nussinov’s algorithm fills a table: cell (i,j) holds the most base pairs achievable on the sub-stretch from position i to j. Press <b>Fold</b> and watch it fill from the diagonal outward — the top-right corner is the best fold.</p>
<div class="row">
  <input id="seq" type="text" value="GGGAAAUCC" maxlength="14" spellcheck="false" />
  <button id="fold" type="button">Fold</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<div id="table" class="table"></div>
<div class="status" id="status">Press Fold to run Nussinov’s algorithm.</div>
<div id="pairs" class="pairs"></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; }
.row { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .7rem; }
input { font: 700 16px ui-monospace, monospace; letter-spacing: 2px; text-transform: uppercase;
        padding: .4rem .6rem; border: 1px solid #1d3557; border-radius: 8px; width: 11rem; }
.table { display: inline-grid; gap: 2px; margin: .3rem 0; }
.c { width: 34px; height: 34px; display: flex; align-items: center; justify-content: center;
     font: 600 14px ui-monospace, monospace; border-radius: 6px; }
.hd { background: #1d3557; color: #fff; }
.dg { background: #eef2f6; color: #aab4bf; }
.cell { background: #e8eef3; color: #1d3557; border: 1px solid #cdd9e3; }
.cell.fill { animation: pop .25s ease; background: #cfe3d6; border-color: #9ccfae; }
.cell.corner { background: #0a7d33; color: #fff; border-color: #0a7d33; }
@keyframes pop { from { transform: scale(.6); opacity: .2; } to { transform: scale(1); opacity: 1; } }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0 .3rem; min-height: 1.4em; color: #0a7d33; }
.pairs { font: 600 15px ui-monospace, monospace; color: #1d3557; min-height: 1.4em; word-break: break-all; }
.btns { display: flex; gap: .5rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Nussinov (1978): find the secondary structure of an RNA strand that maximizes
// the number of valid base pairs (A-U and G-C, here also G-U wobble off for clarity).
// DP table M[i][j] = max pairs on substring s[i..j]. Recurrence, for i<j:
//   M[i][j] = max( M[i+1][j],                                   // i unpaired
//                  max over k in (i,j] of: pair(i,k)+M[i+1][k-1]+M[k+1][j] )
// A min loop length keeps a base from pairing with an immediate neighbor.
const MINLOOP = 1;
const canPair = (a, b) => (a==='A'&&b==='U')||(a==='U'&&b==='A')||(a==='G'&&b==='C')||(a==='C'&&b==='G');

function nussinov(s){
  const n = s.length;
  const M = Array.from({length:n}, () => new Array(n).fill(0));
  // fill by increasing substring length
  for(let len=2; len<=n; len++){
    for(let i=0; i+len-1<n; i++){
      const j = i+len-1;
      let best = M[i+1][j];                     // i unpaired
      for(let k=i+1; k<=j; k++){
        if(k-i>MINLOOP && canPair(s[i],s[k])){
          const inner = (i+1<=k-1) ? M[i+1][k-1] : 0;
          const outer = (k+1<=j)   ? M[k+1][j]   : 0;
          best = Math.max(best, 1 + inner + outer);
        }
      }
      M[i][j] = best;
    }
  }
  return M;
}
// Traceback to recover the actual list of pairs (i,j) of one optimal fold.
function traceback(s, M){
  const pairs = [];
  (function rec(i,j){
    if(i>=j) return;
    if(M[i][j]===M[i+1][j]){ rec(i+1,j); return; }
    for(let k=i+1; k<=j; k++){
      if(k-i>MINLOOP && canPair(s[i],s[k])){
        const inner=(i+1<=k-1)?M[i+1][k-1]:0, outer=(k+1<=j)?M[k+1][j]:0;
        if(M[i][j]===1+inner+outer){ pairs.push([i,k]); rec(i+1,k-1); rec(k+1,j); return; }
      }
    }
  })(0, s.length-1);
  return pairs;
}

let timer = null;
function clean(v){ return (v||'').toUpperCase().replace(/[^AUGC]/g,'').slice(0,14); }

function render(s, M, shown){
  const n=s.length, t=document.getElementById('table');
  t.style.gridTemplateColumns = `repeat(${n+1}, 34px)`;
  t.innerHTML='';
  t.appendChild(div('c hd',''));
  for(let j=0;j<n;j++) t.appendChild(div('c hd', s[j]));
  for(let i=0;i<n;i++){
    t.appendChild(div('c hd', s[i]));
    for(let j=0;j<n;j++){
      if(j<i){ t.appendChild(div('c dg','')); continue; }
      if(j===i){ t.appendChild(div('c dg','0')); continue; }
      const isShown = shown.has(i+','+j);
      const corner = (i===0 && j===n-1 && isShown);
      const cls='c cell'+(isShown?' fill':'')+(corner?' corner':'');
      t.appendChild(div(cls, isShown ? String(M[i][j]) : ''));
    }
  }
}
function div(cls,txt){ const d=document.createElement('div'); d.className=cls; d.textContent=txt; return d; }

function run(){
  if(timer){ clearInterval(timer); timer=null; }
  const s = clean(document.getElementById('seq').value);
  document.getElementById('seq').value = s;
  document.getElementById('pairs').textContent='';
  if(s.length<2){ document.getElementById('status').textContent='Enter at least 2 letters.'; render(s,[],new Set()); return; }
  const M = nussinov(s);
  // animate the fill order: by increasing length
  const order=[];
  for(let len=2; len<=s.length; len++) for(let i=0;i+len-1<s.length;i++) order.push([i,i+len-1]);
  const shown=new Set(); let idx=0;
  render(s,M,shown);
  document.getElementById('status').textContent='Filling the table, shorter stretches first
';
  timer=setInterval(()=>{
    if(idx>=order.length){
      clearInterval(timer); timer=null;
      const best=M[0][s.length-1];
      document.getElementById('status').textContent=fmt('Best fold: %best% base pair%v%.', { best: best, v: best===1?'':'s' });
      const ps=traceback(s,M).sort((a,b)=>a[0]-b[0]);
      document.getElementById('pairs').textContent = s+'\n'+notation(s,ps);
      console.log('seq',s,'maxPairs',best,'pairs',JSON.stringify(ps));
      return;
    }
    const [i,j]=order[idx++]; shown.add(i+','+j); render(s,M,shown);
  }, 90);
}
function notation(s,pairs){
  const a=new Array(s.length).fill('.');
  pairs.forEach(([i,j])=>{a[i]='(';a[j]=')';});
  return a.join('');
}
document.getElementById('fold').addEventListener('click',run);
document.getElementById('reset').addEventListener('click',()=>{
  if(timer){clearInterval(timer);timer=null;}
  document.getElementById('seq').value='GGGAAAUCC';
  document.getElementById('status').textContent='Press Fold to run Nussinov’s algorithm.';
  document.getElementById('pairs').textContent='';
  document.getElementById('table').innerHTML='';
});
run();
Result
Console

Notice what the table is doing. To find the best fold of a stretch, it only ever combines answers it has already computed for shorter stretches. Nothing is recomputed and nothing is brute-forced. A problem with astronomically many possible folds collapses into a tidy grid of n × n cells — the signature move of dynamic programming.

The Real Complexity

How hard is it to fold RNA? For the clean version of the question, the answer is a happy surprise: it is easy.

  • The search space is enormous. A strand of length n admits a number of valid foldings that grows super-exponentially — far too many to enumerate.
  • Yet it is solved, and in polynomial time. In 1978, biophysicist Ruth Nussinov introduced a dynamic-programming algorithm that finds the fold maximizing the number of base pairs without ever listing the folds. It runs in O(n3)O(n^{3}) time and O(n2)O(n^{2}) space.
  • That puts it inside P. Because n3n^{3} is a polynomial, predicting the maximum-pairing secondary structure is firmly among the tractable problems — the easy side of P vs NP.
  • The trick is overlapping sub-problems. The best fold of a long stretch reuses the best folds of its inner stretches. Solve every short stretch once, store it, and snap the long answers together.

The lesson is the reverse of most stories on this site. A problem can look impossibly large — astronomically many shapes — and still be genuinely easy, once you spot that its pieces overlap. Not every big search is a hard problem.

(The full chemistry is harder: realistic energy models, "pseudoknots," and 3-D structure push beyond Nussinov's clean rule, and some of those richer variants become NP-hard. But the core base-pair-maximization problem is solved.)

Where It Matters

Knowing an RNA's shape means knowing much of its function — so the fold matters far beyond the textbook:

  • Medicine and vaccines: the stability and behavior of an mRNA vaccine depend on how its strand folds, and structure-prediction tools guide the design.
  • Diagnostics and virology: many viruses carry RNA genomes whose folded regions are drug and test targets.
  • Synthetic biology: engineers design RNA "switches" that fold one way or another to turn genes on and off.
  • Algorithms everywhere: Nussinov's table is a cousin of the dynamic programming behind sequence alignment, subset sum, and countless optimization tasks — the same "build big answers from small ones" engine.

Learn why RNA folding is easy and you've met dynamic programming at its most elegant — a method that tames a super-exponential search with nothing more than a well-filled grid.

Conclusion

RNA folding is a beautiful counterexample. The molecule can twist into more shapes than you could ever count, and yet a single table — filled diagonal by diagonal — hands you the fold with the most base pairs in polynomial time. Ruth Nussinov saw, back in 1978, that the search space's overwhelming size was a mirage: its parts overlap, so you never have to face the whole.

So when a problem looks hopeless because the possibilities are endless, pause before declaring it hard. Sometimes, as with RNA, the right table makes the impossible merely O(n3)O(n^{3}) — and the cell in the top-right corner already knows the answer.

Share this article

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

Comments

Loading comments...

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