Solving multiple sequence alignment using deep reinforcement learning

Abstract

Multiple Sequence Alignment (MSA) is a fundamental task in Bioinformatics, essential for understanding evolutionary relationships, genetic adaptations, drug design, and other applications. In general, MSA is a Nondeterministic Polynomially complete problem with many heuristic solvers approaching over the years. Machine Learning (ML) can handle combinatorial optimization problems by learning models that generalize in various instances. Recent years have witnessed a surge of interest in applying Deep Reinforcement Learning (DRL) techniques for training agents to approach MSAs. In this work, we introduce IntellAlign, a novel methodology for aligning sequences using DRL for training and Natural Language Processing (NLP) approach. We build strong policies with only a few simulations, no previous knowledge, and self-play using the Gumbel AlphaZero algorithm. Our goal is maximizing a multi-objective reward based on well-known MSA quality metrics. We also propose attention-based networks for encoding MSAs. We contribute by achieving full flexibility of the sequence shape and by allowing the agent with a stop move to finish the alignment. We utilize the Glimpse-Pointer Network for pointing a series of positions sequentially to add a gap in the MSA. Finally, we utilize positional encodings for passing the sequence structural information to the network. Our algorithm is compared with three well-established aligners (Clustal Omega, MAFFT, and MUSCLE) on DNA MSAs. The results are promising, showing that IntellAlign outperforms MAFFT and MUSCLE tools. Moreover, it tends to score close to the Clustal Omega tool.