A Novel Optimization of Profile HMM by a Hybrid Genetic Algorithm

摘要

Profile Hidden Markov Models (Profile HMM) are well suited to modelling multiple alignment and are widely used in molecular biology. Usually, heuristic algorithms such as Baum-Welch are used to estimate the model parameters. However, Baum-Welch has a tendency to stagnate on local optima. A more involved approach is to use some form of stochastic search algorithm that 'bumps' Baum-Welch off from local maxima. In this paper, a hybrid genetic algorithm is presented for training profile HMM (hybrid GA-HMM training) and producing multiple sequence alignment from groups of unaligned protein sequences. The quality of the alignments produced by hybrid GA-HMM training is compared to that by the other Profile HMM training methods. The experimental results prove very competitive with and even better than the other tested profile HMM training methods. Analysis of the behavior of the algorithm sheds light on possible improvement.