麻省理工大学：《Foundations of Biology》课程教学资源（英文版）Lecture 5 Markov models

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