{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T04:06:56Z","timestamp":1783483616415,"version":"3.55.0"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T00:00:00Z","timestamp":1710288000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T00:00:00Z","timestamp":1710288000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"National Science Foundation, United States","award":["IIS 1845967"],"award-info":[{"award-number":["IIS 1845967"]}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["1R35GM142725"],"award-info":[{"award-number":["1R35GM142725"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Gene trees can be different from the species tree due to biological processes and inference errors. One way to obtain a species tree is to find one that maximizes some measure of similarity to a set of gene trees. The number of shared quartets between a potential species tree and gene trees provides a statistically justifiable score; if maximized properly, it could result in a statistically consistent estimator of the species tree under several statistical models of discordance. However, finding the median quartet score tree, one that maximizes this score, is NP-Hard, motivating several existing heuristic algorithms. These heuristics do not follow the hill-climbing paradigm used extensively in phylogenetics. In this paper, we make theoretical contributions that enable an efficient hill-climbing approach. Specifically, we show that a subtree of size <jats:italic>m<\/jats:italic> can be placed optimally on a tree of size <jats:italic>n<\/jats:italic> in quasi-linear time with respect to <jats:italic>n<\/jats:italic> and (almost) independently of <jats:italic>m<\/jats:italic>. This result enables us to perform subtree prune and regraft (SPR) rearrangements as part of a hill-climbing search. We show that this approach can slightly improve upon the results of widely-used methods such as ASTRAL in terms of the optimization score but not necessarily accuracy.<\/jats:p>","DOI":"10.1186\/s13015-024-00257-3","type":"journal-article","created":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T17:02:30Z","timestamp":1710349350000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Median quartet tree search algorithms using optimal subtree prune and regraft"],"prefix":"10.1186","volume":"19","author":[{"given":"Shayesteh","family":"Arasti","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Siavash","family":"Mirarab","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,3,13]]},"reference":[{"key":"257_CR1","doi-asserted-by":"publisher","unstructured":"Lafond M, Scornavacca C. On the Weighted Quartet Consensus problem. Theor Comput Sci 2019;769, 1\u201317 https:\/\/doi.org\/10.1016\/j.tcs.2018.10.005 . arXiv: 1610.00505","DOI":"10.1016\/j.tcs.2018.10.005"},{"key":"257_CR2","doi-asserted-by":"crossref","unstructured":"Mirarab S. Species tree estimation using ASTRAL: Practical considerations. In: Species tree inference: a guide to methods and applications. Princeton; Princeton University Press; 2023.","DOI":"10.2307\/j.ctv2wr4wdf.9"},{"issue":"2","key":"257_CR3","doi-asserted-by":"publisher","first-page":"193","DOI":"10.2307\/sysbio\/34.2.193","volume":"34","author":"GF Estabrook","year":"1985","unstructured":"Estabrook GF, McMorris FR, Meacham CA. Comparison of undirected phylogenetic trees based on subtrees of four evolutionary units. Syst Biol. 1985;34(2):193\u2013200. https:\/\/doi.org\/10.2307\/sysbio\/34.2.193.","journal-title":"Syst Biol"},{"issue":"1","key":"257_CR4","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/BF02618470","volume":"9","author":"M Steel","year":"1992","unstructured":"Steel M. The complexity of reconstructing trees from qualitative characters and subtrees. J Class. 1992;9(1):91\u2013116. https:\/\/doi.org\/10.1007\/BF02618470.","journal-title":"J Class"},{"issue":"1","key":"257_CR5","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1089\/cmb.2007.0103","volume":"15","author":"S Snir","year":"2008","unstructured":"Snir S, Warnow T, Rao S. Short Quartet Puzzling: A New Quartet-Based Phylogeny Reconstruction Algorithm. J Comput Biol. 2008;15(1):91\u2013103. https:\/\/doi.org\/10.1089\/cmb.2007.0103.","journal-title":"J Comput Biol"},{"issue":"3","key":"257_CR6","doi-asserted-by":"publisher","first-page":"523","DOI":"10.2307\/2413694","volume":"46","author":"WP Maddison","year":"1997","unstructured":"Maddison WP. Gene trees in species trees. Syst Biol. 1997;46(3):523\u201336. https:\/\/doi.org\/10.2307\/2413694.","journal-title":"Syst Biol"},{"key":"257_CR7","volume-title":"Species tree inference: a guide to methods and applications","author":"PD Blischak","year":"2023","unstructured":"Blischak PD, Brown JM, Cao Z, Cloutier A, Cobb K, DiGiacomo, AA, Eaton DA, Edwards SV, Gallivan KA, Gates DJ. Species tree inference: a guide to methods and applications. Princeton: Princeton University Press; 2023."},{"key":"257_CR8","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1007\/s00285-010-0355-7","volume":"62","author":"ES Allman","year":"2011","unstructured":"Allman ES, Degnan JH, Rhodes JA. Identifying the rooted species tree from the distribution of unrooted gene trees under the coalescent. J Math Biol. 2011;62:833\u201362.","journal-title":"J Math Biol"},{"key":"257_CR9","unstructured":"Pamilo P, Nei M. Relationships between gene trees and species trees. Molecular biology and evolution 1988;5(5), 568\u2013583 . ISBN: 0737-4038 (Print)"},{"key":"257_CR10","doi-asserted-by":"crossref","unstructured":"Rannala B, Yang, Z. Bayes estimation of species divergence times and ancestral population sizes using DNA sequences from multiple loci. Genetics 2003;164(4), 1645\u20131656. Publisher: Department of Medical Genetics, University of Alberta, Edmonton, Alberta T6G 2H7, Canada.","DOI":"10.1093\/genetics\/164.4.1645"},{"issue":"5","key":"257_CR11","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1089\/cmb.2020.0424","volume":"28","author":"B Legried","year":"2021","unstructured":"Legried B, Molloy EK, Warnow T, Roch S. Polynomial-time statistical estimation of species trees under gene duplication and loss. J Comput Biol. 2021;28(5):452\u201368. https:\/\/doi.org\/10.1089\/cmb.2020.0424.","journal-title":"J Comput Biol"},{"key":"257_CR12","unstructured":"Hill M, Legried B, Roch S. Species tree estimation under joint modeling of coalescence and duplication: sample complexity of quartet methods. arXiv, 2020;2007\u201306697. arXiv: 2007.06697"},{"issue":"2","key":"257_CR13","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1089\/cmb.2012.0234","volume":"20","author":"S Roch","year":"2013","unstructured":"Roch S, Snir S. Recovering the treelike trend of evolution despite extensive lateral genetic transfer: a probabilistic analysis. J Comput Biol. 2013;20(2):93\u2013112. https:\/\/doi.org\/10.1089\/cmb.2012.0234.","journal-title":"J Comput Biol"},{"key":"257_CR14","doi-asserted-by":"publisher","unstructured":"Markin A, Eulenstein O. Quartet-based inference is statistically consistent under the unified duplication-loss-coalescence model. Bioinformatics, 2021; 414 https:\/\/doi.org\/10.1093\/bioinformatics\/btab414","DOI":"10.1093\/bioinformatics\/btab414"},{"issue":"17","key":"257_CR15","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1093\/bioinformatics\/btu462","volume":"30","author":"S Mirarab","year":"2014","unstructured":"Mirarab S, Reaz R, Bayzid MS, Zimmermann T, Swenson MS, Warnow T. ASTRAL: genome-scale coalescent-based species tree estimation. Bioinformatics. 2014;30(17):541\u20138. https:\/\/doi.org\/10.1093\/bioinformatics\/btu462.","journal-title":"Bioinformatics"},{"issue":"23","key":"257_CR16","doi-asserted-by":"publisher","first-page":"3317","DOI":"10.1093\/bioinformatics\/btu530","volume":"30","author":"J Chifman","year":"2014","unstructured":"Chifman J, Kubatko LS. Quartet inference from SNP data under the coalescent model. Bioinformatics. 2014;30(23):3317\u201324. https:\/\/doi.org\/10.1093\/bioinformatics\/btu530.","journal-title":"Bioinformatics"},{"key":"257_CR17","doi-asserted-by":"publisher","unstructured":"Larget BR, Kotha SK, Dewey CN, An\u00e9 C. BUCKy: Gene tree\/species tree reconciliation with Bayesian concordance analysis. Bioinformatics 2010; 26(22), 2910\u20132911 https:\/\/doi.org\/10.1093\/bioinformatics\/btq539 . arXiv: 0912.4472 Publisher: Department of Statistics, University of Wisconsin-Madison, WI 53706, USA. ISBN: 03036812","DOI":"10.1093\/bioinformatics\/btq539"},{"issue":"S10","key":"257_CR18","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1186\/s12864-016-3098-z","volume":"17","author":"E Sayyari","year":"2016","unstructured":"Sayyari E, Mirarab S. Anchoring quartet-based phylogenetic distances and applications to species tree reconstruction. BMC Genomics. 2016;17(S10):101\u201313. https:\/\/doi.org\/10.1186\/s12864-016-3098-z.","journal-title":"BMC Genomics"},{"key":"257_CR19","doi-asserted-by":"publisher","unstructured":"Brown DG, Truszkowski, J. Towards a Practical O(n logn) Phylogeny Algorithm, pp. 14\u201325 2011; https:\/\/doi.org\/10.1007\/978-3-642-23038-7_2 .","DOI":"10.1007\/978-3-642-23038-7_2"},{"key":"257_CR20","unstructured":"Bryant D, Tsang J, Kearney PE, Li M. Computing the quartet distance between evolutionary trees, vol. 9, pp. 285\u2013286. Citeseer, 2000;. Issue: 11"},{"issue":"12","key":"257_CR21","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1093\/bioinformatics\/btv234","volume":"31","author":"S Mirarab","year":"2015","unstructured":"Mirarab S, Warnow T. ASTRAL-II: Coalescent-based species tree estimation with many hundreds of taxa and thousands of genes. Bioinformatics. 2015;31(12):44\u201352. https:\/\/doi.org\/10.1093\/bioinformatics\/btv234.","journal-title":"Bioinformatics"},{"key":"257_CR22","doi-asserted-by":"publisher","unstructured":"Brodal GS, Fagerberg R, Mailund T, Pedersen CNS, Sand, A. Efficient Algorithms for Computing the Triplet and Quartet Distance Between Trees of Arbitrary Degree. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1814\u20131832. Society for Industrial and Applied Mathematics, Philadelphia, PA 2013;. https:\/\/doi.org\/10.1137\/1.9781611973105.130 . https:\/\/epubs.siam.org\/doi\/10.1137\/1.9781611973105.130","DOI":"10.1137\/1.9781611973105.130"},{"issue":"6","key":"257_CR23","doi-asserted-by":"publisher","first-page":"1532","DOI":"10.1093\/bioinformatics\/btab875","volume":"38","author":"U Mai","year":"2022","unstructured":"Mai U, Mirarab S. Completing gene trees without species trees in sub-quadratic time. Bioinformatics. 2022;38(6):1532\u201341. https:\/\/doi.org\/10.1093\/bioinformatics\/btab875.","journal-title":"Bioinformatics"},{"issue":"12","key":"257_CR24","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1093\/molbev\/msac215","volume":"39","author":"C Zhang","year":"2022","unstructured":"Zhang C, Mirarab S. Weighting by gene tree uncertainty improves accuracy of quartet-based species trees. Mol Biol Evol. 2022;39(12):215. https:\/\/doi.org\/10.1093\/molbev\/msac215.","journal-title":"Mol Biol Evol"},{"key":"257_CR25","doi-asserted-by":"publisher","unstructured":"Hallett M T, Lagergren, J. New algorithms for the duplication-loss model. In: Proceedings of the Fourth Annual International Conference on Computational Molecular Biology - RECOMB \u201900, pp. 138\u2013146. ACM Press, New York, New York, USA 2000; https:\/\/doi.org\/10.1145\/332306.332359","DOI":"10.1145\/332306.332359"},{"issue":"1","key":"257_CR26","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1006\/jagm.2000.1133","volume":"38","author":"D Bryant","year":"2001","unstructured":"Bryant D, Steel M. Constructing optimal trees from quartets. J Algorithms. 2001;38(1):237\u201359. https:\/\/doi.org\/10.1006\/jagm.2000.1133.","journal-title":"J Algorithms"},{"issue":"9","key":"257_CR27","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.1000501","volume":"5","author":"C Than","year":"2009","unstructured":"Than C, Nakhleh L. Species tree inference by minimizing deep coalescences. PLoS Comput Biol. 2009;5(9):1000501. https:\/\/doi.org\/10.1371\/journal.pcbi.1000501.","journal-title":"PLoS Comput Biol"},{"issue":"S6","key":"257_CR28","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1186\/s12859-018-2129-y","volume":"19","author":"C Zhang","year":"2018","unstructured":"Zhang C, Rabiee M, Sayyari E, Mirarab S. ASTRAL-III: polynomial time species tree reconstruction from partially resolved gene trees. BMC Bioinform. 2018;19(S6):153. https:\/\/doi.org\/10.1186\/s12859-018-2129-y.","journal-title":"BMC Bioinform"},{"key":"257_CR29","doi-asserted-by":"publisher","unstructured":"Zhang C, Nielsen R, Mirarab S. CASTER: Direct species tree inference from whole-genome alignments. bioRxiv prepress 2023;https:\/\/doi.org\/10.1101\/2023.10.04.560884","DOI":"10.1101\/2023.10.04.560884"},{"issue":"2","key":"257_CR30","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1093\/sysbio\/syu087","volume":"64","author":"E Avni","year":"2015","unstructured":"Avni E, Cohen R, Snir S. Weighted quartets phylogenetics. Syst Biol. 2015;64(2):233\u201342. https:\/\/doi.org\/10.1093\/sysbio\/syu087.","journal-title":"Syst Biol"},{"key":"257_CR31","doi-asserted-by":"publisher","DOI":"10.1017\/9781316882313","volume-title":"Computational phylogenetics: an introduction to designing methods for phylogeny estimation","author":"T Warnow","year":"2017","unstructured":"Warnow T. Computational phylogenetics: an introduction to designing methods for phylogeny estimation. Cambridge: Cambridge University Press; 2017."},{"issue":"14","key":"257_CR32","doi-asserted-by":"publisher","first-page":"2079","DOI":"10.1093\/bioinformatics\/btu157","volume":"30","author":"A Sand","year":"2014","unstructured":"Sand A, Holt MK, Johansen J, Brodal GS, Mailund T, Pedersen CNS. tqDist: a library for computing the quartet and triplet distances between binary or general trees. Bioinformatics. 2014;30(14):2079\u201380. https:\/\/doi.org\/10.1093\/bioinformatics\/btu157.","journal-title":"Bioinformatics"},{"issue":"1","key":"257_CR33","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1093\/sysbio\/syac031","volume":"72","author":"Y Jiang","year":"2022","unstructured":"Jiang Y, Balaban M, Zhu Q, Mirarab S. DEPP: deep learning enables extending species trees using single genes. Syst Biol. 2022;72(1):17\u201334. https:\/\/doi.org\/10.1093\/sysbio\/syac031.","journal-title":"Syst Biol"},{"issue":"2","key":"257_CR34","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1093\/sysbio\/syv082","volume":"65","author":"D Mallo","year":"2016","unstructured":"Mallo D, De Oliveira Martins L, Posada D. SimPhy: phylogenomic simulation of gene, locus, and species trees. Syst Biol. 2016;65(2):334\u201344. https:\/\/doi.org\/10.1093\/sysbio\/syv082.","journal-title":"Syst Biol"},{"issue":"3","key":"257_CR35","doi-asserted-by":"publisher","first-page":"9490","DOI":"10.1371\/journal.pone.0009490","volume":"5","author":"MN Price","year":"2010","unstructured":"Price MN, Dehal PS, Arkin AP. FastTree-2 - approximately maximum-likelihood trees for large alignments. PLoS ONE. 2010;5(3):9490. https:\/\/doi.org\/10.1371\/journal.pone.0009490.","journal-title":"PLoS ONE"},{"issue":"1\u20132","key":"257_CR36","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0025-5564(81)90043-2","volume":"53","author":"D Robinson","year":"1981","unstructured":"Robinson D, Foulds L. Comparison of phylogenetic trees. Math Biosci. 1981;53(1\u20132):131\u201347.","journal-title":"Math Biosci"},{"issue":"7","key":"257_CR37","doi-asserted-by":"publisher","first-page":"1654","DOI":"10.1093\/molbev\/msw079","volume":"33","author":"E Sayyari","year":"2016","unstructured":"Sayyari E, Mirarab S. Fast coalescent-based computation of local branch support from quartet frequencies. Mol Biol Evol. 2016;33(7):1654\u201368. https:\/\/doi.org\/10.1093\/molbev\/msw079.","journal-title":"Mol Biol Evol"},{"issue":"1","key":"257_CR38","doi-asserted-by":"publisher","first-page":"1983","DOI":"10.1038\/s41467-021-22073-8","volume":"12","author":"D Azouri","year":"2021","unstructured":"Azouri D, Abadi S, Mansour Y, Mayrose I, Pupko T. Harnessing machine learning to guide phylogenetic-tree search algorithms. Nat Commun. 2021;12(1):1983. https:\/\/doi.org\/10.1038\/s41467-021-22073-8.","journal-title":"Nat Commun"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-024-00257-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-024-00257-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-024-00257-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,16]],"date-time":"2024-03-16T20:01:32Z","timestamp":1710619292000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-024-00257-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,13]]},"references-count":38,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,12]]}},"alternative-id":["257"],"URL":"https:\/\/doi.org\/10.1186\/s13015-024-00257-3","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,13]]},"assertion":[{"value":"30 November 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 February 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 March 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"12"}}