CAMUS: scalable phylogenetic network estimation
TL;DR
CAMUS is a new scalable algorithm for estimating phylogenetic networks that can analyze datasets of up to 201 species in hours, overcoming the strict computational limits of previous methods.
Problem / question
Estimating phylogenetic networks to model complex evolutionary events like hybridization and horizontal gene transfer is computationally difficult, with leading methods like SNaQ and PhyloNet-MPL typically failing to complete on datasets larger than 15 to 26 species.
Methods
The researchers developed CAMUS (Constrained Algorithm Maximizing qUartetS), a dynamic programming method that adds reticulate edges to a rooted constraint tree (generated by ASTRAL) to maximize the number of satisfied unrooted quartet trees. They tested CAMUS against SNaQ and PhyloNet-MPL on simulated datasets ranging from 16 to 201 species (each with 1000 gene trees) under the Network Multi-Species Coalescent model, and on a real biological dataset of 48 bird species with roughly 14,000 gene trees.
Key findings
CAMUS successfully analyzed 201-species datasets in 2 to 3 hours, whereas SNaQ failed on 26 species, PhyloNet-MPL failed on 51 species, and PhyloNet-MPL with a fixed tree failed on 101 species within a 12-hour limit. CAMUS was more topologically accurate than SNaQ and PhyloNet-MPL with a fixed tree, though slightly less accurate than PhyloNet-MPL without a fixed tree. On the 48-species avian dataset, CAMUS completed in just over a minute and identified two potential historical hybridization events, while PhyloNet-MPL without a fixed tree timed out after 24 hours.
Why it matters
By scaling phylogenetic network estimation to hundreds of species, CAMUS allows researchers to accurately map complex evolutionary histories and reticulate events across large genomic datasets that were previously impossible to analyze due to computational bottlenecks.
Limitations
CAMUS is slightly less accurate than heuristic searches that allow the constraint tree to change, and its memory usage scales steeply with the number of species, requiring up to 156 GB of RAM to process 201 species.
Takeaway
CAMUS provides a highly scalable, polynomial-time approach to building level-1 phylogenetic networks, enabling the analysis of reticulate evolution in datasets with over 200 species in just a few hours.