Reza Jafari - Department of Computer Science, Shahid Bahonar University of Kerman, Iran
Hamed Tabrizchi - Department of Computer Science, Shahid Bahonar University of Kerman, Iran
Marjan Kuchaki Rafsanjani - Department of Computer Science, Shahid Bahonar University of Kerman, Iran
Mohammad Masoud Javidi - Department of Computer Science, Shahid Bahonar University of Kerman, Iran

This article uses a distributed (multi-agent) deep Q- learning (DDQL) approach to solve the multiple sequence alignment (MSA) problem, an NP-complete problem. The MSA problem alludes to the Deoxyribonucleic acid (DNA), Ribonucleic acid (RNA), or protein initial sequence arrangement process to maximize their similarity regions. The problem is modeled by our method as a DDQL problem. In the distributed model, each agent is a deep Q -learning algorithm that attempts to reach local Q values. An ideal solution will be obtained by sending optimized local Q values to their supervisor, a blackboard mechanism, or a server. We used Long Short Term Memory networks due to the sequential character of the MSA problem and their ability to memorize long dependencies. They do the function estimator role in the approximation stage We also used the policy gradient and actor-critic algorithm to have a faster procedure in case of solving long sequences. Besides, the number of training episodes could be reduced by using a multi-agent system. Eight different real-world data sets undergo experimental evaluation. In each of the used data sets, our method performs better than other famous methods and tools like ClustalW, Multiple Alignment using Fast Fourier Transform (MAFFT), and different heuristic methods regarding scoring in solving the MSA problem.

Artificial Intelligence, Reinforcement learning, Bioinformatics, distributed deep Q-learning, Multiple Sequence Alignment.