Phylogenetic Trees

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.

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">{{hint}}</p>
<div class="grid">
  <div class="panel">
    <h4>{{h_matrix}}</h4>
    <div id="matrix"></div>
  </div>
  <div class="panel">
    <h4>{{h_tree}}</h4>
    <pre id="tree" class="tree"></pre>
  </div>
</div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="run" type="button">{{btn_run}}</button>
  <button id="reset" type="button" class="ghost">{{btn_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; }

// Code not found

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.

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 × $10^{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.

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.

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.