Maximum-Likelihood Phylogenetics

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 $n$ species is:

$$T(n) = (2n - 5)!! = 1 \cdot 3 \cdot 5 \cdots (2n-5)$$

For $n = 10$ that is already 2,027,025 trees; for $n = 50$ it exceeds $3 \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.

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.

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</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">{{label_log_lk}}</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">{{btn_find_best}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_intro}} */
* { 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; }

// Code not found

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).

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)$ time, where $k$ is the sequence length. Checking is polynomial.
• The tree space is combinatorial. The number of unrooted binary trees on $n$ taxa grows as $(2n-5)!!$, faster than exponential. For $n = 20$ there are over $2 \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.

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.

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.