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.