Constructing ancestral recombination graphs through reinforcement learning.

Area of Science:

• Computational Biology
• Genetics
• Machine Learning

Background:

• Ancestral Recombination Graphs (ARGs) are crucial for understanding genetic relationships.
• Existing methods for ARG construction often assume the most likely graph has the fewest recombination events.
• These methods frequently rely on heuristic rules or complex theoretical models.

Purpose of the Study:

• To introduce a novel approach for building maximum parsimony Ancestral Recombination Graphs (ARGs).
• To leverage Reinforcement Learning (RL) for constructing ARGs directly from genetic data.
• To compare the performance of RL-based ARG construction against existing heuristic algorithms.

Main Methods:

• The study frames ARG construction as a shortest path problem, analogous to a maze navigation task in Reinforcement Learning.
• An RL agent learns optimal actions (coalescence, mutation, recombination) to efficiently reach the most recent common ancestor.
• This approach exploits similarities between finding the shortest path in a maze and identifying the most parsimonious ARG.

Main Results:

• Reinforcement Learning (RL) successfully builds ARGs with a number of recombination events comparable to, and sometimes fewer than, optimized heuristic algorithms.
• The RL method generates a distribution of parsimonious ARGs for a given genetic sample.
• The approach demonstrates generalization capabilities, performing well on new datasets not encountered during training.

Conclusions:

• Reinforcement Learning presents a promising and innovative method for constructing Ancestral Recombination Graphs.
• This data-driven approach bypasses the need for predefined heuristic rules or intricate theoretical frameworks.
• RL offers a flexible and effective alternative for inferring complex genetic relationships represented by ARGs.