Constructing Ancestral Recombination Graphs through Reinforcement Learning

多年来，已经提出了许多方法来构建祖先重组图（ARGs），这些图用于表示个体之间的遗传关系。其中许多方法依赖于最可能的图形在最短图形之间的假设。在本文中，我们提出了一种新的构建短ARGs的方法：强化学习（RL）。我们利用了在一组基因序列之间找到最短路径和它们的最近公共祖先之间找到最短路径之间的相似之处，并且发现这是一个经典的强化学习问题，即在迷宫的入口和出口之间找到最短路径。在迷宫问题中，学习者被称为代理，必须学习要采取的方向，以尽快逃脱，而在我们的问题中，代理必须学习在合并、突变和重组之间采取的行动，以尽快到达最近公共祖先。我们的结果表明，强化学习可以用于构建ARGs，其长度与优化构建短ARGs的启发式算法构建的ARGs一样短，有时甚至更短。此外，我们的方法允许为给定样本构建短ARGs的分布，并且可以将学习推广到在学习过程中未使用的新样本。

本文旨在提出一种新的方法，使用强化学习（RL）构建祖先重组图（ARGs），以表示个体之间的遗传关系。论文试图解决的问题是如何使用RL构建最短的ARGs。

本文提出使用强化学习算法构建ARGs，将基因序列之间的最短路径问题转化为经典的RL问题，即迷宫问题。通过学习在共同祖先、突变和重组之间采取的行动，以尽快到达最近的共同祖先。与目前优化构建最短ARGs的启发式算法相比，本文提出的方法可以构建出与之相当甚至更短的ARGs。

本文的实验结果表明，使用RL算法构建ARGs可以得到与启发式算法相当甚至更短的ARGs。此外，该方法还可以构建给定样本的短ARGs分布，并且可以将学习推广到未在学习过程中使用的新样本。本文的代码已经开源。

最近的研究包括使用其他方法构建ARGs，如基于贝叶斯网络的方法和最大似然方法。相关论文包括："Efficient inference of recombination hot regions in bacterial genomes using a Bayesian change-point model" 和 "Maximum likelihood inference of reticulate evolutionary histories"。