ProbPFP: a multiple sequence alignment algorithm combining hidden Markov model optimized by particle swarm optimization with partition function

Qing Zhan, Nan Wang, Shuilin Jin, Renjie Tan, Qinghua Jiang, Yadong WangBMC Bioinformatics 2019 · OpenReview

TL;DR

This paper introduces ProbPFP, a novel algorithm for multiple sequence alignment (MSA) that significantly improves accuracy by combining a Hidden Markov Model (HMM) optimized with Particle Swarm Optimization (PSO) and a partition function approach. ProbPFP achieves state-of-the-art or near state-of-the-art performance on benchmark datasets and demonstrates its utility in phylogenetic tree reconstruction.

What Problem Does This Paper Address?

Multiple Sequence Alignment (MSA) is a fundamental task in bioinformatics, crucial for tasks like protein structure prediction and phylogenetic inference. Accurately aligning sequences is challenging, especially for divergent ones. Traditional MSA methods often rely on pairwise alignment substitution scores. While Hidden Markov Models (HMMs) and partition function methods have individually shown promise in improving alignment accuracy by providing more adaptive scores (posterior probabilities), their combined potential, particularly with an optimized HMM, had been largely unexplored. This paper aims to bridge this gap by proposing an integrated approach that leverages the strengths of both optimized HMMs and partition functions.

Methods

The core of ProbPFP lies in its novel integration strategy. The process begins with optimizing the parameters of a pair-Hidden Markov Model (HMM) using Particle Swarm Optimization (PSO). Specifically, PSO is employed to tune gap open penalties, gap extend penalties, and initial distribution parameters. The fitness function for PSO is the standard sum-of-pairs (SoP) score, aiming to maximize alignment quality.

Once the HMM parameters are optimized, the HMM is used to calculate posterior probabilities for residue alignments. Concurrently, a separate partition function method is used to compute its own set of posterior probabilities. ProbPFP then combines these two sets of posterior probabilities to derive an integrated substitution score. This integrated score is subsequently used in a progressive alignment framework.

The progressive alignment process involves:

  1. Pairwise Alignment: Using the integrated substitution scores to align pairs of sequences.
  2. Distance Matrix Computation: Constructing a distance matrix based on the pairwise alignment scores.
  3. Guide Tree Construction: Building a guide tree (using UPGMA) from the distance matrix to dictate the order of alignment.
  4. Probabilistic Consistency Transformation: Applying a transformation to re-estimate probabilities considering other sequences' effects.
  5. Profile-Profile Alignment: Progressively aligning profiles (sequences or alignments) using dynamic programming with scores derived from the mean of posterior probabilities.
  6. Iterative Refinement: A final step of iterative refinement is performed.

Datasets

The paper evaluates ProbPFP using three well-established MSA benchmark datasets:

  • OXBench 1.3: Used for evaluation.
  • BAliBASE 3: Used for evaluation.
  • SABmark 1.65: Used for evaluation.

The authors note that for BAliBASE 3 and SABmark 1.65, specific subsets (RV11, RV12, Twilight Zone, and Superfamily) were used, which are consistent with previous studies. The paper also uses six protein families from the TreeFam database for phylogenetic tree reconstruction experiments.

Key Insights and Ideas

  • Synergistic Power of Integration: The most significant insight is that combining an optimized HMM (via PSO) with a partition function approach yields better alignment accuracy than either method alone. This suggests that these two probabilistic frameworks capture complementary aspects of sequence relationships.
  • PSO as an Effective Optimizer for HMMs: The study demonstrates that PSO is a viable and effective method for optimizing HMM parameters in the context of MSA, leading to improved alignment quality.
  • Partition Function's Strength in Divergent Regions: The paper suggests that the partition function method might be particularly adept at identifying highly similar regions, while the combined approach (ProbPFP) excels in handling more divergent families.
  • Impact on Downstream Analysis: The improved alignment quality directly translates to more accurate phylogenetic tree reconstructions, highlighting the practical utility of ProbPFP beyond just sequence alignment.

Key Results

  • Benchmark Performance: ProbPFP achieved the highest mean Total Column (TC) and Sum-of-Pairs (SP) scores on the OXBench and SABmark datasets.
  • BAliBASE Performance: On the BAliBASE dataset, ProbPFP achieved the second-highest mean TC and SP scores, very close to the top performer (Probalign). The authors attribute this to BAliBASE's bias towards globally related protein families, where the partition function alone might have a slight edge.
  • Phylogenetic Tree Reconstruction: When used to reconstruct phylogenetic trees for six protein families from TreeFam, ProbPFP's alignments resulted in trees that were closer to the reference trees in 5 out of 6 tests compared to four other leading aligners.
  • Parameter Optimization: Experiments showed that 10 particles and 30 iterations were sufficient for PSO optimization, balancing performance gains with computational cost.

Limitations and Future Work

  • BAliBASE Bias: The authors acknowledge that the BAliBASE dataset's bias towards globally related protein families might explain why Probalign (using only partition function) performed exceptionally well, and the combined approach didn't achieve the absolute top score on this specific dataset.
  • Computational Cost: While not explicitly detailed as a limitation, the integration of PSO optimization and partition function calculations likely increases the computational cost compared to simpler MSA methods.
  • Future Work: The paper implicitly suggests that further exploration of different optimization algorithms for HMMs and variations in combining probabilistic scores could lead to even greater improvements in MSA accuracy. The success in phylogenetic tree reconstruction also opens avenues for applying ProbPFP in broader evolutionary biology studies.

Summary updated

Abstract

Background During procedures for conducting multiple sequence alignment, that is so essential to use the substitution score of pairwise alignment. To compute adaptive scores for alignment, researchers usually use Hidden Markov Model or probabilistic consistency methods such as partition function. Recent studies show that optimizing the parameters for hidden Markov model, as well as integrating hidden Markov model with partition function can raise the accuracy of alignment. The combination of partition function and optimized HMM, which could further improve the alignment’s accuracy, however, was ignored by these researches. Results A novel algorithm for MSA called ProbPFP is presented in this paper. It intergrate optimized HMM by particle swarm with partition function. The algorithm of PSO was applied to optimize HMM’s parameters. After that, the posterior probability obtained by the HMM was combined with the one obtained by partition function, and thus to calculate an integrated substitution score for alignment. In order to evaluate the effectiveness of ProbPFP, we compared it with 13 outstanding or classic MSA methods. The results demonstrate that the alignments obtained by ProbPFP got the maximum mean TC scores and mean SP scores on these two benchmark datasets: SABmark and OXBench, and it got the second highest mean TC scores and mean SP scores on the benchmark dataset BAliBASE. ProbPFP is also compared with 4 other outstanding methods, by reconstructing the phylogenetic trees for six protein families extracted from the database TreeFam, based on the alignments obtained by these 5 methods. The result indicates that the reference trees are closer to the phylogenetic trees reconstructed from the alignments obtained by ProbPFP than the other methods. Conclusions We propose a new multiple sequence alignment method combining optimized HMM and partition function in this paper. The performance validates this method could make a great improvement of the alignment’s accuracy.
BibTeX
@article{zhan2019probpfp,
  author = {Qing Zhan and Nan Wang and Shuilin Jin and Renjie Tan and Qinghua Jiang and Yadong Wang},
  title = {{ProbPFP: a multiple sequence alignment algorithm combining hidden Markov model optimized by particle swarm optimization with partition function}},
  journal = {BMC Bioinformatics},
  year = {2019},
  url = {https://openreview.net/forum?id=D37abzfbY5z},
}
Figure