Constructing Ancestral Recombination Graphs through Reinforcement Learning

Raymond, Mélanie; Descary, Marie-Hélène; Beaulac, Cédric et Larribe, Fabrice (2025). « Constructing Ancestral Recombination Graphs through Reinforcement Learning ». Frontiers in Genetics - Computational Genomics, 16.

Fichier(s) associé(s) à ce document :

	PDF Télécharger (2MB)

Résumé

Introduction: Over the years, many approaches have been proposed to build ancestral recombination graphs (ARGs), graphs used to represent the genetic relationship between individuals. Among these methods, many rely on the assumption that the most likely graph is among those with the fewest recombination events. In this paper, we propose a new approach to build maximum parsimony ARGs: Reinforcement Learning (RL). Methods: We exploit the similarities between finding the shortest path between a set of genetic sequences and their most recent common ancestor and finding the shortest path between the entrance and exit of a maze, a classic RL problem. In the maze problem, the learner, called the agent, must learn the directions to take in order to escape as quickly as possible, whereas in our problem, the agent must learn the actions to take between coalescence, mutation, and recombination in order to reach the most recent common ancestor as quickly as possible. Results: Our results show that RL can be used to build ARGs with as few recombination events as those built with a heuristic algorithm optimized to build minimal ARGs, and sometimes even fewer. Moreover, our method allows to build a distribution of ARGs with few recombination events for a given sample, and can also generalize learning to new samples not used during the learning process. Discussion: RL is a promising and innovative approach to build ARGs. By learning to construct ARGs just from the data, our method differs from conventional methods that rely on heuristic rules or complex theoretical models.

Type:	Article de revue scientifique
Mots-clés ou Sujets:	genetic statistics, reinforcement learning, neural network, ensemble method, genealogy, ancestral recombination graph
Unité d'appartenance:	Faculté des sciences > Département de mathématiques
Déposé par:	Cédric Beaulac
Date de dépôt:	13 juin 2025 09:12
Dernière modification:	13 juin 2025 09:12
Adresse URL :	http://archipel.uqam.ca/id/eprint/18829

Modifier les métadonnées (propriétaire du document)

Statistiques