Hidden Markov Models In Genomic Analysis

Question

[didymos]

Hi All,
I would like to use Hidden Markov Models to investigate some genomic properties (DNA breaking points). Do you know any good literature and/or tutorials about how to implement HMM in python, R (Bioconductor)? (especially for sequence analysis) I would be grateful for any comments and suggestions.

Answer 1

[Gjain]

Hi,

This one explains HMM with examples:

• http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/main.html

and this article in nature explains it with a biological background:

• http://www.nature.com/nbt/journal/v22/n10/full/nbt1004-1315.html

Here is the R package for HMM

• http://cran.r-project.org/web/packages/HMM/HMM.pdf

hope this helps.

[Jonasr]

For a more detailed explanation you could also look at the following book: Durbin,R. et al. (1998) Biological sequence analysis Cambridge university press, Cambridge, UK. http://books.google.com/books/about/Biological_sequence_analysis.html?id=R5P2GlJvigQC

[Boboppie]

The nbt article is a good start, and Richard's book is definitely worth reading.

[Gjain]

oh yes ... that book is very good. thanks

Answer 2

[lh3]

For genomic data (at least for applications I am familiar with), you need very efficient implementations. The core should be really written in low-level languages such as C. Here are comments on a few existing implementations:

• BioPerl has an HMM implementation with the core written in C.

• The R package HMM sounds right, but it is written purely in R (one of the slowest, if not the slowest, scripting languages) without using matrix operations, and in a very inefficient way. Probably it is going to be >1000X, if not >10000X, slower than a proper C implementation.

• BioPython also has an HMM module, but written purely in Python apparently. Python is typically ~50-100X slower than C for such an application.

• If you do not want to implement HMM by yourself, you may consider Ewan Birney's dynamite. It is able to generate code for very complex HMMs. The famous GeneWise is built upon that.

Richard's book is the best as a tutorial.

[Hranjeev]

Richard's book? Pointers pls

[Jonasr]

'Richard's book' is the one I mentioned in the comments to Gjain's answer. Richard Durbin.

[Delinquentme]

Just thought the claims on speed here might be worth looking into:

http://www.ll.mit.edu/HPEC/agendas/proc03/pdfs/nehrbass.pdf

Answer 3

[Khader Shameer]

I would start with the wikipedia article on HMM, followed by articles that describe HMMs from perspective of application in biology (not as such genomic analysis )by Sean Eddy.

• Hidden Markov Models
• Profile hidden Markov models
• What is a hidden Markov model?

Regarding implementation of HMM for prediction genomic properties I would reccomend to take a look at various algorithms developed to predict transcription factor binding sites (see 1, 2, 3 etc.. (Disclaimer: I am a co-author of STIF). Also, I remember that old version of HMMER package accept nucleotide sequences, looking at the source code will be helpful for you. Also see recent implementations of HMM for predicting genomic properties (1,2) other than TFBS or motifs.

Answer 4

[Woa]

I just came across this good tutorial paper: Seven things to remember about hidden Markov models: A tutorial on Markovian models for time series