Python Programming for Biology: Bioinformatics and Beyond

Hidden Markov models

A  hidden  Markov  model  (HMM)  is  a  kind  of  Markov  chain  where  the  states  are  not

directly  observable,  but  a  quantity  that  is  directly  observable  is  determined,  often

probabilistically, by the state at a given point in the sequence. The key idea is that there is

not  necessarily  any  direct  correspondence  between  the  invisible  state  and  the  observable

state.  For  example,  if  we  want  to  predict  the  secondary  structure  of  a  protein  (which  we

might  simply  represent  as  alpha-helix,  beta-strand  or  random  coil)  then  the  observable

data  would  be  the  protein  sequence  and  the  hidden  states  could  be  modelled  as  the

secondary-structure  type  at  each  point  in  the  sequence.  Here,  by  considering  the

probabilities  of  changing  from  one  state  to  another  and  the  probabilities  of  making  an

observation, given a particular state, then we can make a prediction about what the hidden

states  are  if  we  have  some  observable  data,  i.e.  having  a  protein  sequence  allows  us  to

make a prediction of the underlying secondary-structure states. Later in this chapter, once

we  have  covered  some  key  theory  and  algorithms,  we  will  look  at  an  HMM  example  in

Python that involves protein sequences.

To be more precise, suppose we can obtain some observable data d for each position in

the Markov chain. We require a function e

i

(d) that gives the probability of generating or

‘emitting’  the  observed  data  given  an  underlying  state  i.  It  is  assumed  this  emission

---

probability  is  independent  of  the  position  in  the  chain.  Sometimes  an  HMM  model  is

constructed  such  that  the  observable  data  has  a  direct  correspondence  to  one  of  the

underlying  states,  in  which  case  e

i

(d)  =  1  for  that  specific  observation  and  e

i

(d)  =  0

otherwise;  we  will  demonstrate  this  idea  later.  Because  for  an  HMM  we  distinguish

between  the  hidden  state  at  position  n  and  the  data  observed  (emitted)  at  position  n,  we

multiply  the  transition  matrices  to  get  the  probabilities  of  the  subsequent  hidden  states

(from the previous states) and multiply the emission probabilities to get the likelihood of

observing the actual data given this underlying state. Hence, the probability of observing

the  whole  sequence  of  data,  over  all  the  positions  of  the  Markov  chain  starting  with

probabilities for the initial state,

can be written as: