Multiple Sequence Alignment based on deep Q network with negative feedback policy. (December 2022)

• Record Type: Journal Article
• Authors: Zhang, Yongqing; Zhang, Qiang; Liu, Yuhang; Lin, Meng; Ding, Chunli
• Is Part Of: Computational biology and chemistry. Volume 101(2022)
• Publication Date: 2022-12
• Subjects: Multiple Sequence Alignment -- Reinforcement learning -- Deep Q Network -- Negative Feedback Policy; Chemistry -- Data processing -- Periodicals; Biology -- Data processing -- Periodicals; Biochemistry -- Data processing; Biology -- Data processing; Molecular biology -- Data processing; Periodicals; Electronic journals; 542.85
• DOI: 10.1016/j.compbiolchem.2022.107780
• Languages: English
• ISSNs: 1476-9271

Abstract

Abstract: Background and objective: Multiple Sequence Alignment (MSA) is an essential procedure in the sequence analysis of biological macromolecules, which can obtain the potential information between multiple sequences, such as functional and structural information. At present, the main challenge of MSA is an NP-complete problem; the algorithm's complexity increases exponentially with the increase of the number of sequences. Some methods are constantly approaching the results towards the optimal ratio and easy to fall into the local optimization, so the accuracy of these methods is still greatly improved. Methods: Here, we propose a new method based on deep reinforcement learning (DRL) for MSA. Specifically, inspired by biofeedback, we leverage the Negative Feedback Policy (NFP) to enhance the performance and accelerate the convergence of the model. Furthermore, we developed a new profile algorithm to compute the sequence from aligned sequences for the next profile-sequence alignment to facilitate the experiment. Results: Compared to six state-of-the-art methods, three different genetic algorithms, Q-learning, ClustalW, and MAFFT, our method exceeds these methods in terms of Sum-of-Pairs (SP) score and Column Score(CS) scores on most datasets in which the increased range of SP score is from 2 to 1056. Conclusion: Extensive experiments based on several datasets validate the effectiveness of our method for achieving a better alignment, and the results have higher accuracy and stability. The source code can be found at https://github.com/MrZhang176/DNPMSA . Graphical abstract: Highlights: A deep reinforcement learning is proposed to improve the scale of the sequence to a certain extent in MSA. A new profile algorithm is proposed to improve the accuracy and stability of the alignment. The negative feedback policy is proposed to improve the method's stability.