Abstract
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.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Rabiner, L.R.: Aturorial on hidden Markov models and selected applications in speech recognition. Proc. IEEE 77, 257–286 (1989)
Krogh, A., Brown, M., Mian, I.S., Sjolander, K., Haussler, D.: Hidden Markov models in computational biology: Applications to protein modeling. Journal of Molecular Biology 235, 1501–1531 (1994)
Baldi, P., Chauvin, Y., Hunkapiler, T., McClure, M.A.: Hidden Markov modes of biological primary sequence information. Proc. Natl. Acad. Sci. USA 91, 1059–1063 (1994)
Eddy, S.: Multiple alignment using hidden Markov models. In: Proc. Int. Conf. on Intelligent Systems for Molecular Biology, pp. 114–120. AAAI/MIT Press, Cambridge (1995)
Kwong, S., Chau, C.W.: Analysis of parallel genetic algorithms on HMM based speech recognition system. IEEE Transactions on Consumer Electronics 43, 1229–1233 (1997)
Thomsen, R.: Evolving the Topology of Hidden Markov Models using Evolutionary Algorithms. In: Proceedings of the Seventh International Conference on Parallel Problem Solving from Nature - PPSN VII, pp. 861–870 (2002)
Durbin, R., Eddy, S.R., Krogh, A., Mitchison, G.J.: Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, Cambridge (1998)
Brown, M.P., Hughey, R., Krogh, A., Mian, I.S., Sjölander, K., Haussler, D.: Using Dirichlet mixture priors to derive hidden Markov models for protein families. In: Proc. of First Int. Conf. on Intelligent Systems for Molecular Biology, pp. 47–55. AAAI/MIT Press, Menlo Park (1993)
Thompson, J.D., Plewniak, F., Poch, O.: A comprehensive comparison of multiple sequence alignment programs. Nucleic Acids Research 27(13), 2682–2690 (1999)
Bashford, D., Chothia, C., Lesk, A.M.: Determinants of a protein fold: unique features of the globin amino axid sequence. Journal of Molecular Biology 196, 199–216 (1987)
Thompson, J.D., Plewniak, F., Poch, O.: BAliBASE: a benchmark alignment database for the evaluation of multiple alignment programs. Bioinformatics 15, 87–88 (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Liu, L., Huo, H., Wang, B. (2005). A Novel Optimization of Profile HMM by a Hybrid Genetic Algorithm. In: Cabestany, J., Prieto, A., Sandoval, F. (eds) Computational Intelligence and Bioinspired Systems. IWANN 2005. Lecture Notes in Computer Science, vol 3512. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11494669_90
Download citation
DOI: https://doi.org/10.1007/11494669_90
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26208-4
Online ISBN: 978-3-540-32106-4
eBook Packages: Computer ScienceComputer Science (R0)