CS262 Computational Genomics Lecture note 4 Thu 4 11 02 Submitted by Waraporn Tongprasit and Joe Francis Walkush Hidden Markov Models Have you ever been to a casino A game exists in which a player wins 1 dollar for each roll that lands on 1 2 3 4 or 5 and loses 6 dollars if the roll lands on a 6 With fair dice the probability that the dealer wins i e rolls a 6 is 1 6 This probability is independent from the sequence of the previous rolls If you were a casino owner you would like to improve your chance to win the six dollars bucks from the gambler How can you do that If you are a dishonest businessman you may introduce a second die one that is loaded and consequently has a higher probability of landing on a 6 Assume that the probability to win the game if you roll the loaded die is 50 i e the dice will be 6 with probability 0 5 and will be other with probability 0 1 each However because you do not want to be caught you have to change dice at random say at 5 percent when going from fair to loaded and 10 percent from loaded to fair The model representing the rolling dice game is as follow 0 95 FAIR DICE 0 05 LOADED DICE 0 10 0 90 Where Alphabet 1 2 3 4 5 6 and P 1 P 2 P 3 P 4 P 5 P 6 1 6 for fair dice and P 6 0 50 P 1 P 2 P 3 P 4 P 5 0 10 for loaded dice From the above diagram you can see that sum of all transitions out of a state is 1 This diagram is HMM Hidden Markov Model Why is it called Hidden Markov Model Let say that we have a sequence of dice rolling as follow 1 2 6 4 3 6 5 2 6 6 4 1 3 6 6 6 6 6 6 6 6 5 4 6 1 6 We cannot tell which state each rolling is in e g subsequence 6 6 6 6 6 6 may happen using the loaded dice or it can happen using the fair dice even though the later case has less probability The state is hidden from the sequence e g we cannot determine the sequence of states from the given sequence Hence it is Hidden Markov Model Three categories of questions from HMM 1 Evaluations question For example given a sequence X x1 x2 x3 xn of rolls what is the probability that x was generated by the model 2 Decoding question For example given a sequence X x1 x2 x3 xn of rolls what is the most likely sequence 1 2 3 n of states argmax X The solutions for decoding problem do not have to be unique 3 Learning problem For example given the architecture of a model and sequence X x1 x2 x3 xn of rolls estimate model parameters HMM in Genomic Computation A Markov model or Markov chain is a complete graph with edges labeled by probabilities of transiting from a state to another state HMM used in genomic computation is MM with Alphabet A C G T or 20 amino acids Set of states Q q1 q2 qn Transition probabilities between any two states qk akl ql Emission probabilities ek b P xi b i k b k Q Characteristics of HMM HMM is memoryless and n aki 1 i 1 ek b 1 b The probability of going to the next state depends on only the current state not the history sequence of states The sequence of states is hidden from the sequence of outcome CPG Islands Wherever a CG dinucleotide occurs there is a high likelihood that the C nucleotidewill change to a T Thus CG TG This process is called methylation However there are regions where methylation does not occur or where it is very unlikely These regions are where we find CG pairs and are often in functional regions that is they are found in regions where genes are heavy For example we have may have probabilities in each state as follows This is intended to show how differing states lead to differing emission probabilities i e G will follow C in CpG with probability of 274 while G will almost never follow C in non CpG probability of 078 The numbers are not necessarily accurate Non CpG CpG A C G T A 18 17 16 08 C 27 37 34 35 G 43 27 37 38 T 12 19 12 18 A C G T A 3 32 25 18 C 20 3 25 24 G 28 08 30 29 T 21 30 21 29 The finite state machine might look something like this where every transition from one state to the next state is affiliated with some transition probability The signifies CpG non CpG Not all arrows are drawn but this shows the general idea every state has a transition to every state including itself A C G T A C G T Start has transitions to all other states Start Decoding Given x x1 xn we want to find 1 n such that probability P x is maximized argmax P x Define Vk xi Probability of the most probable sequence of states that ends with xi being at state k x1 xi k xn As stated in the last page Vk xi Probability of the most probable sequence of states that ends with xi being at state k Then it follows that for any state l Vl xi 1 el xi 1 max k Vk xi akl That is the probability of the sequence of states that ends at xi 1 being at state l is equal to the emission probability at that state the max over all k of this function evaluated at xi coming from state k the transition probability of k l The runtime of this algorithm is O k2N where k is the number of states and n is the sequence length Decoding Viterbi Given sequence X x1 x2 x3 xn Initialization V0 0 1 dummy start state Recursion Vl i el xi max Vk i 1 akl k Ptri l argmax Vk i 1 akl k Termination P X max Vk n k argmax Vk n k n Traceback Ptri i i 1 The difficulty for this calculation is that the computer cannot hold a very small value Hence we use log space for decoding Log space log ab log a log b Thus calculating probability using log space we do not have to multiply the probabilities In log space we do so using adding log of probabilities instead Therefore Vl i log el xi max Vk i 1 akl K Evaluation Forward Initialization f0 0 1 Recursion fl i el xi Sk fk i 1 akl Termination P x Sk fk n fl i P x1 xi pi l P x1 xi 1 pi l P xi pi l el xi Sk P pi l pi 1 k P x1 xi pi …
View Full Document
Unlocking...