Scaling coalescent-based species tree inference to 100,000 taxa with STELAR-X

Abstract

Summary methods reconstruct species trees from collections of gene trees while accounting for gene tree discordance and provide a statistically consistent framework for phylogenomic inference under the multispecies coalescent model. While existing triplet- and quartet-based approaches such as ASTRAL and STELAR have provable statistical consistency, their running time and memory usage restrict their applicability to ultra-large datasets. We introduce STELAR-X, a statistically consistent and highly scalable triplet-based phylogenetic inference algorithm that achieves an asymptotically optimal memory complexity of $O(nk)$ for \textit{n} species and \textit{k} gene trees, essentially matching the input size and allowing analyses to remain feasible as long as the input trees fit in memory, while also substantially reducing running time. STELAR-X achieves this through a compact integer tuple-based encoding of tree bipartitions, efficient precomputation of bipartition weights, and GPU parallelism. These innovations substantially reduce computational overhead in the underlying dynamic programming framework. Experiments demonstrate that STELAR-X achieves unprecedented scalability. On simulated datasets with 10,000 taxa and 1,000 gene trees, STELAR-X runs 3,576$\times$ faster than ASTRAL-MP (the most scalable variant of ASTRAL) while using 13.9$\times$ less CPU memory. STELAR-X analyzed a dataset of 100,000 taxa and 1,000 genes in 34.37 minutes using 58.40 GB RAM, and a 100,000-gene dataset with 1000 taxa in just 3.32 minutes using 74.10 GB RAM, scales that were previously intractable for statistically consistent summary methods. Moreover, applying STELAR-X to two large-scale avian datasets produced trees highly consistent with established bird phylogenies, demonstrating its robustness on biological data.