Introduction

Every species alive today shares ancestors with every other — somewhere back in time, your family tree meets the oak's and the mushroom's. A phylogenetic tree is biology's best guess at the shape of those connections: a branching diagram where each fork is a common ancestor and each tip is a species we can measure.

Given DNA, proteins, or anatomical traits, we can score how different any two species are. The dream is simple: feed in the differences and read out the one tree that best explains them. But "best" hides a trap. The number of possible trees explodes faster than almost anything in nature — and picking the winner turns out to be one of the genuinely hard problems in computer science.

So biologists rarely find the perfect tree. Instead they use fast, clever heuristics that build a very good tree without ever checking them all. This article shows one of the most famous in action.

Build a Tree

Here is a small table of distances between five species — bigger numbers mean more evolutionary change between them. From this matrix alone we want to recover the tree.

<p class="hint">Each cell is the evolutionary distance between two species — larger means more change. From this table alone, neighbor-joining rebuilds the tree by repeatedly merging the closest pair into a new ancestor.</p>
<div class="grid">
  <div class="panel">
    <h4>Distance matrix</h4>
    <div id="matrix"></div>
  </div>
  <div class="panel">
    <h4>Tree being built</h4>
    <pre id="tree" class="tree"></pre>
  </div>
</div>
<div class="status" id="status">Press Step to merge the closest pair.</div>
<div class="btns">
  <button id="step" type="button">Step</button>
  <button id="run" type="button">Run all</button>
  <button id="reset" type="button" class="ghost">Reset</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; }
.grid { display: flex; gap: 1rem; flex-wrap: wrap; }
.panel { flex: 1 1 240px; }
h4 { margin: 0 0 .4rem; font-size: .85rem; color: #1d3557; text-transform: uppercase; letter-spacing: .04em; }
table { border-collapse: collapse; font: 600 13px ui-monospace, monospace; }
th, td { border: 1px solid #cdd9e3; padding: .3rem .45rem; text-align: center; min-width: 34px; }
th { background: #e8eef3; color: #1d3557; }
td.pair { background: #ffe7c2; }
td.lo { color: #0a7d33; font-weight: 700; }
.tree { background: #f4f7fa; border: 1px solid #cdd9e3; border-radius: 8px;
        padding: .7rem; font: 600 13px ui-monospace, monospace; color: #1d3557;
        white-space: pre; overflow:auto; min-height: 120px; margin: 0; }
.status { font-size: 1rem; font-weight: 600; margin: .7rem 0 .4rem; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
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; }
button:disabled { opacity: .45; cursor: default; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Neighbor-joining (Saitou & Nei, 1987). Given a distance matrix between taxa,
// each step: compute the Q-matrix, pick the pair (i,j) minimizing Q, join them
// into a new node, and replace the two rows/cols by distances to the new node.
// It never enumerates whole trees — finding the OPTIMAL tree (max parsimony /
// likelihood) is NP-hard, so this fast heuristic is what biology actually uses.
const START = () => ({
  names: ['A','B','C','D','E'],
  // symmetric distance matrix (additive-ish, recovers a clean tree)
  D: [
    [0, 5, 9, 9, 8],
    [5, 0, 10,10, 9],
    [9,10, 0, 8, 7],
    [9,10, 8, 0, 3],
    [8, 9, 7, 3, 0],
  ],
});

let names, D, newick;

function reset(){
  const s = START();
  names = s.names.slice();
  D = s.D.map(r => r.slice());
  newick = names.slice();          // each leaf starts as its own subtree label
  setStatus('Press Step to merge the closest pair.','');
  render(null);
  document.getElementById('step').disabled = false;
  document.getElementById('run').disabled = false;
}

// Q-matrix: Q(i,j) = (n-2)*D(i,j) - sum(D row i) - sum(D row j).
function qMatrix(){
  const n = D.length;
  const rowSum = D.map(r => r.reduce((a,b)=>a+b,0));
  const Q = D.map(r => r.map(()=>0));
  let best = Infinity, bi=-1, bj=-1;
  for(let i=0;i<n;i++) for(let j=0;j<n;j++) if(i!==j){
    Q[i][j] = (n-2)*D[i][j] - rowSum[i] - rowSum[j];
    if(Q[i][j] < best){ best = Q[i][j]; bi=i; bj=j; }
  }
  return { Q, bi, bj };
}

function step(){
  const n = D.length;
  if(n <= 2){
    if(n === 2){
      newick = ['(' + newick[0] + ',' + newick[1] + ')'];
      render(null);
    }
    setStatus('Done — a single tree remains.','ok');
    document.getElementById('step').disabled = true;
    document.getElementById('run').disabled = true;
    return false;
  }
  const { bi, bj } = qMatrix();
  const a = Math.min(bi,bj), b = Math.max(bi,bj);
  const merged = '(' + newick[a] + ',' + newick[b] + ')';
  // distance from every other taxon k to the new node u:
  // D(u,k) = (D(a,k) + D(b,k) - D(a,b)) / 2
  const dab = D[a][b];
  const keep = [];
  for(let k=0;k<n;k++) if(k!==a && k!==b) keep.push(k);
  const m = keep.length + 1;       // new size
  const nD = Array.from({length:m},()=>Array(m).fill(0));
  for(let x=0;x<keep.length;x++) for(let y=0;y<keep.length;y++)
    nD[x][y] = D[keep[x]][keep[y]];
  for(let x=0;x<keep.length;x++){
    const dk = (D[a][keep[x]] + D[b][keep[x]] - dab) / 2;
    nD[x][keep.length] = dk; nD[keep.length][x] = dk;
  }
  const nNames = keep.map(k=>names[k]); nNames.push('U');
  const nNewick = keep.map(k=>newick[k]); nNewick.push(merged);
  const joinedLabels = names[a] + ' + ' + names[b];
  names = nNames; D = nD; newick = nNewick;
  render(null);
  setStatus(fmt('Joined %joinedLabels% into a new ancestor.', { joinedLabels: joinedLabels }),'ok');
  return true;
}

function runAll(){ while(step()){} }

function render(highlight){
  // matrix
  const { bi, bj } = D.length > 2 ? qMatrix() : { bi:-1, bj:-1 };
  const n = D.length;
  let h = '<table><tr><th></th>';
  for(let j=0;j<n;j++) h += '<th>'+names[j]+'</th>';
  h += '</tr>';
  for(let i=0;i<n;i++){
    h += '<tr><th>'+names[i]+'</th>';
    for(let j=0;j<n;j++){
      const isPair = (i===bi&&j===bj)||(i===bj&&j===bi);
      h += '<td class="'+(isPair?'pair lo':'')+'">'+(i===j?'·':D[i][j])+'</td>';
    }
    h += '</tr>';
  }
  h += '</table>';
  document.getElementById('matrix').innerHTML = h;
  // tree
  document.getElementById('tree').textContent =
    newick.length === 1 ? newick[0] : newick.join('\n');
}

function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }
document.getElementById('step').addEventListener('click',step);
document.getElementById('run').addEventListener('click',runAll);
document.getElementById('reset').addEventListener('click',reset);
reset();
Result
Console

Press Step to watch neighbor-joining work: at each round it picks the two taxa that are closest once the rest of the table is taken into account, fuses them into a new ancestor node, and shrinks the matrix by one. Repeat until a single tree remains. Notice that it never compares whole trees against each other — it makes a sequence of cheap local choices, which is exactly why it is fast where the exact search is hopeless.

The Real Complexity

How hard is it to find the best tree? Brutally hard — and we can be precise about it.

  • The search space explodes. For just 10 species there are over 34 million possible rooted trees; for 20 there are more than 8 × 102110^{21}. The count grows super-exponentially, so checking every tree is out of the question.
  • Maximum parsimony is NP-hard. Choosing the tree that needs the fewest evolutionary changes is equivalent to the Steiner tree problem in a discrete space, shown NP-hard by Foulds and Graham (1982).
  • Maximum likelihood is NP-hard too. Picking the tree that makes the observed data most probable was proven hard by Sebastien Roch (2006) — even the simplest models don't get a free pass.
  • So the exact problem is intractable. There is no known efficient algorithm, and a fast one would imply P = NP.

That is why real phylogenetics runs on heuristics: distance methods like neighbor-joining, plus hill-climbing searches that nudge a tree toward better scores. They come with no guarantee of optimality, but they finish — and most of the time the tree they find is excellent.

Where It Matters

Reconstructing a tree from data is one of biology's workhorses, and the same idea reaches far beyond it:

  • Tracking outbreaks: sequencing a virus and placing it on a tree reveals who infected whom and how the pathogen is mutating — central to responses to flu, HIV and COVID-19.
  • Conservation: trees show which species are evolutionarily unique, helping prioritize what to protect.
  • Drug and enzyme discovery: relating proteins by ancestry points to functions and useful variants.
  • Forensics and ancestry: the same math relates samples, individuals and populations.
  • Beyond biology: historical linguists build family trees of languages, and editors reconstruct how copied manuscripts descend from lost originals — using the very same algorithms.

Under all of these sits the same intractable core. Like the traveling salesman, it is a problem we cannot solve perfectly at scale, so we lean on heuristics that are fast and good enough.

Conclusion

The tree of life is not just a poetic image — it is a concrete object we try to compute, and computing the best one is NP-hard. The number of possible trees outruns any brute-force search, and both of the natural scoring rules, parsimony and likelihood, are provably intractable.

And yet biology does not stall. Heuristics like neighbor-joining build a tree in a sequence of fast, local choices, giving up the promise of perfection for an answer that arrives in time to matter — during an outbreak, in a lab, on a deadline. It is a familiar bargain across computer science: when the exact problem is as hard as P vs NP, being approximately right, quickly, is what keeps the science moving.

Share this article

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

Comments

Loading comments...

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