{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"institution":[{"name":"bioRxiv"}],"indexed":{"date-parts":[[2026,10,29]],"date-time":"2026-10-29T18:37:55Z","timestamp":1793299075162,"version":"4.5.0"},"posted":{"date-parts":[[2026,9,4]]},"group-title":"Bioinformatics","reference-count":82,"publisher":"openRxiv","license":[{"start":{"date-parts":[[2026,9,4]],"date-time":"2026-09-04T00:00:00Z","timestamp":1788480000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"funder":[{"award":["1R35GM142725"],"award-info":[{"award-number":["1R35GM142725"]}],"id":[{"id":"https:\/\/ror.org\/001d55x84","id-type":"ROR","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"accepted":{"date-parts":[[2026,10,26]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                <jats:p>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.<\/jats:p>","DOI":"10.64898\/2026.08.31.748319","type":"posted-content","created":{"date-parts":[[2026,9,4]],"date-time":"2026-09-04T21:55:15Z","timestamp":1788558915000},"source":"Crossref","is-referenced-by-count":1,"title":["BROOQS: Quartet-based Resolution of Level-1 Hybridization Cycles without Tests of Symmetry"],"prefix":"10.64898","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-1607-5300","authenticated-orcid":false,"given":"Shayesteh","family":"Arasti","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, UC San Diego, 9500 Gilman Dr., 92093, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5410-1518","authenticated-orcid":false,"given":"Siavash","family":"Mirarab","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, UC San Diego, 9500 Gilman Dr., 92093, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"54368","reference":[{"key":"2026102911301196000_2026.08.31.748319v3.1","doi-asserted-by":"crossref","first-page":"1076","DOI":"10.1093\/sysbio\/syy034","article-title":"Assessing the impacts of positive selection on coalescent-based species tree estimation and species delimitation","volume":"67","year":"2018","journal-title":"Systematic Biology"},{"key":"2026102911301196000_2026.08.31.748319v3.2","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1007\/s11538-024-01339-4","article-title":"Identifiability of level-1 species networks from gene tree quartets","volume":"86","year":"2024","journal-title":"Bull Math Biol"},{"key":"2026102911301196000_2026.08.31.748319v3.3","doi-asserted-by":"publisher","DOI":"10.1007\/s00285-022-01838-9"},{"key":"2026102911301196000_2026.08.31.748319v3.4","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1186\/s13015-024-00266-2","article-title":"Tinnik: inference of the tree of blobs of a species network under the coalescent model","volume":"19","year":"2024","journal-title":"Algorithms for Molecular Biology"},{"key":"2026102911301196000_2026.08.31.748319v3.5","doi-asserted-by":"publisher","DOI":"10.1186\/s13015-019-0159-2"},{"key":"2026102911301196000_2026.08.31.748319v3.6","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1186\/s13015-025-00274-w","article-title":"Nanuq+: A divide-and-conquer approach to network estimation","volume":"20","year":"2025","journal-title":"Algorithms for Molecular Biology"},{"key":"2026102911301196000_2026.08.31.748319v3.7","doi-asserted-by":"publisher","DOI":"10.1007\/s00285-010-0355-7"},{"key":"2026102911301196000_2026.08.31.748319v3.8","doi-asserted-by":"publisher","DOI":"10.2307\/2405610"},{"key":"2026102911301196000_2026.08.31.748319v3.9","doi-asserted-by":"crossref","first-page":"1223","DOI":"10.1137\/21M139356X","article-title":"An optimal algorithm for strict circular seriation","volume":"3","year":"2021","journal-title":"SIAM Journal on Mathematics of Data Science"},{"key":"2026102911301196000_2026.08.31.748319v3.10","doi-asserted-by":"publisher","DOI":"10.1007\/s11538-018-0485-4"},{"key":"2026102911301196000_2026.08.31.748319v3.11","doi-asserted-by":"publisher","DOI":"10.1093\/aob\/mcr208"},{"key":"2026102911301196000_2026.08.31.748319v3.12","doi-asserted-by":"publisher","DOI":"10.1016\/j.ympev.2024.108197"},{"key":"2026102911301196000_2026.08.31.748319v3.13","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80045-1"},{"key":"2026102911301196000_2026.08.31.748319v3.14","unstructured":"Bryant, D. , J. Tsang , P. Kearney , and M. Li . 2000. Computing the quartet distance between evolutionary trees. Pages 285\u2013286 in Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms SODA \u201800 Society for Industrial and Applied Mathematics, USA."},{"key":"2026102911301196000_2026.08.31.748319v3.15","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2008.70"},{"key":"2026102911301196000_2026.08.31.748319v3.16","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.97.8.4086"},{"key":"2026102911301196000_2026.08.31.748319v3.17","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2008.2002305"},{"key":"2026102911301196000_2026.08.31.748319v3.18","doi-asserted-by":"crossref","unstructured":"Dai, J. , Y. Han , and E. K. Molloy . 2026. Quartet-based species tree methods enable fast and consistent tree of blobs reconstruction under the network multispecies coalescent. Genome Research Page gr.282203.126.","DOI":"10.1101\/gr.282203.126"},{"key":"2026102911301196000_2026.08.31.748319v3.19","doi-asserted-by":"crossref","unstructured":"Dai, J. and E. K. Molloy . 2026. Is Level-1 Blob Reconstruction Under the Network Multispecies Coalescent Easy? Pages 1:1\u20131:24 in 26th International Conference on Algorithms for Bioinformatics (WABI 2026) ( N. El-Mabrouk and F. Vandin , eds.) vol. 390 of Leibniz International Proceedings in Informatics (LIPIcs) Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany.","DOI":"10.64898\/2026.06.06.730607"},{"key":"2026102911301196000_2026.08.31.748319v3.20","doi-asserted-by":"publisher","DOI":"10.1093\/sysbio\/syy040"},{"key":"2026102911301196000_2026.08.31.748319v3.21","doi-asserted-by":"publisher","DOI":"10.1016\/S1055-7903(03)00067-8"},{"key":"2026102911301196000_2026.08.31.748319v3.22","doi-asserted-by":"publisher","DOI":"10.1093\/sysbio\/27.4.401"},{"key":"2026102911301196000_2026.08.31.748319v3.23","doi-asserted-by":"publisher","DOI":"10.1093\/molbev\/msp098"},{"key":"2026102911301196000_2026.08.31.748319v3.24","first-page":"1","article-title":"Spectral ranking using seriation","volume":"17","year":"2016","journal-title":"Journal of Machine Learning Research"},{"key":"2026102911301196000_2026.08.31.748319v3.25","doi-asserted-by":"publisher","DOI":"10.1093\/sysbio\/syad030"},{"key":"2026102911301196000_2026.08.31.748319v3.26","doi-asserted-by":"publisher","DOI":"10.1093\/sysbio\/syad056"},{"key":"2026102911301196000_2026.08.31.748319v3.27","doi-asserted-by":"crossref","unstructured":"Gatesy, J. and M. S. Springer . 2022. Phylogenomic coalescent analyses of avian retroelements infer zero-length branches at the base of neoaves, emergent support for controversial clades, and ancient introgressive hybridization in afroaves. Genes 13.","DOI":"10.3390\/genes13071167"},{"key":"2026102911301196000_2026.08.31.748319v3.28","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2006.0137"},{"key":"2026102911301196000_2026.08.31.748319v3.29","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1111\/jse.70034","article-title":"Integrative phylogenomics and morphology reveal the evolution and biogeography of encephalartos (zamiaceae)","volume":"64","year":"2026","journal-title":"Journal of Systematics and Evolution"},{"key":"2026102911301196000_2026.08.31.748319v3.30","doi-asserted-by":"crossref","first-page":"3945","DOI":"10.1534\/g3.118.200754","article-title":"Whole-genome analysis of introgression between the spotted owl and barred owl (strix occidentalis and strix varia, respectively; aves: Strigidae) in western north america","volume":"8","year":"2018","journal-title":"G3 Genes\u2014Genomes\u2014Genetics"},{"key":"2026102911301196000_2026.08.31.748319v3.31","doi-asserted-by":"crossref","first-page":"752","DOI":"10.1093\/sysbio\/syaf085","article-title":"Population size differences can lead to biases in phylogenetic inference and introgression detection in the presence of purifying selection","volume":"75","year":"2026","journal-title":"Systematic Biology"},{"key":"2026102911301196000_2026.08.31.748319v3.32","doi-asserted-by":"crossref","first-page":"881","DOI":"10.1093\/molbev\/msz232","article-title":"Asymmetric distribution of gene trees can arise under purifying selection if differences in population size exist","volume":"37","year":"2020","journal-title":"Molecular Biology and Evolution"},{"key":"2026102911301196000_2026.08.31.748319v3.33","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1186\/s12859-016-1277-1","article-title":"A scalability study of phylogenetic network inference methods using empirical datasets and simulations involving a single reticulation","volume":"17","year":"2016","journal-title":"BMC Bioinformatics"},{"key":"2026102911301196000_2026.08.31.748319v3.34","doi-asserted-by":"publisher","DOI":"10.1093\/molbev\/msaf067"},{"key":"2026102911301196000_2026.08.31.748319v3.35","doi-asserted-by":"publisher","DOI":"10.1007\/s11538-018-0450-2"},{"key":"2026102911301196000_2026.08.31.748319v3.36","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/BF02294859","article-title":"Graph-theoretic representations for proximity matrices through strongly-anti-robinson or circular strongly-anti-robinson matrices","volume":"63","year":"1998","journal-title":"Psychometrika"},{"key":"2026102911301196000_2026.08.31.748319v3.37","doi-asserted-by":"crossref","unstructured":"Huson, D. H. , R. Rupp , and C. Scornavacca . 2010. Phylogenetic Networks: Concepts, Algorithms and Applications. Cambridge University Press.","DOI":"10.1017\/CBO9780511974076"},{"key":"2026102911301196000_2026.08.31.748319v3.38","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1137\/20M1365715","article-title":"Spectral neighbor joining for reconstruction of latent tree models","volume":"3","year":"2021","journal-title":"SIAM Journal on Mathematics of Data Science"},{"key":"2026102911301196000_2026.08.31.748319v3.39","doi-asserted-by":"publisher","DOI":"10.1126\/science.1253451"},{"key":"2026102911301196000_2026.08.31.748319v3.40","doi-asserted-by":"publisher","DOI":"10.1080\/10635150490468648"},{"key":"2026102911301196000_2026.08.31.748319v3.41","doi-asserted-by":"crossref","first-page":"1687","DOI":"10.1111\/2041-210X.14116","article-title":"Siphynetwork: An r package for simulating phylogenetic networks","volume":"14","year":"2023","journal-title":"Methods in Ecology and Evolution"},{"key":"2026102911301196000_2026.08.31.748319v3.42","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1214\/14-AOS1275","article-title":"Graph connection Laplacian methods can be made robust to noise","volume":"44","year":"2016","journal-title":"The Annals of Statistics"},{"key":"2026102911301196000_2026.08.31.748319v3.43","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/30.1-2.81"},{"key":"2026102911301196000_2026.08.31.748319v3.44","doi-asserted-by":"crossref","unstructured":"Kolbow, N. , S. Kong , and C. Sol\u00eds-Lemus . 2026. A method for massively scalable inference of phylogenetic networks. bioRxiv .","DOI":"10.1101\/2025.05.05.652278"},{"key":"2026102911301196000_2026.08.31.748319v3.45","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.2410934122"},{"key":"2026102911301196000_2026.08.31.748319v3.46","doi-asserted-by":"crossref","first-page":"qac064","DOI":"10.1093\/nargab\/lqac064","article-title":"Pitfalls of the site-concordance factor (scf) as measure of phylogenetic branch support","volume":"4","year":"2022","journal-title":"NAR Genom Bioinform"},{"key":"2026102911301196000_2026.08.31.748319v3.47","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-019-1693-2"},{"key":"2026102911301196000_2026.08.31.748319v3.48","doi-asserted-by":"crossref","first-page":"1451","DOI":"10.1093\/zoolinnean\/zlac060","article-title":"Mitogenomes resolve the phylogeography and divergence times within the endemic new zealand callaeidae (aves: Passerida)","volume":"196","year":"2022","journal-title":"Zoological Journal of the Linnean Society"},{"key":"2026102911301196000_2026.08.31.748319v3.49","doi-asserted-by":"publisher","DOI":"10.1093\/gbe\/evz209"},{"key":"2026102911301196000_2026.08.31.748319v3.50","doi-asserted-by":"publisher","DOI":"10.7717\/peerj&mdash;cs.103"},{"key":"2026102911301196000_2026.08.31.748319v3.51","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-ecolsys-012121-095340"},{"key":"2026102911301196000_2026.08.31.748319v3.52","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btu462"},{"key":"2026102911301196000_2026.08.31.748319v3.53","doi-asserted-by":"crossref","first-page":"2150","DOI":"10.1214\/19-EJS1576","article-title":"Hypothesis testing near singularities and boundaries","volume":"13","year":"2019","journal-title":"Electron J Stat"},{"key":"2026102911301196000_2026.08.31.748319v3.54","doi-asserted-by":"crossref","first-page":"12709","DOI":"10.1038\/ncomms12709","article-title":"Tectonic collision and uplift of wallacea triggered the global songbird radiation","volume":"7","year":"2016","journal-title":"Nature Communications"},{"key":"2026102911301196000_2026.08.31.748319v3.55","doi-asserted-by":"crossref","unstructured":"Nakhleh, L. 2011. Evolutionary Phylogenetic Networks: Models and Issues Pages 125\u2013158. Springer US, Boston, MA.","DOI":"10.1007\/978-0-387-09760-2_7"},{"key":"2026102911301196000_2026.08.31.748319v3.56","doi-asserted-by":"publisher","DOI":"10.1093\/oxfordjournals.molbev.a026290"},{"key":"2026102911301196000_2026.08.31.748319v3.57","doi-asserted-by":"publisher","DOI":"10.1002\/bies.202000012"},{"key":"2026102911301196000_2026.08.31.748319v3.58","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1676\/21-00011","article-title":"An instance of hybridization with common grackle (quiscalus quiscula) and male parental care by great-tailed grackle (q. mexicanus)","volume":"133","year":"2021","journal-title":"The Wilson Journal of Ornithology"},{"key":"2026102911301196000_2026.08.31.748319v3.59","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0013124"},{"key":"2026102911301196000_2026.08.31.748319v3.60","unstructured":"Recanati, A. , T. Kerdreux , and A. d\u2019Aspremont . 2018. Reconstructing latent orderings by spectral clustering. CoRR abs\/1807.07122."},{"key":"2026102911301196000_2026.08.31.748319v3.61","unstructured":"Reshef, O. , O. Glassman , O. Zuk , Y. Aizenbud , B. Nadler , and A. Jaffe . 2026. Sdsr: A spectral divide-and-conquer approach for species tree reconstruction."},{"key":"2026102911301196000_2026.08.31.748319v3.62","doi-asserted-by":"publisher","DOI":"10.1093\/BIOINFORMATICS\/BTAA868"},{"key":"2026102911301196000_2026.08.31.748319v3.63","doi-asserted-by":"publisher","DOI":"10.1016\/0025-5564(81)90043-2"},{"key":"2026102911301196000_2026.08.31.748319v3.64","doi-asserted-by":"crossref","first-page":"783","DOI":"10.1186\/s12864-016-3098-z","article-title":"Anchoring quartet-based phylogenetic distances and applications to species tree reconstruction","volume":"17","year":"2016","journal-title":"BMC Genomics"},{"key":"2026102911301196000_2026.08.31.748319v3.65","doi-asserted-by":"publisher","DOI":"10.1600\/036364414X683921"},{"key":"2026102911301196000_2026.08.31.748319v3.66","doi-asserted-by":"publisher","DOI":"10.3732\/ajb.1400190"},{"key":"2026102911301196000_2026.08.31.748319v3.67","first-page":"1","article-title":"Inferring phylogenetic networks with maximum pseudolikelihood under incomplete lineage sorting","volume":"12","year":"2016","journal-title":"PLOS Genetics"},{"key":"2026102911301196000_2026.08.31.748319v3.68","doi-asserted-by":"publisher","DOI":"10.1093\/sysbio\/syw030"},{"key":"2026102911301196000_2026.08.31.748319v3.69","unstructured":"Stephan, L. and L. Massouli\u00e9 . 2019. Robustness of spectral methods for community detection. Pages 2831\u20132860 in Proceedings of the Thirty-Second Conference on Learning Theory ( A. Beygelzimer and D. Hsu , eds.) vol. 99 of Proceedings of Machine Learning Research PMLR."},{"key":"2026102911301196000_2026.08.31.748319v3.70","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-024-07323-1"},{"key":"2026102911301196000_2026.08.31.748319v3.71","doi-asserted-by":"publisher","DOI":"10.1111\/tpj.16142"},{"key":"2026102911301196000_2026.08.31.748319v3.72","doi-asserted-by":"publisher","DOI":"10.1111\/zsc.12213"},{"key":"2026102911301196000_2026.08.31.748319v3.73","unstructured":"von Luxburg, U. 2007. A tutorial on spectral clustering. CoRR abs\/0711.0189."},{"key":"2026102911301196000_2026.08.31.748319v3.74","doi-asserted-by":"publisher","DOI":"10.1093\/sysbio\/syy015"},{"key":"2026102911301196000_2026.08.31.748319v3.75","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1323926111"},{"key":"2026102911301196000_2026.08.31.748319v3.76","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btag245"},{"key":"2026102911301196000_2026.08.31.748319v3.77","doi-asserted-by":"publisher","DOI":"10.1093\/molbev\/msag117)"},{"key":"2026102911301196000_2026.08.31.748319v3.78","doi-asserted-by":"publisher","DOI":"10.1111\/j.1558-5646.2011.01476.x"},{"key":"2026102911301196000_2026.08.31.748319v3.79","first-page":"1","article-title":"The probability of a gene tree topology within a phylogenetic network with applications to hybridization detection","volume":"8","year":"2012","journal-title":"PLOS Genetics"},{"key":"2026102911301196000_2026.08.31.748319v3.80","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2164-16-S10-S10"},{"key":"2026102911301196000_2026.08.31.748319v3.81","doi-asserted-by":"crossref","first-page":"msaf172.","DOI":"10.1093\/molbev\/msaf172","article-title":"ASTER: A Package for Large-Scale Phylogenomic Reconstructions","volume":"42","year":"2025","journal-title":"Molecular Biology and Evolution"},{"key":"2026102911301196000_2026.08.31.748319v3.82","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bty295"}],"container-title":[],"original-title":[],"link":[{"URL":"https:\/\/syndication.highwire.org\/content\/doi\/10.64898\/2026.08.31.748319","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,29]],"date-time":"2026-10-29T18:30:24Z","timestamp":1793298624000},"score":1,"resource":{"primary":{"URL":"http:\/\/biorxiv.org\/lookup\/doi\/10.64898\/2026.08.31.748319"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,9,4]]},"references-count":82,"URL":"https:\/\/doi.org\/10.64898\/2026.08.31.748319","relation":{},"subject":[],"published":{"date-parts":[[2026,9,4]]},"subtype":"preprint"}}