Constructing phylogenetic networks via cherry picking and machine learning

Giulia Bernardini, Leo van Iersel, Esther Julien, Leen Stougie*

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)
17 Downloads (Pure)

Abstract

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.

Original languageEnglish
Article number13
Number of pages28
JournalAlgorithms for Molecular Biology
Volume18
Issue number1
DOIs
Publication statusPublished - 2023

Keywords

  • Cherry picking
  • Heuristic
  • Hybridization
  • Machine learning
  • Phylogenetics

Fingerprint

Dive into the research topics of 'Constructing phylogenetic networks via cherry picking and machine learning'. Together they form a unique fingerprint.

Cite this