12
$\begingroup$

Hidden Markov models (HMMs) are used extensively in bioinformatics, and have been adapted for gene prediction, protein family classification, and a variety of other problems. Indeed, the treatise by Durbin, Eddy and colleagues is one of the defining volumes in this field.

Although the details of each of these different applications of HMMs differ, the core mathematical model remains unchanged, and there are efficient algorithms for computing the probability of the observed sequence given the model, or (perhaps more useful) the most likely hidden sequence given the sequence of observed states.

Accordingly, it seems plausible that there could be a generic software library for solving HMMs. As far as I can tell that's not the case, and most bioinformaticians end up writing HMMs from scratch. Perhaps there's a good reason for this? (Aside from the obvious fact that it's already difficult, nigh impossible, to get funding to build and provide long-term support for open source science software. Academic pressures incentivize building a new tool that you can publish a paper on much more than building on and extending existing tools.)

Do any generic HMM solver libraries exist? If so, would this be tempting enough for bioinformaticians to use rather than writing their own from scratch?

$\endgroup$
  • 1
    $\begingroup$ You make it sound like “writing HMMs from scratch” is a huge endeavour. ;-) That said, of course having existing implementations of the relevant algorithms makes sense. $\endgroup$ – Konrad Rudolph Jun 2 '17 at 10:56
6
$\begingroup$

I would also recommend to take a look at pomegranate, a nice Python package for probabilistic graphical models. It includes solvers for HMMs and much more. Under the hood it uses Cythonised code, so it's also quite fast.

$\endgroup$
4
$\begingroup$

There are certainly software libraries for working with HMMs. For a general-purpose implementation in C++, take a look at the SeqAn HMM algorithms.

For your purposes, i.e. “computing … the most likely hidden sequence given the sequence of observed states”, you’d invoke viterbiAlgorithm with your observed sequence and the HMM graph.

More fundamentally I think that most existing, mature implementations are probably found in the domain of signal processing, which has been using them longer than biology, and where most of the underlying theory was developed.

$\endgroup$
4
$\begingroup$

If I remember correctly Ewan Birney's Dynamite (a compiler-compiler) as presented at ISMB 1997 had this functionality, there is also some code here on GitHub https://github.com/birney/wise3 which at least mentions Dynamite. Suspect Ewan is too busy these days to work on this, although he has tweeted about blowing dust of his old Dynamite, sorry Dynamite code: https://twitter.com/ewanbirney/status/788121636973142016

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.