Quartet-based species tree methods enable fast and consistent tree of blobs reconstruction under the network multispecies coalescent
Preprint
Abstract
Hybridization between species is an important force in evolution, commonly modeled by the network multispecies coalescent. Reconstructing evolutionary histories under this model is computationally challenging, even for level-1 networks where hybridization events are isolated. Divide-and-conquer is a promising path forward, but current methods with statistical guarantees rely on an estimated tree of blobs (TOB) for the network, which compresses the non-tree-like parts into single vertices. TOB reconstruction is itself challenging, with the only available method TINNiK having time complexity O ( n 5 + n 4 k ) for k genes and n species. Here, we present a new framework for scalable TOB reconstruction with statistical guarantees. Our approach operates by (1) seeking a refinement of the TOB and then (2) contracting edges in it. For step (1), we show that any optimal solution to Weighted Quartet Consensus is a TOB refinement almost surely, as the number of genes goes to infinity, motivating the use of methods, such as ASTRAL or TREE-QMC. For step (2), we show that applying the same hypothesis tests as TINNiK to just O ( n ) four-taxon subsets around each edge is sufficient for statistical consistency when the underlying network is level-1. Leveraging TREE-QMC for the first step gives our method time complexity O ( n 3 k ) and its name: TOB-QMC. On simulated data, TOB-QMC typically matches or exceeds TINNiK in accuracy while being more scalable. TOB-QMC also enables fast exploration of non-tree-like evolution, as demonstrated through re-analysis of three phylogenomic data sets. Lastly, our study clarifies the theoretical utility of quartet-based species tree methods in the context of hybridization, which is critical given the recent result that ASTRAL can be misleading.Keywords
Funding Information
- State of Maryland
This publication has 42 references indexed in Scilit:
- TINNiK: inference of the tree of blobs of a species network under the coalescent modelAlgorithms for Molecular Biology, 2024
- Anomalous networks under the multispecies coalescent: theory and prevalenceJournal of Mathematical Biology, 2024
- PhyloCoalSimulations: A Simulator for Network Multispecies Coalescent Models, Including a New Extension for the Inheritance of Gene FlowSystematic Biology, 2023
- Improving quartet graph construction for scalable and accurate species tree estimation from gene treesGenome Research, 2023
- On the Weighted Quartet Consensus problemTheoretical Computer Science, 2019
- Identifying Species Network Features from Gene Tree Quartets Under the Coalescent ModelBulletin of Mathematical Biology, 2018
- Computational Phylogenetics2017
- Maximum likelihood inference of reticulate evolutionary historiesProceedings of the National Academy of Sciences, 2014
- ASTRAL: genome-scale coalescent-based species tree estimationBioinformatics, 2014
- A Decomposition Theory for Phylogenetic Networks and Incompatible CharactersJournal of Computational Biology, 2007