A Parallel Multiobjective Metaheuristic for Multiple Sequence Alignment.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Multiple Sequence Alignment (MSA) is an NP-hard problem with exponential time complexity.
• Optimizing MSA simultaneously for accuracy and conservation presents a significant computational challenge.
• Existing metaheuristics for MSA often face scalability issues with increasing sequence numbers.

Purpose of the Study:

• To propose a parallel version of a hybrid multiobjective memetic metaheuristic for MSA.
• To address the multiobjective nature of MSA by optimizing both alignment accuracy and conservation.
• To enhance the efficiency and scalability of MSA for large datasets.

Main Methods:

• Development of a parallel hybrid multiobjective memetic metaheuristic algorithm for MSA.
• Evaluation of the parallel algorithm's performance on datasets with up to 1000 sequences.
• Comparative analysis against established parallel metaheuristics: MSAProbs, T-Coffee, Clustal Omega, and MAFFT.

Main Results:

• The proposed parallel aligner demonstrated superior alignment accuracy and conservation compared to MSAProbs, T-Coffee, Clustal Omega, and MAFFT.
• The parallel version achieved approximately 25 times speedup over the sequential version using 32 cores.
• An efficiency of around 80% was observed for the parallel implementation.

Conclusions:

• The novel parallel metaheuristic offers a significant improvement in both performance and accuracy for multiobjective MSA.
• This approach provides a scalable and efficient solution for analyzing large biological sequence datasets.
• The findings contribute to advancing computational methods in bioinformatics and genomics research.