Cargando…
Constructing phylogenetic networks via cherry picking and machine learning
BACKGROUND: 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...
Autores principales: | , , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
BioMed Central
2023
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10505335/ https://www.ncbi.nlm.nih.gov/pubmed/37717003 http://dx.doi.org/10.1186/s13015-023-00233-3 |
_version_ | 1785106897189208064 |
---|---|
author | Bernardini, Giulia van Iersel, Leo Julien, Esther Stougie, Leen |
author_facet | Bernardini, Giulia van Iersel, Leo Julien, Esther Stougie, Leen |
author_sort | Bernardini, Giulia |
collection | PubMed |
description | BACKGROUND: 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. RESULTS: 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. CONCLUSIONS: 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. |
format | Online Article Text |
id | pubmed-10505335 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2023 |
publisher | BioMed Central |
record_format | MEDLINE/PubMed |
spelling | pubmed-105053352023-09-18 Constructing phylogenetic networks via cherry picking and machine learning Bernardini, Giulia van Iersel, Leo Julien, Esther Stougie, Leen Algorithms Mol Biol Research BACKGROUND: 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. RESULTS: 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. CONCLUSIONS: 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. BioMed Central 2023-09-16 /pmc/articles/PMC10505335/ /pubmed/37717003 http://dx.doi.org/10.1186/s13015-023-00233-3 Text en © The Author(s) 2023 https://creativecommons.org/licenses/by/4.0/Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/ (https://creativecommons.org/licenses/by/4.0/) . The Creative Commons Public Domain Dedication waiver (http://creativecommons.org/publicdomain/zero/1.0/ (https://creativecommons.org/publicdomain/zero/1.0/) ) applies to the data made available in this article, unless otherwise stated in a credit line to the data. |
spellingShingle | Research Bernardini, Giulia van Iersel, Leo Julien, Esther Stougie, Leen Constructing phylogenetic networks via cherry picking and machine learning |
title | Constructing phylogenetic networks via cherry picking and machine learning |
title_full | Constructing phylogenetic networks via cherry picking and machine learning |
title_fullStr | Constructing phylogenetic networks via cherry picking and machine learning |
title_full_unstemmed | Constructing phylogenetic networks via cherry picking and machine learning |
title_short | Constructing phylogenetic networks via cherry picking and machine learning |
title_sort | constructing phylogenetic networks via cherry picking and machine learning |
topic | Research |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10505335/ https://www.ncbi.nlm.nih.gov/pubmed/37717003 http://dx.doi.org/10.1186/s13015-023-00233-3 |
work_keys_str_mv | AT bernardinigiulia constructingphylogeneticnetworksviacherrypickingandmachinelearning AT vanierselleo constructingphylogeneticnetworksviacherrypickingandmachinelearning AT julienesther constructingphylogeneticnetworksviacherrypickingandmachinelearning AT stougieleen constructingphylogeneticnetworksviacherrypickingandmachinelearning |