Skip to main content

A Novel Optimization of Profile HMM by a Hybrid Genetic Algorithm

  • Conference paper
Computational Intelligence and Bioinspired Systems (IWANN 2005)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3512))

Included in the following conference series:

  • 2586 Accesses

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Rabiner, L.R.: Aturorial on hidden Markov models and selected applications in speech recognition. Proc. IEEE 77, 257–286 (1989)

    Article  Google Scholar 

  2. 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)

    Article  Google Scholar 

  3. 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)

    Article  Google Scholar 

  4. 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)

    Google Scholar 

  5. 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)

    Article  Google Scholar 

  6. 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)

    Google Scholar 

  7. 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)

    Book  MATH  Google Scholar 

  8. 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)

    Google Scholar 

  9. Thompson, J.D., Plewniak, F., Poch, O.: A comprehensive comparison of multiple sequence alignment programs. Nucleic Acids Research 27(13), 2682–2690 (1999)

    Article  Google Scholar 

  10. 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)

    Article  Google Scholar 

  11. Thompson, J.D., Plewniak, F., Poch, O.: BAliBASE: a benchmark alignment database for the evaluation of multiple alignment programs. Bioinformatics 15, 87–88 (1999)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints 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)

Publish with us

Policies and ethics