The tree reconstruction game: phylogenetic reconstruction using
reinforcement learning
- URL: http://arxiv.org/abs/2303.06695v1
- Date: Sun, 12 Mar 2023 16:19:06 GMT
- Title: The tree reconstruction game: phylogenetic reconstruction using
reinforcement learning
- Authors: Dana Azouri, Oz Granit, Michael Alburquerque, Yishay Mansour, Tal
Pupko and Itay Mayrose
- Abstract summary: We propose a reinforcement-learning algorithm to tackle the challenge of reconstructing phylogenetic trees.
In this study, we demonstrate that reinforcement learning can be used to learn an optimal search strategy.
Our results show that the likelihood scores of the inferred phylogenies are similar to those obtained from widely-used software.
- Score: 30.114112337828875
- License: http://creativecommons.org/licenses/by/4.0/
- 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.
Related papers
- Tree Search-Based Evolutionary Bandits for Protein Sequence Optimization [44.356888079704156]
Protein engineering is a daunting task due to the vast sequence space of any given protein.
Protein engineering is typically conducted through an iterative process of adding mutations to the wild-type or lead sequences.
We propose a tree search-based bandit learning method, which expands a tree starting from the initial sequence with the guidance of a bandit machine learning model.
arXiv Detail & Related papers (2024-01-08T06:33:27Z) - Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
In this paper we offer a new perspective on the well established agglomerative clustering algorithm, focusing on recovery of hierarchical structure.
We recommend a simple variant of the standard algorithm, in which clusters are merged by maximum average dot product and not, for example, by minimum distance or within-cluster variance.
We demonstrate that the tree output by this algorithm provides a bona fide estimate of generative hierarchical structure in data, under a generic probabilistic graphical model.
arXiv Detail & Related papers (2023-05-24T11:05:12Z) - A Novel Memetic Strategy for Optimized Learning of Classification Trees [0.0]
We propose a novel evolutionary algorithm for the induction of classification trees that exploits a memetic approach that is able to handle datasets with thousands of points.
Our procedure combines the exploration of the feasible space of solutions with local searches to obtain structures with generalization capabilities that are competitive with the state-of-the-art methods.
arXiv Detail & Related papers (2023-05-13T16:29:10Z) - Constructing Phylogenetic Networks via Cherry Picking and Machine
Learning [0.1045050906735615]
Existing methods are computationally expensive and can either handle only small numbers of phylogenetic trees or are limited to severely restricted classes of networks.
We apply the recently-introduced theoretical framework of cherry picking to design a class of efficients that are guaranteed to produce a network containing each of the input trees.
We also propose simple and fast randomiseds that prove to be very effective when run multiple times.
arXiv Detail & Related papers (2023-03-31T15:04:42Z) - Reinforcement Learning for Branch-and-Bound Optimisation using
Retrospective Trajectories [72.15369769265398]
Machine learning has emerged as a promising paradigm for branching.
We propose retro branching; a simple yet effective approach to RL for branching.
We outperform the current state-of-the-art RL branching algorithm by 3-5x and come within 20% of the best IL method's performance on MILPs with 500 constraints and 1000 variables.
arXiv Detail & Related papers (2022-05-28T06:08:07Z) - A Hybrid Framework for Sequential Data Prediction with End-to-End
Optimization [0.0]
We investigate nonlinear prediction in an online setting and introduce a hybrid model that effectively mitigates hand-designed features and manual model selection issues.
We employ a recurrent neural network (LSTM) for adaptive feature extraction from sequential data and a gradient boosting machinery (soft GBDT) for effective supervised regression.
We demonstrate the learning behavior of our algorithm on synthetic data and the significant performance improvements over the conventional methods over various real life datasets.
arXiv Detail & Related papers (2022-03-25T17:13:08Z) - Improving RNA Secondary Structure Design using Deep Reinforcement
Learning [69.63971634605797]
We propose a new benchmark of applying reinforcement learning to RNA sequence design, in which the objective function is defined to be the free energy in the sequence's secondary structure.
We show results of the ablation analysis that we do for these algorithms, as well as graphs indicating the algorithm's performance across batches.
arXiv Detail & Related papers (2021-11-05T02:54:06Z) - Provable Hierarchy-Based Meta-Reinforcement Learning [50.17896588738377]
We analyze HRL in the meta-RL setting, where learner learns latent hierarchical structure during meta-training for use in a downstream task.
We provide "diversity conditions" which, together with a tractable optimism-based algorithm, guarantee sample-efficient recovery of this natural hierarchy.
Our bounds incorporate common notions in HRL literature such as temporal and state/action abstractions, suggesting that our setting and analysis capture important features of HRL in practice.
arXiv Detail & Related papers (2021-10-18T17:56:02Z) - On the Exploitation of Neuroevolutionary Information: Analyzing the Past
for a More Efficient Future [60.99717891994599]
We propose an approach that extracts information from neuroevolutionary runs, and use it to build a metamodel.
We inspect the best structures found during neuroevolutionary searches of generative adversarial networks with varying characteristics.
arXiv Detail & Related papers (2021-05-26T20:55:29Z) - MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
We present a novel algorithm for learning optimal classification trees based on dynamic programming and search.
Our approach uses only a fraction of the time required by the state-of-the-art and can handle datasets with tens of thousands of instances.
arXiv Detail & Related papers (2020-07-24T17:06:55Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.