Scalable and statistically rigorous algorithms for phylogenetic network reconstruction in the genome era

Hybridization between species and admixture between populations can produce novel combinations of genetic variants and, in turn, phenotypes. Studying trait evolution in this context requires a phylogenetic network, rather than a tree. Yet, network reconstruction is regarded as one of the most difficult problems in phylogenetics, posing significant computational and statistical obstacles, even for simple networks in which all cycles are vertex disjoint, called level-1. Notably, widely used methods require subnetworks estimated for all subsets of four species, leading to an Omega(n^4) time cost. In this talk, I will present our recent work developing statistically rigorous algorithms that break the quartic time barrier. I will show how these advances have led to unprecedented speed and accuracy, describe their deployment in the Vertebrate Genome Project, and highlight ongoing challenges and opportunities for algorithm design.