ProbPFP: A Multiple Sequence Alignment Algorithm Combining Partition Function and Hidden Markov Model with Particle Swarm Optimization

The substitution score for pairwise sequence alignment is essential in conducting multiple sequence alignment (MSA). The Hidden Markov Model (HMM) and partition function are two methods that are widely chosen for this purpose. Recent studies showed that the accuracy of alignment could be improved by combining the partition function and HMM algorithms or optimizing the parameters of HMM. However, the combination of optimized HMM and partition function, which could greatly improve the accuracy of alignment, was ignored in these studies. This study presents a new MSA algorithm known as ProbPFP that combines the partition function and the HMM optimized by particle swarm optimization (PSO). In this work, the parameters of HMM were first optimized by the PSO algorithm, and the posterior probabilities derived from the HMM were subsequently combined with the results derived from the partition function to compute a comprehensive substitution score for alignment. To assess the effectiveness, ProbPFP was compared with 13 leading aligners, namely, Probalign, CONTRAlign, ProbCons, MUSCLE, MAFFT, COBALT, T-Coffee, ClustalΩ, ClustalW, DIALIGN, PicXAA, Align-m and KALIGN2. The results showed that ProbPFP achieved the highest average sum-of-pairs (SP) scores (0.9015, 0.5984) and average total column (TC) scores (0.8170, 0.3956) on two benchmark sets OXBench and SABmark, as well as the second highest average SP score (0.8250) and average TC score (0.6703) on the benchmark set BAliBASE. We also used the alignments generated by ProbPFP and 4 other leading aligners to rebuild the phylogenetic trees of 6 families from the TreeFam database. The result suggests that the trees from the alignments generated by ProbPFP are closer to the reference trees.