Introduction

Every living thing carries its evolutionary history in its DNA. Sequences accumulate random mutations over millions of years, and the pattern of shared changes tells us who is related to whom. Molecular phylogenetics is the discipline that reads those patterns and draws the family tree.

The most principled way to do it is maximum-likelihood (ML) estimation, introduced for phylogenetics by Joseph Felsenstein in 1981. The idea is elegant: given a substitution model — a mathematical description of how DNA letters change over time — compute the probability that the observed sequences evolved on each candidate tree. The tree that makes the data most probable is the ML tree.

The trouble is that the number of distinct unrooted binary trees on nn species is:

T(n)=(2n−5)!!=1⋅3⋅5⋯(2n−5)T(n) = (2n - 5)!! = 1 \cdot 3 \cdot 5 \cdots (2n-5)

For n=10n = 10 that is already 2,027,025 trees; for n=50n = 50 it exceeds 3×10743 \times 10^{74}. Evaluating every topology is hopeless, so in practice the search is heuristic — and the optimization problem is known to be NP-hard.

Score the Trees

Below are four short DNA sequences from hypothetical species A, B, C, and D. For four species there are exactly three possible unrooted binary tree topologies. Select one, and the demo computes its log-likelihood under the Jukes-Cantor substitution model — the simplest model in which all substitutions happen at equal rates.

<!-- Phylogenetics demo: score three candidate topologies for 4 sequences -->
<p class="hint">Four DNA sequences from species A, B, C, D — each 10 bases long. For 4 species there are exactly 3 unrooted binary topologies. Select one to see its log-likelihood under the Jukes-Cantor model. Higher is better.</p>
<div class="seqs" id="seqs"></div>
<div class="tree-btns" id="tree-btns"></div>
<div class="tree-vis" id="tree-vis"></div>
<div class="score-row">
  <span class="score-label">Log-likelihood:</span>
  <span class="score-val" id="score-val">—</span>
</div>
<div class="status" id="status"></div>
<div class="btns">
  <button id="btn-best" type="button">Find best tree</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>

/* Layout for the phylogenetics demo */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.seqs { font-family: ui-monospace, monospace; font-size: .82rem; background: #f0f4f8;
        border: 1px solid #cdd9e3; border-radius: 8px; padding: .6rem .8rem; margin-bottom: .8rem; }
.seq-row { display: flex; gap: .6rem; align-items: center; line-height: 1.9; }
.seq-label { font-weight: 700; color: #1d3557; min-width: 1.4rem; }
.seq-base { display: inline-block; width: 1.2rem; text-align: center; border-radius: 3px; }
.base-A { background: #c8f7c5; color: #145214; }
.base-C { background: #c5e3f7; color: #0d3a5c; }
.base-G { background: #f7e8c5; color: #5c3a0d; }
.base-T { background: #f7c5c5; color: #5c0d0d; }
.tree-btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .7rem; }
.tree-btn { font: 600 13px system-ui; padding: .38rem .75rem; border: 1px solid #1d3557;
           background: #fff; color: #1d3557; border-radius: 8px; cursor: pointer; transition: all .15s; }
.tree-btn.active { background: #1d3557; color: #fff; }
.tree-vis { background: #f8fafc; border: 1px solid #cdd9e3; border-radius: 8px;
            margin-bottom: .7rem; display: flex; align-items: center; justify-content: center;
            min-height: 110px; padding: .5rem; }
.tree-vis svg { max-width: 340px; }
.score-row { display: flex; align-items: center; gap: .5rem; margin-bottom: .4rem; }
.score-label { font-size: .9rem; color: #555; }
.score-val { font: 700 1rem ui-monospace, monospace; color: #1d3557; }
.score-val.best { color: #0a7d33; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin-bottom: .5rem; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

/* Hardcoded sequences for taxa A, B, C, D (10 bases each) */
const TAXA = ['A', 'B', 'C', 'D'];
const SEQS = {
  A: 'ACGTATCGAT',
  B: 'ACGTATCGCT',
  C: 'TCGTATCGAC',
  D: 'TCGTATCGCC'
};
const SEQ_LEN = SEQS['A'].length;

/* The 3 unrooted binary topologies for 4 taxa, as sister-pair lists */
const TOPOLOGIES = [
  { id: 't1', label: 'Tree 1: (A,B)|(C,D)', pairs: [['A','B'],['C','D']] },
  { id: 't2', label: 'Tree 2: (A,C)|(B,D)', pairs: [['A','C'],['B','D']] },
  { id: 't3', label: 'Tree 3: (A,D)|(B,C)', pairs: [['A','D'],['B','C']] }
];

/* Jukes-Cantor log-likelihood for a pair of sequences at a fixed branch length */
function jcLogLik(seq1, seq2) {
  let logL = 0;
  for (let i = 0; i < SEQ_LEN; i++) {
    const same = seq1[i] === seq2[i];
    /* Fixed branch length t=0.2 substitutions per site */
    const t = 0.2;
    const p = same ? (0.25 + 0.75 * Math.exp(-4 * t / 3)) : (0.25 - 0.25 * Math.exp(-4 * t / 3));
    logL += Math.log(Math.max(p, 1e-15));
  }
  return logL;
}

/* Approximate tree log-likelihood: sum of pair log-likelihoods for sister pairs plus an internal-node term */
function treeLogLik(pairs) {
  let total = 0;
  for (const [a, b] of pairs) {
    total += jcLogLik(SEQS[a], SEQS[b]);
  }
  /* Add a small contribution for the internal branch connecting the two clades */
  for (let i = 0; i < pairs.length - 1; i++) {
    const repA = SEQS[pairs[i][0]];
    const repB = SEQS[pairs[i + 1][0]];
    total += jcLogLik(repA, repB) * 0.4;
  }
  return total;
}

/* SVG diagrams for each of the three topologies */
const TREE_SVGS = {
  t1: `<svg viewBox="0 0 340 110" xmlns="http://www.w3.org/2000/svg" fill="none" stroke="#1d3557" stroke-width="1.6">
    <line x1="170" y1="55" x2="100" y2="55"/>
    <line x1="100" y1="55" x2="50" y2="25"/>
    <line x1="100" y1="55" x2="50" y2="85"/>
    <line x1="170" y1="55" x2="240" y2="55"/>
    <line x1="240" y1="55" x2="290" y2="25"/>
    <line x1="240" y1="55" x2="290" y2="85"/>
    <text x="30" y="29" font-size="14" font-weight="700" fill="#1d3557" stroke="none">A</text>
    <text x="30" y="89" font-size="14" font-weight="700" fill="#1d3557" stroke="none">B</text>
    <text x="295" y="29" font-size="14" font-weight="700" fill="#1d3557" stroke="none">C</text>
    <text x="295" y="89" font-size="14" font-weight="700" fill="#1d3557" stroke="none">D</text>
  </svg>`,
  t2: `<svg viewBox="0 0 340 110" xmlns="http://www.w3.org/2000/svg" fill="none" stroke="#1d3557" stroke-width="1.6">
    <line x1="170" y1="55" x2="100" y2="55"/>
    <line x1="100" y1="55" x2="50" y2="25"/>
    <line x1="100" y1="55" x2="50" y2="85"/>
    <line x1="170" y1="55" x2="240" y2="55"/>
    <line x1="240" y1="55" x2="290" y2="25"/>
    <line x1="240" y1="55" x2="290" y2="85"/>
    <text x="30" y="29" font-size="14" font-weight="700" fill="#1d3557" stroke="none">A</text>
    <text x="30" y="89" font-size="14" font-weight="700" fill="#1d3557" stroke="none">C</text>
    <text x="295" y="29" font-size="14" font-weight="700" fill="#1d3557" stroke="none">B</text>
    <text x="295" y="89" font-size="14" font-weight="700" fill="#1d3557" stroke="none">D</text>
  </svg>`,
  t3: `<svg viewBox="0 0 340 110" xmlns="http://www.w3.org/2000/svg" fill="none" stroke="#1d3557" stroke-width="1.6">
    <line x1="170" y1="55" x2="100" y2="55"/>
    <line x1="100" y1="55" x2="50" y2="25"/>
    <line x1="100" y1="55" x2="50" y2="85"/>
    <line x1="170" y1="55" x2="240" y2="55"/>
    <line x1="240" y1="55" x2="290" y2="25"/>
    <line x1="240" y1="55" x2="290" y2="85"/>
    <text x="30" y="29" font-size="14" font-weight="700" fill="#1d3557" stroke="none">A</text>
    <text x="30" y="89" font-size="14" font-weight="700" fill="#1d3557" stroke="none">D</text>
    <text x="295" y="29" font-size="14" font-weight="700" fill="#1d3557" stroke="none">B</text>
    <text x="295" y="89" font-size="14" font-weight="700" fill="#1d3557" stroke="none">C</text>
  </svg>`
};

let selectedTopo = null;
let scores = {};

/* Render colorized sequences in the UI */
function renderSeqs() {
  const container = document.getElementById('seqs');
  container.innerHTML = '';
  for (const taxon of TAXA) {
    const row = document.createElement('div');
    row.className = 'seq-row';
    const lbl = document.createElement('span');
    lbl.className = 'seq-label';
    lbl.textContent = taxon + ':';
    row.appendChild(lbl);
    for (const base of SEQS[taxon]) {
      const span = document.createElement('span');
      span.className = `seq-base base-${base}`;
      span.textContent = base;
      row.appendChild(span);
    }
    container.appendChild(row);
  }
}

/* Pre-compute scores for all three topologies at startup */
function precomputeScores() {
  for (const topo of TOPOLOGIES) {
    scores[topo.id] = treeLogLik(topo.pairs);
  }
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t;
  s.className = 'status ' + cls;
}

function selectTopo(id) {
  selectedTopo = id;
  document.querySelectorAll('.tree-btn').forEach(b => {
    b.classList.toggle('active', b.dataset.id === id);
  });
  const topo = TOPOLOGIES.find(t => t.id === id);
  document.getElementById('tree-vis').innerHTML = TREE_SVGS[id];
  const sc = scores[id];
  const bestScore = Math.max(...Object.values(scores));
  const valEl = document.getElementById('score-val');
  valEl.textContent = sc.toFixed(3);
  valEl.className = 'score-val' + (sc === bestScore ? ' best' : '');
  if (sc === bestScore) {
    setStatus(i18nFmt('This is the maximum-likelihood tree: %label%', { label: topo.label }), 'ok');
  } else {
    const diff = sc - bestScore;
    setStatus(i18nFmt('Not the best — delta log-likelihood: %delta%', { delta: diff.toFixed(2) }), 'info');
  }
}

function findBest() {
  const bestId = TOPOLOGIES.reduce((b, t) => scores[t.id] > scores[b.id] ? t : b, TOPOLOGIES[0]).id;
  selectTopo(bestId);
}

function reset() {
  selectedTopo = null;
  document.querySelectorAll('.tree-btn').forEach(b => b.classList.remove('active'));
  document.getElementById('tree-vis').innerHTML = '';
  document.getElementById('score-val').textContent = '—';
  document.getElementById('score-val').className = 'score-val';
  setStatus('', '');
}

/* Render topology selector buttons */
function renderButtons() {
  const container = document.getElementById('tree-btns');
  container.innerHTML = '';
  for (const topo of TOPOLOGIES) {
    const btn = document.createElement('button');
    btn.className = 'tree-btn';
    btn.dataset.id = topo.id;
    btn.textContent = topo.label;
    btn.addEventListener('click', () => selectTopo(topo.id));
    container.appendChild(btn);
  }
}

document.getElementById('btn-best').addEventListener('click', findBest);
document.getElementById('btn-reset').addEventListener('click', reset);

renderSeqs();
precomputeScores();
renderButtons();
Result
Console

The topology with the highest log-likelihood is the maximum-likelihood tree. Notice how a single topology change can shift the score substantially — and that is with only four sequences. With dozens of species, the search must visit millions of topologies using heuristics like nearest-neighbor interchange (NNI) or subtree pruning and regrafting (SPR).

The Real Complexity

How hard is maximum-likelihood phylogenetics, really?

  • Evaluating one tree is efficient: Felsenstein's pruning algorithm computes the likelihood of a fixed topology in O(nk)O(nk) time, where kk is the sequence length. Checking is polynomial.
  • The tree space is combinatorial. The number of unrooted binary trees on nn taxa grows as (2n−5)!!(2n-5)!!, faster than exponential. For n=20n = 20 there are over 2×10202 \times 10^{20} topologies — far beyond exhaustive search.
  • It is NP-hard. Roch and Steel (2015) proved that finding the exact maximum-likelihood tree under the general Markov model is NP-hard. Earlier work by Chor and Tuller (2005) showed hardness under simpler models. This means that, unless P vs NP resolves in our favor, no polynomial-time exact algorithm exists.
  • The landscape is treacherous. The likelihood function over tree space is multimodal: local optima abound, and hill-climbing can get stuck far from the global maximum. This is why software like RAxML and IQ-TREE use sophisticated restart and perturbation strategies rather than simple gradient ascent.

The gap between "score this tree" (easy) and "find the best tree" (hard) mirrors the same asymmetry we see in sequence alignment and countless other bioinformatics problems.

Where It Matters

Maximum-likelihood trees are not an academic exercise — they are a core tool in modern science:

  • Pandemic surveillance: during COVID-19, tools like Nextstrain built real-time ML phylogenies from thousands of SARS-CoV-2 genomes to track variant spread and geographic origin.
  • Antimicrobial resistance: phylogenies reveal how resistance genes spread between bacterial strains and across hospitals, informing infection control.
  • Cancer evolution: tumor phylogenetics reconstructs the branching history of mutations within a patient's cancer, guiding therapy selection.
  • Conservation biology: accurate trees tell us which populations are most distinct and therefore most valuable to preserve.
  • Drug target discovery: understanding how a pathogen's proteins evolved helps identify conserved regions that are good targets for drugs or vaccines.

The heuristics that make ML phylogenetics tractable in practice — NNI moves, SPR rearrangements, bootstrap resampling — are themselves an engineering triumph born directly from the hardness of the underlying optimization problem.

Conclusion

Maximum-likelihood phylogenetics sits at the intersection of probability theory, evolutionary biology, and computational complexity. Felsenstein's 1981 algorithm made it possible to evaluate any tree efficiently. The catch is that the forest of candidate trees is combinatorially vast, and finding the best one is provably NP-hard.

In practice, this means the evolutionary history you read in a paper is not guaranteed to be the true maximum-likelihood tree — it is the best tree that heuristic search found before the computer ran out of time. That is a remarkable limitation hiding inside one of biology's most fundamental questions.

The next time you see a phylogenetic tree in a pandemic report or a conservation study, remember: behind that elegant branching diagram lies a search problem as hard as any in computer science, solved every day by good heuristics and a healthy dose of computational humility.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/molecular-phylogenetics-ml/Content licensed under CC BY-NC 4.0.