ASTRAL-X: Scaling Coalescent-Based Species Tree Inference to 300,000 Taxa

Advances in genome sequencing have enabled phylogenomic studies involving tens or even hundreds of thousands of species. However, species tree inference has not kept pace with this growth because existing statistically consistent methods cannot scale to datasets of this scale. ASTRAL, the most widely used coalescent-based species tree estimator, remains limited by computational and memory bottlenecks that make ultra-large analyses impractical. Here we present ASTRAL-X, a complete algorithmic redesign of the ASTRAL framework that overcomes these computational limitations. By fundamentally redesigning the underlying data representations, algorithms, and computational framework, ASTRAL-X dramatically reduces running time while lowering memory requirements to nearly the size of the input-the asymptotically optimal bound-thereby enabling statistically consistent species tree inference at an unprecedented scale. ASTRAL-X preserves ASTRALs statistical guarantees and achieves accuracy comparable to state-of-the-art methods across simulated and empirical datasets while reconstructing species trees containing 200,000 and 300,000 taxa in 5 hours and 12 hours, respectively, using modest computational resources. Notably, ASTRAL-X reconstructed the evolutionary history of 9,524 angiosperm species in only 16 minutes. These results make highly accurate statistically consistent species tree inference practical at the scale demanded by emerging Tree of Life initiatives. ASTRAL-X is publicly available at https://github.com/aaniksahaa/ASTRAL-X-releases.