Exploring reinforcement learning techniques in muliple sequence alignment
Ramchalam Kinattinkara Ramakrishnan · 2018
Biological sequence alignment is a task that is critical for identifying regions of similarity that may be a consequence of functional, structural, or evolutionary relationships between DNA, RNA or protein sequences. The Multiple Sequence Alignment (MSA) problem isan NP-hard problem. Consequently, practical approaches to the problem are all heuristics-based. However, these heuristics are imperfect and there is a need to change our approach to the MSA problem in order to deal with these imperfections. Reinforcement Learning (RL) techniques are currently very popular and have been used to solve tasks similar to the MSA problem, but have not yet been used by itself to tackle this specific problem. In this thesis, we describe a method to solve the MSA problem using RL. We develop an algorithm basedon two popular RL frameworks: Deep Q - Network (DQN) and Asynchronous Advantage Actor Critic (A3C). An RL game environment was first created and the models were then trained to align several short sequences. Our approach is a novel RL method implemented without a known goal state, so we trained the algorithm using a heuristic-based estimation of the goal state. We further demonstrated that models trained on short sequences can be used to align longer sequences. Overall, DQN and A3C both provided good results, but the A3C model converged much faster than DQN and was used for most of the analysis. For short sequences, the alignments produced by our model are competitive with those produced by state-of-the-art algorithms such as MAFFT. Our RL approach, combined with certain heuristics we developed, has the potential to generalize to larger alignments, making it computationally practical.%%%%L'alignement de sequences biologiques est une tâche essentielle pour identifier les regions de similarite qui peuvent etre une consequence de relations fonctionnelles, structurelles ou evolutives entre des sequences d'ADN, d'ARN ou de proteines. Le probleme d'alignement de sequences multiples (ASM) est un probleme NP-difficile. En consequence, les seules approches praticables sont celles basees sur des heuristiques. Cependant, ces heuristiques sont imparfaites et il est necessaire de changer notre approche du probleme MSA pour faire face a ces imperfections. Les techniques d'apprentissage par renforcement (AR) sont actuellement tres populaires et ont ete utilisees pour resoudre des tâches similaires au probleme MSA. Dans cette these, nous decrivons une methode pour resoudre le probleme MSA en utilisant AR. Nous developpons un algorithme base sur deux familles d'approches de AR populaires: Deep Q - Network (DQN) et Asynchronous Advantage Actor Critic (A3C). Un environnement de jeu AR a d'abord ete cree et les modeles ont ensuite ete formes pour aligner plusieurs sequences courtes. Notre approche est une nouvelle methode AR implementee sans etat de but connu, donc nous avons forme l'algorithme en utilisant une estimation heuristique de l'etat du but. Nous avons egalement demontre que des modeles formes sur des sequences courtes peuvent etre…