Mitotree: The Universal Human Mitochondrial Reference Phylogeny at 10x the Resolution

Mitochondrial DNA (mtDNA) is the oldest and most prevalent source of human molecular phylogenetic reconstruction. Everyone alive today traces their matrilines to one female African ancestor who lived some 145 thousand years ago. For decades, PhyloTree provided researchers with a moderately sized reference tree (v17: n=24,275 sequences, n=5,438 branches). However, hundreds of thousands of sequences are available today, and since PhyloTree's retirement in 2016, there is a need for an actively maintained phylogenetic reference system. In addition, no currently published method can wield such a large de novo reconstruction while dealing with the rampant homoplasy seen in mtDNA and adhering to the accuracy standards expected in this well-studied field. In this paper we introduce Mitotree, the largest human phylogeny ever described (n~330,000 complete sequences, n~54,000 branches), and a new recursive phylogenetic pipeline for estimating it. We incorporate ancient DNA, relaxed clock age estimates (TMRCAs), and public databases (e.g., GenBank, 1000 Genomes, HGDP, and SGDP). We report approximately 180 previously unknown branches older than 30,000 years. The median TMRCA of terminal haplogroups is 2,000 years more recent than PhyloTree. Our pipeline offers a novel divide-and-conquer approach that tackles huge heuristic searches within tractable runtimes, provides high accuracy, and reasonable confidence estimates. Our validation found a false negative rate of 3.5%, and a false positive rate of 1.0%. Among the most striking findings are an ~83 kya split of African L2e (the oldest in our dataset), the resolution of Ötzi's K1f into a clade with living descendants, new ethnic founder haplogroups (e.g., Jewish diaspora), and placement of historical figures such as Abraham Lincoln. To our knowledge, Mitotree is the largest de novo haplotype phylogeny built for humanity, and is a continually improved resource for academic, genealogical, and medical research.