← All research

Human phylogenetics at scale

A phylogeny is a hypothesis about who descends from whom. Build one from a few hundred sequences and you can check it by eye. Build one from a third of a million and almost nothing in the standard phylogenetics toolkit survives contact with the data.

The tree everyone was using had stopped keeping up

PhyloTree v17 was published in 2016. It described about 5,400 haplogroups and quietly became the thing that nearly every lab, consumer test, and forensic pipeline depended on. It was a genuinely good resource. The problem was that it stopped being rebuilt.

Meanwhile sequencing costs collapsed and the number of available mitogenomes grew by more than an order of magnitude. When a reference tree stops being re-estimated, new sequences get grafted onto an increasingly outdated scaffold. Errors do not announce themselves; they accumulate quietly, and every downstream result inherits them.

Mitotree is the replacement. It resolves 53,588 haplogroups from 331,221 complete mitochondrial genomes, which collapse to 177,196 unique haplotypes once identical sequences are merged. That is roughly ten times the resolution of the previous standard, and it was built from scratch rather than grafted onto what came before.

Why it had not been done

Two problems stood in the way, and they are different in kind.

The first is search. Finding a good tree means evaluating an astronomically large space of possible topologies, and the heuristics that do this well had never been benchmarked above roughly 50,000 sequences. Above that they either failed outright or returned error rates nobody would accept. Several groups had tried.

The solution was a recursive divide-and-conquer framework. It breaks the problem into tractable subproblems, runs weighted parsimony searches on each, and reassembles them, with the reassembly step designed so that decisions made locally do not lock in mistakes globally. It handles 175,000 haplotypes, which is 3.5× the largest dataset previously benchmarked in the literature.

The second problem is knowing whether the answer is right. A tree this size cannot be checked by inspection, and there is no independent ground truth for human matrilineal descent. So I generated simulated phylogenies where the true answer was known by construction and ran the entire pipeline over them, end to end, exactly as it runs on real data.

I also built a three-part node support metric, because “how confident are we in this branch” turns out to be three separate questions. A branch can be uncertain because there were not enough informative sites, because the search did not converge, or because the mutations genuinely conflict with each other. Collapsing those into one number hides the thing you most want to know, which is whether more data or more compute would help.

Everything upstream of the tree

Most of the work in a project like this is not phylogenetics. Before a single tree search runs, a third of a million samples have to be aligned, called, and filtered, and the filters matter enormously. Heteroplasmy, ambiguous base calls, reference bias, and post-mortem damage in ancient samples each produce characteristic artifacts that look exactly like real mutations and will happily anchor a spurious branch that then propagates through everything downstream.

Haplogroup L7: an eighth African lineage hiding in public data

Modern humans have been around for something like 300,000 to 500,000 years, but global mitochondrial diversity coalesces to a single African ancestor roughly 145,000 years ago, because the matrilineal haploid genome has a quarter the effective population size of the autosomes. Most of human prehistory therefore played out in Africa, and the deepest structure in the mitochondrial tree is African structure.

For nearly two decades that structure was described by seven basal haplogroups, L0 through L6. They formed the backbone of the tree. Working through sequences that were already published, alongside newly generated ones, we found an eighth.

L7 is roughly 100,000 years old and had been misclassified in the literature. Its sublineage L7a* is the oldest singleton branch known in the human mitochondrial tree at about 80,000 years, meaning a lineage that split that long ago and is represented today by a single sampled sequence.

L7 and its sister group L5 are both low-frequency relics centered on East Africa, but they sit in different populations. L7 turns up among the Sandawe, L5 among the Mbuti. Three small subclades of African foragers hint at where the combined L5’7 lineage originated, but most subclades divide into Afro-Asiatic and eastern Bantu groups, which reflects more recent admixture rather than ancient structure.

Dating the paternal tree

The same problem exists on the Y chromosome, with a complication. The Y-DNA phylogeny at FamilyTreeDNA now exceeds 90,000 whole-Y sequences, and the callable portion of the Y varies substantially between samples depending on coverage. A dating method that ignores this will systematically misdate branches that happen to be populated by lower-coverage samples.

I developed the age estimation method used across that tree. It accounts for variable coverage across the callable region and for uncertainty in the mutation rate rather than assuming either away, and it is the engine behind the public Y-DNA Discover tool and the relationship reports built on top of it.

Tree search as a methods problem in its own right

Working at this scale surfaced a general question. Tree searches often need to respect relationships that are already known, which means searching under topological constraints, and it was not clear how standard heuristics behave when parts of the topology are fixed in advance. That became a separate methods paper with Pablo Goloboff, who wrote TNT, the software the Mitotree searches run on.