The Tree Reconstruction Game: Phylogenetic Reconstruction Using Reinforcement Learning
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).
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)
Stichwörter der Autor:innen
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}
}
EUVIMED