EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC 4.0

The Tree Reconstruction Game: Phylogenetic Reconstruction Using Reinforcement Learning

Dana Azouri iD, Oz Granit iD, Michael Alburquerque iD, Yishay Mansour iD, Tal Pupko iD, Itay Mayrose iD

Molecular Biology and Evolution · 2024

DOI: 10.1093/molbev/msae105 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Molecular Biology and Evolution, 2024. Verfasst von Dana Azouri und 5 weiteren Autor:innen. Beteiligte Einrichtung: School of Plant Sciences and Food Security, Tel Aviv University, Ramat Aviv, Tel Aviv 69978, Israel. Hauptthemen laut MEDLINE: Phylogeny, Algorithms. Die Arbeit wurde bisher 18-mal zitiert (Crossref) und nennt 46 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC 4.0).

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The computational search for the maximum-likelihood phylogenetic tree is an NP-hard problem. As such, current tree search algorithms might result in a tree that is the local optima, not the global one. Here, we introduce a paradigm shift for predicting the maximum-likelihood tree, by approximating long-term gains of likelihood rather than maximizing likelihood gain at each step of the search. Our proposed approach harnesses the power of reinforcement learning to learn an optimal search strategy, aiming at the global optimum of the search space. We show that when analyzing empirical data containing dozens of sequences, the log-likelihood improvement from the starting tree obtained by the reinforcement learning–based agent was 0.969 or higher compared to that achieved by current state-of-the-art techniques. Notably, this performance is attained without the need to perform costly likelihood optimizations apart from the training process, thus potentially allowing for an exponential increase in runtime. We exemplify this for data sets containing 15 sequences of length 18,000 bp and demonstrate that the reinforcement learning–based method is roughly three times faster than the state-of-the-art software. This study illustrates the potential of reinforcement learning in addressing the challenges of phylogenetic tree reconstruction.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

PhylogenyAlgorithmsLikelihood FunctionsModels, GeneticComputational BiologySoftware

Stichwörter der Autor:innen

artificial intelligenceevolutionmachine learningmolecular biologyphylogeneticsreinforcement learning

Autor:innen und Institutionen

  • School of Plant Sciences and Food Security, Tel Aviv University, Ramat Aviv, Tel Aviv 69978, Israel.
  • The Shmunis School of Biomedicine and Cancer Research, Tel Aviv University, Ramat Aviv, Tel Aviv 69978, Israel.
  • Balvatnik School of Computer Science, Tel Aviv University, Ramat Aviv, Tel Aviv 69978, Israel.

ORCID-Profile: Dana Azouri, Oz Granit, Michael Alburquerque, Yishay Mansour, Tal Pupko, Itay Mayrose

Zitieren

APA

Azouri, D., Granit, O., Alburquerque, M., Mansour, Y., Pupko, T., & Mayrose, I. (2024). The Tree Reconstruction Game: Phylogenetic Reconstruction Using Reinforcement Learning. Molecular Biology and Evolution. https://doi.org/10.1093/molbev/msae105

Vancouver

Azouri D, Granit O, Alburquerque M, Mansour Y, Pupko T, Mayrose I. The Tree Reconstruction Game: Phylogenetic Reconstruction Using Reinforcement Learning. Molecular Biology and Evolution. 2024. doi:10.1093/molbev/msae105

BibTeX
@article{Azouri2024,
  author = {Azouri, Dana and Granit, Oz and Alburquerque, Michael and Mansour, Yishay and Pupko, Tal and Mayrose, Itay},
  title = {The Tree Reconstruction Game: Phylogenetic Reconstruction Using Reinforcement Learning},
  journal = {Molecular Biology and Evolution},
  year = {2024},
  doi = {10.1093/molbev/msae105}
}
Kostenlos starten →