Multiple Sequence Alignment with Hidden Markov Models Learned by Random Drift Particle Swarm Optimization

Jun Sun, Vasile Palade, Xiaojun Wu, Wei Fang

Research output: Contribution to journalArticlepeer-review

20 Citations (Scopus)


Hidden Markov Models (HMMs) are powerful tools for multiple sequence alignment (MSA), which is known to be an NPcomplete and important problem in bioinformatics. Learning HMMs is a difficult task, and many meta-heuristic methods, including particle swarm optimization (PSO), have been used for that. In this paper, a new variant of PSO, called the random drift particle swarm
optimization (RDPSO) algorithm, is proposed to be used for HMM learning tasks in MSA problems. The proposed RDPSO algorithm, inspired by the free electron model in metal conductors in an external electric field, employs a novel set of evolution equations that can enhance the global search ability of the algorithm. Moreover, in order to further enhance the algorithmic performance of the RDPSO, we incorporate a diversity control method into the algorithm and, thus, propose an RDPSO with diversity-guided search (RDPSODGS). The performances of the RDPSO, RDPSO-DGS and other algorithms are tested and compared by learning HMMs for MSA on two well-known benchmark data sets. The experimental results show that the HMMs learned by the RDPSO and RDPSO-DGS are able to generate better alignments for the benchmark data sets than other most commonly used HMM learning methods, such as the Baum-Welch and other PSO algorithms. The performance comparison with well-known MSA programs, such as ClustalW and MAFFT, also shows that the proposed methods have advantages in multiple sequence alignment.
Original languageEnglish
Pages (from-to)243-257
JournalIEEE/ACM Transactions on Computational Biology and Bioinformatics
Issue number1
Publication statusPublished - Jan 2014

Bibliographical note

This article is not yet available in the repository.

Natural Science Foundation Program for New Century RS-NSFC International Exchange Program Natural Science Foundation of Jiangsu Province, China Key grant Project of Chinese Ministry of Education


  • Hidden Markov Models, multiple sequence alignment, parameter learning, particle swarm optimization

Fingerprint Dive into the research topics of 'Multiple Sequence Alignment with Hidden Markov Models Learned by Random Drift Particle Swarm Optimization'. Together they form a unique fingerprint.

Cite this