{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T04:31:40Z","timestamp":1775017900847,"version":"3.50.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,9,16]],"date-time":"2023-09-16T00:00:00Z","timestamp":1694822400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,9,16]],"date-time":"2023-09-16T00:00:00Z","timestamp":1694822400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["OCENW.GROOT.2019.015"],"award-info":[{"award-number":["OCENW.GROOT.2019.015"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007601","name":"Horizon 2020","doi-asserted-by":"publisher","award":["872539"],"award-info":[{"award-number":["872539"]}],"id":[{"id":"10.13039\/501100007601","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:sec><jats:title>Background<\/jats:title><jats:p>Combining a set of phylogenetic trees into a single phylogenetic network that explains all of them is a fundamental challenge in evolutionary studies. Existing methods are computationally expensive and can either handle only small numbers of phylogenetic trees or are limited to severely restricted classes of networks.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>In this paper, we apply the recently-introduced theoretical framework of cherry picking to design a class of efficient heuristics that are guaranteed to produce a network containing each of the input trees, for practical-size datasets consisting of binary trees. Some of the heuristics in this framework are based on the design and training of a machine learning model that captures essential information on the structure of the input trees and guides the algorithms towards better solutions. We also propose simple and fast randomised heuristics that prove to be very effective when run multiple times.<\/jats:p><\/jats:sec><jats:sec><jats:title>Conclusions<\/jats:title><jats:p>Unlike the existing exact methods, our heuristics are applicable to datasets of practical size, and the experimental study we conducted on both simulated and real data shows that these solutions are qualitatively good, always within some small constant factor from the optimum. Moreover, our machine-learned heuristics are one of the first applications of machine learning to phylogenetics and show its promise.<\/jats:p><\/jats:sec>","DOI":"10.1186\/s13015-023-00233-3","type":"journal-article","created":{"date-parts":[[2023,9,16]],"date-time":"2023-09-16T15:01:39Z","timestamp":1694876499000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Constructing phylogenetic networks via cherry picking and machine learning"],"prefix":"10.1186","volume":"18","author":[{"given":"Giulia","family":"Bernardini","sequence":"first","affiliation":[]},{"given":"Leo","family":"van Iersel","sequence":"additional","affiliation":[]},{"given":"Esther","family":"Julien","sequence":"additional","affiliation":[]},{"given":"Leen","family":"Stougie","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,9,16]]},"reference":[{"issue":"8","key":"233_CR1","doi-asserted-by":"publisher","first-page":"914","DOI":"10.1016\/j.dam.2006.08.008","volume":"155","author":"M Bordewich","year":"2007","unstructured":"Bordewich M, Semple C. Computing the minimum number of hybridization events for a consistent evolutionary history. Discrete Appl Math. 2007;155(8):914\u201328.","journal-title":"Discrete Appl Math"},{"key":"233_CR2","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1016\/j.aam.2019.01.004","volume":"105","author":"S Linz","year":"2019","unstructured":"Linz S, Semple C. Attaching leaves and picking cherries to characterise the hybridisation number for a set of phylogenies. Adv Appl Math. 2019;105:102\u201329.","journal-title":"Adv Appl Math"},{"key":"233_CR3","doi-asserted-by":"publisher","first-page":"917","DOI":"10.1007\/s00453-021-00914-8","volume":"84","author":"L van Iersel","year":"2022","unstructured":"van Iersel L, Janssen R, Jones M, Murakami Y, Zeh N. A practical fixed-parameter algorithm for constructing tree-child networks from multiple binary trees. Algorithmica. 2022;84:917\u201360.","journal-title":"Algorithmica"},{"issue":"4","key":"233_CR4","doi-asserted-by":"publisher","first-page":"1004135","DOI":"10.1371\/journal.pcbi.1004135","volume":"11","author":"F Pardi","year":"2015","unstructured":"Pardi F, Scornavacca C. Reconstructible phylogenetic networks: do not distinguish the indistinguishable. PLoS Comput Biol. 2015;11(4):1004135.","journal-title":"PLoS Comput Biol"},{"issue":"2","key":"233_CR5","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1093\/sysbio\/syq084","volume":"60","author":"Y Yu","year":"2011","unstructured":"Yu Y, Than C, Degnan JH, Nakhleh L. Coalescent histories on phylogenetic networks and detection of hybridization despite incomplete lineage sorting. Syst Biol. 2011;60(2):138\u201349.","journal-title":"Syst Biol"},{"issue":"8","key":"233_CR6","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/s11538-022-01037-z","volume":"84","author":"L van Iersel","year":"2022","unstructured":"van Iersel L, Janssen R, Jones M, Murakami Y. Orchard networks are trees with additional horizontal arcs. Bull Math Biol. 2022;84(8):76.","journal-title":"Bull Math Biol"},{"issue":"1","key":"233_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s12859-015-0660-7","volume":"16","author":"B Albrecht","year":"2015","unstructured":"Albrecht B. Computing all hybridization networks for multiple binary phylogenetic input trees. BMC Bioinform. 2015;16(1):1\u201315.","journal-title":"BMC Bioinform"},{"issue":"12","key":"233_CR8","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1093\/bioinformatics\/btq198","volume":"26","author":"Y Wu","year":"2010","unstructured":"Wu Y. Close lower and upper bounds for the minimum reticulate network of multiple phylogenetic trees. Bioinformatics. 2010;26(12):140\u20138.","journal-title":"Bioinformatics"},{"issue":"3","key":"233_CR9","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1109\/TCBB.2015.2462336","volume":"13","author":"S Mirzaei","year":"2015","unstructured":"Mirzaei S, Wu Y. Fast construction of near parsimonious hybridization networks for multiple phylogenetic trees. IEEE\/ACM Trans Comput Biol Bioinform. 2015;13(3):565\u201370.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"issue":"4","key":"233_CR10","doi-asserted-by":"publisher","first-page":"735","DOI":"10.1093\/sysbio\/syy015","volume":"67","author":"D Wen","year":"2018","unstructured":"Wen D, Yu Y, Zhu J, Nakhleh L. Inferring phylogenetic networks using phylonet. Systematic biology. 2018;67(4):735\u201340.","journal-title":"Syst Biology"},{"issue":"12","key":"233_CR11","doi-asserted-by":"publisher","first-page":"3292","DOI":"10.1093\/molbev\/msx235","volume":"34","author":"C Sol\u00eds-Lemus","year":"2017","unstructured":"Sol\u00eds-Lemus C, Bastide P, An\u00e9 C. Phylonetworks: a package for phylogenetic networks. Mol Biol Evol. 2017;34(12):3292\u20138.","journal-title":"Mol Biol Evol"},{"issue":"10","key":"233_CR12","doi-asserted-by":"publisher","first-page":"1879","DOI":"10.1007\/s11538-013-9874-x","volume":"75","author":"PJ Humphries","year":"2013","unstructured":"Humphries PJ, Linz S, Semple C. Cherry picking: a characterization of the temporal hybridization number for a set of phylogenies. Bull Math Biol. 2013;75(10):1879\u201390.","journal-title":"Bull Math Biol"},{"key":"233_CR13","doi-asserted-by":"crossref","unstructured":"Borst S, van Iersel L, Jones M, Kelk S. New FPT algorithms for finding the temporal hybridization number for sets of phylogenetic trees. Algorithmica. 2022;84(7):2050\u201387.","DOI":"10.1007\/s00453-022-00946-8"},{"issue":"3","key":"233_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00285-021-01654-7","volume":"83","author":"C Semple","year":"2021","unstructured":"Semple C, Toft G. Trinets encode orchard phylogenetic networks. J Math Biol. 2021;83(3):1\u201320.","journal-title":"J Math Biol"},{"key":"233_CR15","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/j.tcs.2020.12.031","volume":"856","author":"R Janssen","year":"2021","unstructured":"Janssen R, Murakami Y. On cherry-picking and network containment. Theor Comput Sci. 2021;856:121\u201350.","journal-title":"Theor Comput Sci"},{"issue":"1","key":"233_CR16","doi-asserted-by":"publisher","first-page":"1","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):1\u20139.","journal-title":"Nat Commun"},{"key":"233_CR17","doi-asserted-by":"publisher","unstructured":"Zhu T, Cai Y. Applying neural network to reconstruction of phylogenetic tree. In: 2021 13th International Conference on Machine Learning and Computing. ICMLC 2021, pp. 146\u2013152. Association for Computing Machinery, New York, NY, USA; 2021. https:\/\/doi.org\/10.1145\/3457682.3457704","DOI":"10.1145\/3457682.3457704"},{"issue":"11","key":"233_CR18","doi-asserted-by":"publisher","first-page":"4674","DOI":"10.1093\/molbev\/msab227","volume":"38","author":"S Kumar","year":"2021","unstructured":"Kumar S, Sharma S. Evolutionary sparse learning for phylogenomics. Mol Biol Evol. 2021;38(11):4674\u201382.","journal-title":"Mol Biol Evol"},{"key":"233_CR19","doi-asserted-by":"publisher","unstructured":"Bernardini G, van Iersel L, Julien E, Stougie L. Reconstructing phylogenetic networks via cherry picking and machine learning. In: 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022). Leibniz International Proceedings in Informatics (LIPIcs), vol. 242, pp. 16\u201311622. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany; 2022. https:\/\/doi.org\/10.4230\/LIPIcs.WABI.2022.16","DOI":"10.4230\/LIPIcs.WABI.2022.16"},{"key":"233_CR20","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2021.102222","volume":"129","author":"L van Iersel","year":"2021","unstructured":"van Iersel L, Janssen R, Jones M, Murakami Y, Zeh N. A unifying characterization of tree-based networks and orchard networks using cherry covers. Adv Appl Math. 2021;129: 102222. https:\/\/doi.org\/10.1016\/j.aam.2021.102222.","journal-title":"Adv Appl Math"},{"issue":"2","key":"233_CR21","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D Harel","year":"1984","unstructured":"Harel D, Tarjan RE. Fast algorithms for finding nearest common ancestors. SIAM J Comput. 1984;13(2):338\u201355. https:\/\/doi.org\/10.1137\/0213024.","journal-title":"SIAM J Comput"},{"issue":"1","key":"233_CR22","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1109\/TCBB.2019.2895344","volume":"17","author":"JC Pons","year":"2019","unstructured":"Pons JC, Scornavacca C, Cardona G. Generation of level-$$k$$ LGT networks. IEEE\/ACM Trans Comput Biol Bioinf. 2019;17(1):158\u201364.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"issue":"3","key":"233_CR23","doi-asserted-by":"publisher","first-page":"785","DOI":"10.1109\/TCBB.2010.69","volume":"8","author":"S Willson","year":"2010","unstructured":"Willson S. Regular networks can be uniquely constructed from their trees. IEEE\/ACM Trans Comput Biol Bioinf. 2010;8(3):785\u201396.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"key":"233_CR24","first-page":"2825","volume":"12","author":"F Pedregosa","year":"2011","unstructured":"Pedregosa F, Varoquaux G, Gramfort A, Michel V, Thirion B, Grisel O, Blondel M, Prettenhofer P, Weiss R, Dubourg V, Vanderplas J, Passos A, Cournapeau D, Brucher M, Perrot M, Duchesnay E. Scikit-learn: Machine learning in Python. J Mach Learn Res. 2011;12:2825\u201330.","journal-title":"J Mach Learn Res"},{"issue":"2","key":"233_CR25","doi-asserted-by":"publisher","first-page":"504","DOI":"10.1093\/molbev\/msx307","volume":"35","author":"C Zhang","year":"2018","unstructured":"Zhang C, Ogilvie HA, Drummond AJ, Stadler T. Bayesian inference of species networks from multilocus sequence data. Mol Biol Evol. 2018;35(2):504\u201317.","journal-title":"Mol Biol Evol"},{"issue":"06","key":"233_CR26","doi-asserted-by":"publisher","first-page":"2140012","DOI":"10.1142\/S0219720021400126","volume":"19","author":"R Janssen","year":"2021","unstructured":"Janssen R, Liu P. Comparing the topology of phylogenetic network generators. J Bioinf Comput Biol. 2021;19(06):2140012.","journal-title":"J Bioinf Comput Biol"},{"issue":"1","key":"233_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1745-6150-6-34","volume":"6","author":"RG Beiko","year":"2011","unstructured":"Beiko RG. Telling the whole story in a 10,000-genome world. Biol Direct. 2011;6(1):1\u201336.","journal-title":"Biol Direct"},{"issue":"4","key":"233_CR28","doi-asserted-by":"publisher","first-page":"1431","DOI":"10.1137\/110845045","volume":"42","author":"C Whidden","year":"2013","unstructured":"Whidden C, Beiko RG, Zeh N. Fixed-parameter algorithms for maximum agreement forests. SIAM J Comput. 2013;42(4):1431\u201366. https:\/\/doi.org\/10.1137\/110845045.","journal-title":"SIAM J Comput."}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-023-00233-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-023-00233-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-023-00233-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,28]],"date-time":"2024-10-28T06:07:26Z","timestamp":1730095646000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-023-00233-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,16]]},"references-count":28,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,12]]}},"alternative-id":["233"],"URL":"https:\/\/doi.org\/10.1186\/s13015-023-00233-3","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,16]]},"assertion":[{"value":"31 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 June 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 September 2023","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 that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"13"}}