Multiple Sequence Alignment with Hidden Markov Models Learned by Random Drift Particle Swarm Optimization.

Area of Science:

• Bioinformatics
• Computational Biology
• Machine Learning

Background:

• Multiple Sequence Alignment (MSA) is a critical yet computationally challenging problem (NP-complete) in bioinformatics.
• Hidden Markov Models (HMMs) are effective for MSA, but learning them is difficult.
• Meta-heuristic methods, like Particle Swarm Optimization (PSO), are used for HMM learning.

Purpose of the Study:

• Introduce a novel variant of PSO, the Random Drift Particle Swarm Optimization (RDPSO) algorithm.
• Enhance the global search capability of PSO for HMM learning in MSA.
• Propose an improved algorithm, RDPSO with Diversity-Guided Search (RDPSO-DGS), by incorporating diversity control.

Main Methods:

• Developed the RDPSO algorithm inspired by the free electron model in physics.
• Integrated a diversity control mechanism to create RDPSO-DGS.
• Evaluated algorithm performance on two benchmark datasets for HMM learning in MSA.

Main Results:

• RDPSO and RDPSO-DGS significantly improve HMM learning for MSA.
• The proposed algorithms generate better alignments than traditional methods like Baum-Welch and other PSO variants.
• Comparative analysis shows RDPSO and RDPSO-DGS outperform established MSA tools like ClustalW and MAFFT.

Conclusions:

• RDPSO and RDPSO-DGS offer superior performance for HMM-based MSA.
• The novel algorithms provide a more effective approach to solving the challenging MSA problem.
• These advancements contribute to more accurate biological sequence analysis.