Skip to main content
Springer Nature Link
Log in

The Block Hidden Markov Model for Biological Sequence Analysis

  • Conference paper
Knowledge-Based Intelligent Information and Engineering Systems (KES 2004)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 3213))

  • 801 Accesses

Abstract

The Hidden Markov Models (HMMs) are widely used for biological sequence analysis because of their ability to incorporate biological information in their structure. An automatic means of optimising the structure of HMMs would be highly desirable. To maintain biologically interpretable blocks inside the HMM, we used a Genetic Algorithm (GA) that has HMM blocks in its coding representation. We developed special genetics operations that maintain the useful HMM blocks. To prevent over-fitting a separate data set is used for comparing the performance of the HMMs to that used for the Baum-Welch training. The performance of this algorithm is applied to finding HMM structures for the promoter and coding region of C. jejuni. The GA-HMM was capable of finding a superior HMM to a hand-coded HMM designed for the same task which has been published in the literature.

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

Access this chapter

Log in via an institution

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. Durbin, R., Eddy, S., Krogh, A., Mitchison, G.: Biological sequence analysis. Cambridge University Press, Cambridge (1998)

    Book  MATH  Google Scholar 

  2. Petersen, L., Larsen, T.S., Ussery, D.W., On, S.L.W., Krogh, A.: Rpod promoters in Campylobacter jejuni exhibit a strong periodic signal instead of a -35 box. Journal of Molecular Biology 326(5), 1361–1372 (2003)

    Article  Google Scholar 

  3. Krogh, A., Larsson, B., von Heijne, G., Sonnhammer, E.: Predicting transmembrane protein topology with a Hidden Markov Model: Application to complete genomes. Journal of Molecular Biology 305(3), 567–580 (2003)

    Article  Google Scholar 

  4. Goldberg, D.E.: Genetic Algorithms in Search, Optimization & Machine Learning. Addison-Wesley, Reading, Mass (1989)

    MATH  Google Scholar 

  5. Yada, T., Ishikawa, M., Tanaka, H., Asai, K.: DNA Sequence Analysis Using Hidden Markov Model and Genetic Algorithm. Genome Informatics 5, 178–179 (1994)

    Google Scholar 

  6. Baker, J.E.: Reducing bias and inefficiency in the selection algorithm. In: Proceedings of the Second International Conference on Genetic Algorithms, Lawrence Erlbaum Associates (Hillsdale) (1987)

    Google Scholar 

  7. Prügel-Bennett, A., Shapiro, J.L.: An analysis of genetic algorithms using statistical mechanics. Physical Review Letters 72(9), 1305–1309 (1994)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. ISIS Group, ECS Department, University of Southampton, SO17 1BJ, United Kingdom

    Kyoung-Jae Won & Adam Prügel-Bennett

  2. Bioinformatics Centre, University of Copenhagen, DK-2100, Copenhagen, Denmark

    Anders Krogh

Authors
  1. Kyoung-Jae Won
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Adam Prügel-Bennett
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Anders Krogh
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. KES International, 2nd Floor, 145-157 St John Street, EC1V 4PY, London, United Kingdom

    Mircea Gh. Negoita

  2. Centre for SMART systems Engineering Research Centre, University of Brighton, BN2 4GJ, Moulsecoomb, Brighton, UK

    Robert J. Howlett

  3. School of Electrical and Information Engineering, Knowledge Based Intelligent Engineering Systems Centre, University of South Australia, 5095, Mawson Lakes, SA, Australia

    Lakhmi C. Jain

Rights and permissions

Reprints and permissions

Copyright information

© 2004 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Won, KJ., Prügel-Bennett, A., Krogh, A. (2004). The Block Hidden Markov Model for Biological Sequence Analysis. In: Negoita, M.G., Howlett, R.J., Jain, L.C. (eds) Knowledge-Based Intelligent Information and Engineering Systems. KES 2004. Lecture Notes in Computer Science(), vol 3213. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30132-5_13

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-30132-5_13

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-23318-3

  • Online ISBN: 978-3-540-30132-5

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation