基于隐马尔可夫模型和免疫粒子群优化的多序列比对算法

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

序列的多重比对是生物序列分析研究中的一个重要内容·基于免疫系统的疫苗接种和受体编辑模型,结合粒子群优化方法提出了一种免疫粒子群优化算法,将该算法用于隐马尔可夫模型的学习过程,进而构建了一种基于隐马尔可夫模型和免疫粒子群优化的多序列比对算法·从BAliBASE比对数据库中选取了一些比对例子进行了模拟计算,并与Baum-Welch算法进行了比较·结果表明,所提出的方法不仅提高了比对的准确程度,而且缩减了比对所花费的时间·

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.