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

Modern phylogenomic studies aim to uncover both vertical and reticulate evolutionary histories. Though non-vertical evolution is becoming more recognized, inferring networks is both conceptually complex and computationally intensive. Building upon the success of quartet-based methods for managing gene tree discordance, numerous quartet-based network inference techniques have emerged.

A significant realization in these approaches is that level-1 networks can be generated by initially constructing a multifurcating tree known as the tree-of-blobs, followed by resolving each polytomy into a cycle. This multi-step process simplifies both the conceptual understanding and computational aspects of the task. However, many quartet-based techniques commonly depend on unreliable statistical tests of asymmetry in quartet frequencies.

Additionally, they either examine every quartet, which hampers scalability, or sample them, which results in information loss. We present BROOQS, a quartet-based technique designed to transform tree-of-blobs into a level-1 phylogenetic network. BROOQS effectively consolidates data from all quartets surrounding a blob without enumerating them, constructs a similarity matrix between pairs, and employs resilient spectral ordering algorithms to deduce the cyclic sequence without depending on individual quartet symmetry tests.

We provide a theoretical proof that our spectral approach is consistent under the network multi-species coalescent (NMSC) model. Empirical and simulated datasets demonstrate that BROOQS consistently enhances accuracy and scalability compared to previous methods, and it has been successfully applied to networks containing thousands of taxa.