Multiple Sequence Alignment Based On the Profile Hidden Markov Model

Abstract:

Multiple sequence alignment(MSA),known as NP-complete problem,is one of the basic problems in computational biology.At present Profile Hidden Markov Model(HMM) was widely used in multiple sequence alignment.This manuscript presented the quantum-behaved particle swarm optimization(QPSO) which was based on particle swarm optimization.The proposed algorithm was used to optimize the profile HMM.Furthermore,an integration algorithm based on the profile HMM and QPSO for the MSA was constructed.Then the approach was evaluated by a set of standard instances which are chosen from nucleotides sequences and the benchmark alignment database,name as BAliBASE.Finally our results are compared with other algorithms.The result shown that the proposed algorithm not only finds out the perfect profile HMM,but also obtains the optimal alignment of multiple sequence.