CpG Island hMm Ill Want to infer ↓↓↓↓↓↓ A GA G A Observe But HMM is written in the other direction (observable depends on hidden)
CpG Island HMM III … Want to infer A C T C G A G T A Observe But HMM is written in the other direction (observable depends on hidden)
Inferring the Hidden from the observable (Bayes' rule) P(H=h1, h2,,hn,0=01, 02,,On) Conditional prob P(AB)=P(A, B)/P(B P(H=h1,.,hn, O=O1 PO=01,,On) P(H=h,…hn)(O=0n,…On|H=hhn) P(O=01,On) P(O=O1,. ,On) somewhat difficult to calculate But notice P(H=hn,…,hn2O )>P(H=h1,…,hn,O mpliesP(H=h,…,hn|O=0,,O)>P(H=h1,hn|0=01,,On) so can treat P(0=O1, ,0n)as a constant
Inferring the Hidden from the Observable (Bayes’ Rule) P ( H = h 1, h 2 ,..., hn | O = o 1, o 2 ,..., on ) Conditional Prob: P(A|B) = P(A,B)/P(B) P ( H = h 1,..., hn , O = o 1, ..., on ) = P (O = o 1, ..., on ) P ( H = h 1,..., hn )P (O = o 1 ,..., on | H = h 1,..., hn ) = P (O = o 1, ..., on ) P (O = o 1 ,..., on ) somewhat difficult to calculate But notice: P ( H = h 1, ..., hn , O = o 1,..., on ) > P ( H = h ′1, ..., h ′n , O = o 1, ..., on ) implies P (H = h 1, ..., hn | O = o 1,..., on ) > P (H = h ′1 ,..., h ′n | O = o 1, ..., on ) so can treat P (O = o 1 ,..., on ) as a constant
Finding the Optimal"Parse 99 (Viterbi algorithm Want to find sequence of hidden states hopt =hip, hip, hyp which maximizes joint probability: P(H=h,,,hn,0=01,On) (optimal "parse" of sequence Solution Define rch= probability of optimal parse of the subsequence 1. i ending in state h Solve recursively, i. e. determine R2 in terms of r,etc A. Viterbi, an MiT bS/MEng student in E.E. -founder of Qualcomm
Finding the Optimal “Parse” (Viterbi Algorithm) H opt opt opt , h 2 which maximizes joint probability: P( H = h1, ..., h n, O = o1,..., o n) Want to find sequence of hidden states = h1 opt , h 3 , ... (optimal “parse” of sequence) Solution: ( h )= probability of optimal parse of the Define Ri subsequence 1..i ending in state h ( h ) Solve recursively, i.e. determine R ( 2 h) in terms of R 1 , etc. A. Viterbi, an MIT BS/MEng student in E.E. - founder of Qualcomm
Trellis" Diagram for Viterbi algorithm Position in Sequence→ +2 +3j+4 个0050 ○O A T G C A Run time for k-state hmm on sequence of length l?
“Trellis” Diagram for Viterbi Algorithm Position in Sequence → 1 … i i+1 i+2 i+3 i+4 … L T … A T C G C … A Run time for k-state HMM on sequence of length L? Hidden Sta et s →
Viterbi algorithm examples What is the optimal parse of the sequence (ACG11000 1000℃8011000407100006011000 Powers of 1.5 N=204060 80 (1.5)=3×1031×1073×10101×1014
Viterbi Algorithm Examples What is the optimal parse of the sequence: • (ACGT)10000 • A1000 C80 T1000 C40 A1000 G60 T1000 Powers of 1.5: N = 20 40 60 80 (1.5)N = 3x103 1x107 3x1010 1x1014