BROOQS: Spectral Methods Resolve Level-1 Hybridization Cycles without Tests of Symmetry

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, builds a pairwise similarity matrix, and uses robust spectral ordering algorithms to recover the cyclic ordering without relying on individual quartet symmetry tests. We prove theoretically that our spectral method is consistent under the network multi-species coalescent (NMSC) model. Across simulated and empirical datasets, BROOQS consistently improves accuracy and scalability compared to existing methods and extends to thousands of taxa.