The phylogenetic tree reconstruction game: developing reinforcement-learning algorithms for fast and accurate inference of evolutionary trees

The following two fields have never interacted before: reinforcement learning and molecular evolution. Here we develop a reinforcement-learning algorithm to solve the challenge of reconstructing phylogenetic trees, which are used to describe the evolutionary relationships among a set of genome sequences. The current tools for phylogenetic tree reconstruction integrate heuristic approaches to evaluate only a subset of all potential trees, thus all suffer from the known trade-off between accuracy and running time. Although recent studies have shown the potential of harnessing AI-based methods to reconstruct phylogenetic trees, the question regarding the overall tree-search strategy remains open. In our study, we provide a novel methodology for predicting the maximum-likelihood tree. We demonstrated that a framework that optimizes a sequence of two "lookahead" moves into the horizon, is superior compared to a framework which optimizes a single move at a time (see the attached figure). These preliminary results thus suggest that our proposed paradigm, that uses reinforcement-learning techniques to learn an optimal strategy for the tree search, can boost tree search-heuristics without compromising accuracy.

The full article >