Fast multiple sequence alignment via multi-armed bandits.

Area of Science:

• Computational Biology
• Bioinformatics
• Machine Learning

Background:

• Multiple sequence alignment is crucial for understanding protein evolution and function.
• Accurate alignment of large biological datasets is computationally intensive.
• Existing methods like UPP rely on computationally expensive hidden Markov model (HMM) scoring.

Purpose of the Study:

• To accelerate the sequence-to-HMM assignment step in multiple sequence alignment.
• To maintain alignment accuracy while significantly reducing computation time.
• To develop an adaptive approach for efficient score estimation.

Main Methods:

• Replacing precise HMM probability scores with efficiently estimated alternative scores.
• Utilizing a multi-armed bandit algorithm for adaptive score estimation.
• Applying the method to large datasets, focusing on long sequences.

Main Results:

• Achieved similar alignment accuracy compared to the established UPP software.
• Demonstrated a significant reduction in computation time.
• The speed-up is particularly notable for datasets containing long sequences.

Conclusions:

• Adaptive score estimation offers a computationally efficient alternative for multiple sequence alignment.
• The proposed method enhances the scalability of bioinformatics tools for large-scale sequence analysis.
• This approach can be broadly applied to accelerate other HMM-based computational biology tasks.