791/7.36/BE490 Lecture 5 Mar.9.2004 Markov models 8 DNA Sequence Evolution Chris burge
7.91 / 7.36 / BE.490 Lecture #5 Mar. 9, 2004 Markov Models & DNA Sequence Evolution Chris Burge
Review of markov HMM Models for dna Markov Models for splice sites Hidden Markov models looking under the hood The Viterbi algorithm Real World HMMs Ch. 4 of Mount
Review of Markov & HMM Models for DNA • Hidden Markov Models - looking under the hood Ch. 4 of Mount • Markov Models for splice sites • The Viterbi Algorithm • Real World HMMs
CpG islands %C+G 60 40
CpG Islands %C+G 60 50 40 30
Cpg Island Hidden Markov Model P:=0.001 g P=0.99999 P:=0999 Genome Hidden Pn:=0.00001 Island ↓↓↓↓↓↓↓↓ A C T C GA G T A C G A T Observable CpG Island: 0.3 0.3 0.2 0.2 Genome:02020.30.3
Hidden CpG Island Hidden Markov Model P Pig = 0.001 P = 0.99999 gg ii = 0.999 Genome Pgi = 0.00001 Island … A C T C G A G T A CpG Island: C 0.3 G 0.3 A 0.2 T 0.2 Genome: 0.2 0.2 0.3 0.3 Observable
CpG Island hmm i P=0.99999 Pin =0.001 Island 99 g “ Transition Genome P:=0999 probabilities" Pn:=0.00001 ACT…℃ GA G T A C G A T “ Emission Probabilities” CpG Island:"0.3030.20.2 Genome:0.20.2030.3
CpG Island HMM II P = 0.99999 Pig = 0.001 Island gg “Transition Genome Pii = 0.999 probabilities” Pgi = 0.00001 … A C C G A G T A T CpG Island: C G A T 0.3 0.3 0.2 0.2 Genome: 0.2 0.2 0.3 0.3 “Emission Probabilities
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
