Following the introduction on dynamic programming, I’m giving an example using Hidden Markov Models (HMM). Since I’m not here to teach math or the usage of such tools in bioinformatics, but just to present an application of the method, I’ll try to keep everything simple.
Let’s try a simple example: the “grumpy cat model”. This cat can be in a good or bad mood, but since it is grumpy it is more likely to stay in a bad mood. Let’s say that a mood lasts the whole day. Also, when the cat is in a bad mood it is more likely to scratch the carpet than to purr, while the opposite happens when in a good mood.
What you want to achieve with the HMM is to know something about good and bad mood days given the observation of scratched carpet and repeated sounds. In other words, the emotional state of the cat is hidden and you would like to know it given the model.
In general, you need a set of states, the probability of moving from one state to another (given an input) and some observable features. In our “grumpy cat model” example: states can be “good mood” and “bad mood“, the probability of going from good to bad is 75% and from bad to good is 40%. The observable features are “scratched carpet“, with an 80% probability to happen when in bad mood and 30% while in good mood, while 20% and 70% are for “purr“, respectively.
Also we need to know how likely is to start in a bad mood, let’s say 60%. Reaching the END states has a 5% probability for both the bad and the good mood. In this example, the END is the death of the cat.
First and most simple application of dynamic programming to HMM is to answer the following question: how likely is to have a specific sequence of observation given the model? I.e. how likely is to have 5 days of scratched carpet, or 2 purr days + 3 scratched carpet days given our grumpy cat model?
This can be achieved by using the forward algorithm. It starts with a table, in our example with 4 rows (one of START, one for BAD mood, one for GOOD mood and one of END) and 7 columns (the 5 days plus one column for the begin and one for the end).
In the first column you have 1 for START and 0 for everything else (initialization of probabilities).
The iteration is the following: the table cell in row I and column J+1 contains the probability of observing the feature J+1 while in state I (i.e. if I is BAD and J+1 is scratched carpet, you use the value 0.8) times the sum of the values in the previous column (J) each multiplied by the probability of moving from that row to the current one.
This was easy: you have 0.4 probability of going from START to GOOD state, and you have 0.3 probability of a scratchy cat in a good mood. Then you have 0.6 probability of going from START to BAD and 0.8 probability of scratch while in bad MOOD.
Moving to the next column:
|GOOD||0||0.12||0.3*(0.2*0.12 + 0.4*0.48)|
|BAD||0||0.48||0.8*(0.75*0.12 + 0.55*0.48)|
In this case, for the GOOD state we have that either the cat stayed in a good mood, or it changed mood from a bad one to the good one. We have 0.2 chance of staying in a good mood times the chance on the good mood in the previous column (0.12), plus the chance of moving from a bad mood to a good mood (0.4) times the probability of bad mood in the previous column (0.48). The sum of these probabilities is multiplied by the chance of seeing a scratch while in a good mood (0.3).
The same reasoning applies for the bad mood.
This process is then iterated for the remaining columns, as shown in the following tables.
|GOOD||0||0.12||0.065||0.3*(0.2*0.065 + 0.4*0.28)|
|BAD||0||0.48||0.28||0.8*(0.75*0.065 + 0.55*0.28)|
|GOOD||0||0.12||0.065||0.038||0.3*(0.2*0.038 + 0.4*0.163)|
|BAD||0||0.48||0.28||0.163||0.8* (0.75*0.038 + 0.55*0.163)|
|GOOD||0||0.12||0.065||0.038||0.022||0.3*(0.2*0.022 + 0.4*0.095)|
|BAD||0||0.48||0.28||0.163||0.095||0.8*(0.75*0.022 + 0.55*0.095)|
After the last day, there is no emission, then the probabilities of the two states (moods) times the probability of reaching the end from that state (5% for both) are summed.
|END||0||0.013*0.05 + 0.029*0.05|
So, there is a 0.003, i.e. a 0.3% probability of observing 5 days of scratching given our grumpy cat model.
The dynamic programming approach evaluates just one column at the time while considering only the previous one. In this way, we can compute the probability for sequences of any length (i.e. as many days as we want) without using complex algorithms.
As exercise, you could try to compute the same matrix for the sequence of observations “Purr, Purr, Scratch, Scratch, Scratch”.
Jan 25 2016: the post has been edited to fix the transition probability to the END state.