The tree reconstruction game: phylogenetic reconstruction using reinforcement learning

Dana Azouri, Oz Granit, Michael Alburquerque, Yishay Mansour, Tal Pupko, Itay MayrosearXiv 2023 · OpenReview

TL;DR

This paper introduces a novel reinforcement learning (RL) approach for reconstructing phylogenetic trees, a computationally challenging task. By framing tree reconstruction as a game, their deep Q-learning agent learns an optimal search strategy, outperforming traditional greedy methods and achieving comparable accuracy to existing state-of-the-art tools without requiring constant likelihood calculations.

What Problem Does This Paper Address?

Reconstructing phylogenetic trees, which depict evolutionary relationships between species or organisms, is fundamental to many biological disciplines. The core challenge lies in the sheer number of possible tree topologies, which grows exponentially with the number of sequences. This makes finding the "best" tree (often defined by maximum likelihood) an NP-hard problem. Current methods rely on heuristics, which are often based on expert intuition and can get stuck in local optima. The authors aim to develop an AI-driven approach that can learn an optimal search strategy, moving beyond these limitations.

Methods

The authors propose a reinforcement learning framework, specifically using a Deep Q-network (DQN), to tackle phylogenetic tree reconstruction. They model the problem as a "game" where:

  • States (S): Represent all possible phylogenetic trees for a given set of aligned sequences.
  • Actions (A): Are Subtree Pruning and Regrafting (SPR) moves, which alter the tree topology.
  • Reward (R): Is based on the change in log-likelihood after an SPR move, scaled by a reference tree's likelihood.

The DQN agent learns a policy to maximize a cumulative reward over a sequence of moves, aiming to find the tree with the highest likelihood. Key aspects include:

  • Feature Extraction: A vector of 27 features representing the current tree topology, branch lengths, and the proposed SPR move is used as input to the neural network.
  • Deep Q-Learning: A neural network estimates the Q-value (expected future reward) for each state-action pair.
  • Exploration-Exploitation Strategy: A SoftMax exploration strategy is employed to balance exploring new moves with exploiting known good ones.
  • Non-Greedy Approach: Unlike traditional methods, the RL agent can take "suboptimal" moves in the short term if they are expected to lead to a better overall outcome.

Datasets

The study utilizes empirical datasets of nucleotide coding alignments, user-submitted phylogenies, and genomic sequences. These datasets were categorized by the number of sequences: 7, 12, 15, and 20. For each size, a portion of the datasets were used for training, validation, and testing. No new benchmarks were introduced; instead, the authors used existing empirical data to test their RL framework.

Key Insights and Ideas

  • RL as a "Game" for Tree Search: Framing phylogenetic reconstruction as a dynamic game where the optimal strategy is unknown and must be learned is a novel conceptualization.
  • Beyond Greedy Optimization: The RL agent's ability to make non-greedy, potentially suboptimal moves in the short term is crucial for escaping local optima and finding better trees. This is a significant departure from traditional heuristic approaches.
  • Learning Search Strategies: The RL agent learns how to search for the best tree, rather than relying on pre-defined rules or expert intuition. This allows for adaptation to different datasets.
  • Reduced Likelihood Calculations: The RL approach doesn't require calculating the likelihood at every single step, potentially speeding up the process, especially for large datasets.

Key Results

  • Comparable Accuracy: The RL agent achieved likelihood scores comparable to widely-used software like RaxML-NG on empirical datasets. For 12-sequence datasets, the average accuracy was 0.969.
  • Benefit of Non-Greedy Moves: Analysis showed that greedy approaches were suboptimal in 33% and 41% of cases for 7 and 12-sequence datasets, respectively, highlighting the advantage of the RL agent's flexible strategy.
  • Scalability: While training time can be significant (e.g., 600 CPU hours for 15 sequences), inference time after training is very fast (around 8.7 seconds for 15 sequences), and notably, it does not depend on MSA length.
  • Zero-Shot Transfer: Pre-trained agents showed promising performance when applied to datasets of different sizes, indicating a degree of transferability in learned search strategies.

Limitations and Future Work

  • Training Time: The training process for the RL agent is computationally intensive, especially for larger datasets.
  • Accuracy for >20 Sequences: The accuracy for datasets with more than 20 sequences was not satisfactory, suggesting challenges in scaling to very large phylogenetic search spaces.
  • Feature Engineering: While the current feature set is effective, the authors suggest that improved representations of trees and alignments could further enhance performance.
  • Future Directions: The authors propose several avenues for future research:
  • Improving training data quality and quantity, potentially using transfer learning.
  • Enhancing code efficiency, particularly in feature extraction.
  • Exploring alternative, automatic representations of the tree search space (e.g., graph neural networks).
  • Investigating different reward functions and action definitions (e.g., nearest-neighbor interchange, tree bisection and regrafting).
  • Examining other RL algorithm variants.

Summary updated

Abstract

We propose a reinforcement-learning algorithm to tackle the challenge of reconstructing phylogenetic trees. The search for the tree that best describes the data is algorithmically challenging, thus all current algorithms for phylogeny reconstruction use various heuristics to make it feasible. In this study, we demonstrate that reinforcement learning can be used to learn an optimal search strategy, thus providing a novel paradigm for predicting the maximum-likelihood tree. Our proposed method does not require likelihood calculation with every step, nor is it limited to greedy uphill moves in the likelihood space. We demonstrate the use of the developed deep-Q-learning agent on a set of unseen empirical data, namely, on unseen environments defined by nucleotide alignments of up to 20 sequences. Our results show that the likelihood scores of the inferred phylogenies are similar to those obtained from widely-used software. It thus establishes a proof-of-concept that it is beneficial to optimize a sequence of moves in the search-space, rather than optimizing the progress made in every single move only. This suggests that a reinforcement-learning based method provides a promising direction for phylogenetic reconstruction.
BibTeX
@misc{azouri2023tree,
  author = {Dana Azouri and Oz Granit and Michael Alburquerque and Yishay Mansour and Tal Pupko and Itay Mayrose},
  title = {{The tree reconstruction game: phylogenetic reconstruction using reinforcement learning}},
  year = {2023},
  eprint = {2303.06695},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2303.06695},
}
Figure