Multiple Sequence Alignment based on deep Q network with negative feedback policy.

Area of Science:

• Computational Biology
• Bioinformatics
• Machine Learning

Background:

• Multiple Sequence Alignment (MSA) is crucial for analyzing biological macromolecules, revealing functional and structural insights.
• MSA is an NP-complete problem, posing computational challenges due to exponential complexity with increasing sequence numbers.
• Existing MSA methods often struggle with local optimization and require accuracy improvements.

Purpose of the Study:

• To develop a novel deep reinforcement learning (DRL) method for enhanced Multiple Sequence Alignment (MSA).
• To improve the accuracy and stability of MSA results.
• To address the computational complexity and local optimization issues in current MSA algorithms.

Main Methods:

• A new method based on deep reinforcement learning (DRL) was proposed for MSA.
• The Negative Feedback Policy (NFP) was leveraged, inspired by biofeedback, to boost performance and convergence.
• A novel profile algorithm was developed for computing sequences in profile-sequence alignment.

Main Results:

• The proposed DRL method demonstrated superior performance compared to six state-of-the-art methods, including genetic algorithms, Q-learning, ClustalW, and MAFFT.
• Significant improvements were observed in Sum-of-Pairs (SP) and Column Score (CS) metrics, with SP score increases ranging from 2 to 1056.
• The method achieved higher accuracy and stability across various datasets.

Conclusions:

• Extensive experiments validated the effectiveness of the proposed DRL-based MSA method.
• The method consistently delivers better alignment accuracy and stability.
• Source code is publicly available for reproducibility and further research.