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

Authors

Anik Saha, Md Shamsuzzoha Bayzid

Published in

Genome research. Oct 01, 2026. Epub Oct 01, 2026.

Abstract

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 n species and 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× faster than ASTRAL-MP (the most scalable variant of ASTRAL) while using 13.9× 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.

PMID:
42823195
Bibliographic data and abstract were imported from PubMed on 02 Oct 2026.

Read full publication at:
Please sign in to see all details.

Stats

1-terrible, 9-excellent. How would you rate this publication? Sign in in to submit your rating.

Post a comment

You need to be signed in to post comments. You can sign in here.

Comments

There are no comments yet.