Scaling coalescent-based species tree inference to 100,000 taxa with STELAR-X
Genome Research · 01.10.2026 · gr.282257.126
DOI: 10.1101/gr.282257.126 ↗Kurz gefasst
Fachartikel in der Zeitschrift Genome Research, online erschienen am 01.10.2026. Verfasst von Anik Saha und 1 weiteren Autor:innen. Beteiligte Einrichtung: Bangladesh University of Engineering and Technology. Die Arbeit wurde bisher 2-mal zitiert (Crossref).
Abstract (Originalsprache)
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.
Autor:innen und Institutionen
- Bangladesh University of Engineering and Technology.
- Bangladesh University of Engineering and Technology shams_bayzid@cse.buet.ac.bd.
Zitieren
APA
Saha, A., & Bayzid, M. S. (2026). Scaling coalescent-based species tree inference to 100,000 taxa with STELAR-X. Genome Research, gr.282257.126. https://doi.org/10.1101/gr.282257.126
Vancouver
Saha A, Bayzid MS. Scaling coalescent-based species tree inference to 100,000 taxa with STELAR-X. Genome Research. 2026:gr.282257.126. doi:10.1101/gr.282257.126
BibTeX
@article{Saha2026,
author = {Saha, Anik and Bayzid, Md Shamsuzzoha},
title = {Scaling coalescent-based species tree inference to 100,000 taxa with STELAR-X},
journal = {Genome Research},
year = {2026},
pages = {gr.282257.126},
doi = {10.1101/gr.282257.126}
}
EUVIMED