A Multiple Sequence Alignment Algorithm Based on a Hidden Markov Model and Immune Particle Swarm Optimization

Multiple sequence alignment (MSA) is a fundamental and challenging problem in the analysis of biologic sequences. In this paper, an immune particle swarm optimization (IPSO) is presented, which is based on the models of the vaccination and the receptor editing in immune systems. The proposed algorithm is used to train hidden Markov models (HMM). Furthermore, an integration algorithm based on the HMM and IPSO for the MSA is constructed. The approach is examined by using a set of standard instances taken from the benchmark alignment database, BAliBASE. Numerical simulation results are compared with those obtained by using the Baum-Welch training algorithm. The result of the comparisons show that the proposed algorithm not only improves the alignment abilities, but also reduces the time cost.