ProbPFP: a multiple sequence alignment algorithm combining hidden Markov model optimized by particle swarm...

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Multiple sequence alignment (MSA) is crucial for biological sequence analysis.
• Traditional methods use pairwise alignment substitution scores, often employing Hidden Markov Models (HMM) or partition functions.
• Optimizing HMM parameters and integrating HMM with partition functions can enhance MSA accuracy, but this combination has been underexplored.

Purpose of the Study:

• To develop a novel multiple sequence alignment (MSA) algorithm that combines an optimized Hidden Markov Model (HMM) with the partition function.
• To improve the accuracy of MSA by integrating posterior probabilities from both HMM and partition function for a more robust substitution score.

Main Methods:

• Developed ProbPFP, a novel MSA algorithm integrating particle swarm optimization (PSO) for HMM parameter tuning.
• Combined posterior probabilities from the optimized HMM and the partition function to compute an integrated substitution score.
• Evaluated ProbPFP against 13 established MSA methods on SABmark, OXBench, and BAliBASE datasets.

Main Results:

• ProbPFP achieved the highest mean TC and SP scores on SABmark and OXBench datasets.
• It demonstrated the second-highest mean TC and SP scores on the BAliBASE dataset.
• Phylogenetic trees reconstructed using ProbPFP alignments were closer to reference trees compared to other methods.

Conclusions:

• The proposed ProbPFP method, combining an optimized HMM and partition function, significantly improves multiple sequence alignment accuracy.
• This integrated approach offers a more accurate and reliable method for sequence alignment and downstream phylogenetic analysis.