A Hybrid Algorithm Based on Artificial Immune System and Hidden Markov Model for Multiple Sequence Alignment

摘要

Multiple sequence alignment (MSA) has become an essential tool in the analysis of biologic sequences. In this paper, an artificial immune system (AIS) is proposed to train hidden Markov models (HMMs).Further, an integration algorithm based on the HMM and AIS for the MSA is constructed and a decoding algorithm based on Viterbi algorithm is also proposed. The approach is tested on a set of standard instances taken from the benchmark alignment database,BAliBASE. Numerical results are compared with those obtained by using the Baum-Welch training algorithm. The results show that the proposed algorithm not only improves the alignment abilities,but also reduces the time cost.