BROOQS: Quartet-based Resolution of Level-1 Hybridization Cycles without Tests of Symmetry
Abstract
Modern phylogenomic analyses often seek to reconstruct both vertical and reticulate evolutionary histories. While the prevalence of non-vertical evolution is increasingly appreciated, inferring networks remains conceptually challenging and computationally demanding. Following the success of quartet-based methods for species tree inference despite gene tree discordance, several quartet-based network inference methods have been developed. Most of these quartet-based methods boil down to detecting asymmetry in minor quartet frequencies, often using statistical tests to control for noise. However, these approaches have not yet been amenable to dynamic programming algorithms used in species tree inference for search, nor have they allowed efficient calculation of statistics across all quartets without listing all quartets. Instead, existing methods either enumerate all quartets, losing some scalability, or subsample them, losing information. For search, an effective recently developed strategy for level-1 networks is to first build a multifurcating tree called a tree-of-blobs and then resolve each polytomy into a cycle. This two-step approach makes the problem easier both conceptually and computationally. However, resolving blobs still requires either subsampling quartets or sacrificing scalability. We introduce BROOQS, a quartet-based method for resolving trees of blobs into a level-1 phylogenetic network. BROOQS efficiently aggregates information from all quartets around a blob in quadratic time and builds a pairwise similarity matrix that we prove encodes the cyclic ordering around the blob without relying on individual quartet symmetry tests. To recover the order from the matrix, we use two approaches. BROOQS-PQtree uses an existing combinatorial method, which allows us to prove statistical consistency under the network multi-species coalescent (NMSC) model for blobs of size 5 to 15. BROOQS-Spectral uses a spectral algorithm, which we conjecture (but have not proved) is consistent in similar conditions based on our simulations, and shows better robustness to noise than BROOQS-PQtree. Across simulated and empirical datasets, BROOQS-Spectral consistently improves accuracy and scalability compared to existing methods and extends to thousands of taxa.
Related
- Cross hybridization inference for phylogenetic resolution-fluorescence in situ hybridization enables microbiome imaging with strain level taxonomic resolution
- Comparison of nasal symmetry in children with unilateral oral clefts treated with/without nasoalveolar molding - a retrospective study with a mean age of 5 years
- BME-like Quartet Weights for Phylogenetic Trees
- QUANTA: A quantum annealing framework for species tree estimation using weighted quartet amalgamation
- Caspase-Like Proteases as Contributors in the Functioning of Reproductive Barriers During Distant Hybridization in Solanaceae
BibTeX
@misc{arasti2026brooqs,
title = {{BROOQS: Quartet-based Resolution of Level-1 Hybridization Cycles without Tests of Symmetry}},
author = {Shayesteh Arasti and Siavash Mirarab},
howpublished = {bioRxiv},
year = {2026},
month = aug,
doi = {10.64898/2026.08.31.748319},
url = {https://doi.org/10.64898/2026.08.31.748319},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - BROOQS: Quartet-based Resolution of Level-1 Hybridization Cycles without Tests of Symmetry
AU - Shayesteh Arasti
AU - Siavash Mirarab
PY - 2026
DA - 2026/08/31
PB - bioRxiv
DO - 10.64898/2026.08.31.748319
UR - https://doi.org/10.64898/2026.08.31.748319
AB - Modern phylogenomic analyses often seek to reconstruct both vertical and reticulate evolutionary histories. While the prevalence of non-vertical evolution is increasingly appreciated, inferring networks remains conceptually challenging and computationally demanding. Following the success of quartet-based methods for species tree inference despite gene tree discordance, several quartet-based network inference methods have been developed. Most of these quartet-based methods boil down to detecting asymmetry in minor quartet frequencies, often using statistical tests to control for noise. However, these approaches have not yet been amenable to dynamic programming algorithms used in species tree inference for search, nor have they allowed efficient calculation of statistics across all quartets without listing all quartets. Instead, existing methods either enumerate all quartets, losing some scalability, or subsample them, losing information. For search, an effective recently developed strategy for level-1 networks is to first build a multifurcating tree called a tree-of-blobs and then resolve each polytomy into a cycle. This two-step approach makes the problem easier both conceptually and computationally. However, resolving blobs still requires either subsampling quartets or sacrificing scalability. We introduce BROOQS, a quartet-based method for resolving trees of blobs into a level-1 phylogenetic network. BROOQS efficiently aggregates information from all quartets around a blob in quadratic time and builds a pairwise similarity matrix that we prove encodes the cyclic ordering around the blob without relying on individual quartet symmetry tests. To recover the order from the matrix, we use two approaches. BROOQS-PQtree uses an existing combinatorial method, which allows us to prove statistical consistency under the network multi-species coalescent (NMSC) model for blobs of size 5 to 15. BROOQS-Spectral uses a spectral algorithm, which we conjecture (but have not proved) is consistent in similar conditions based on our simulations, and shows better robustness to noise than BROOQS-PQtree. Across simulated and empirical datasets, BROOQS-Spectral consistently improves accuracy and scalability compared to existing methods and extends to thousands of taxa.
SN - 2692-8205
ER -