Chap.11 Hidden Markov Model

1. What is a Hidden Markov Model?

1. Hidden Markov Model

2. Hidden Markov Model VS Regular Markov Model

Regular Markov Model에서는, State가 관찰자에게 직접 보이기 때문에 State Transition Probabilities가 유일한 Parameter가 된다. HMM에서는 여기에 Output이 추가된다. 각각의 State는 가능한 Output의 Probability distribution을 가지고 있다. 그러므로 HMM에서 만들어내는 Output Sequence가 바로 State의 Sequence가 되지 않는다.

3. What do you obtain from Hidden Markov Model?

Hidden Markor Model을 이용하면 관측된 Output O = O1,O2,O3...와 Hidden된 State Q = Q1,Q2,Q3... 에 대한 의미있는 결과를 얻을 수 있다.

예를 들어 현재 관측된 Output이 어느 정도 확률로 일어나는 일인가?

또는 관측된 여러 Output이 있을때 그 Output들을 만들어 내는 Hidden State는 어떻게 조직되어 있을까?

이런 질문에 대한 답을 효과적으로 할 수 있습니다.

3. Example

1. Infeasible Method

State : S1, S2 Output M : a, b Transition Probability Matrix : (S1->S1) = 0.9, (S1->S2) = 0.1, (S2->S1) = 0.8, (S2->S2) = 0.2 Emission(Output) Probability Distribution : (S1, a) = 0.5, (S1, b) = 0.5, (S2, a) = 0.25, (S2, b) = 0.75 Initiation Probability Distribution : S1 = pi1 , S2 = pi2

위와 같은 모델이 있을 때 Output 'b,b,b'가 관찰 되었다. 이와 같은 Output이 나올 만한 가능성이 가장 높은 Hidden State Sequence는 어떤 것일까?

우리는 이것을 다음과 같이 생각해 볼 수 있다.

모든 State에 대해서 Output 'b,b,b'가 나올 확률을 구해보면,

S1,S1,S1 => $$ pi1 * 0.5 * 0.9 * 0.5 * 0.9 * 0.5 = 0.10125 * pi1 $$

S1,S1,S2 => $$ pi1 * 0.5 * 0.9 * 0.5 * 0.1 * 0.75 = 0.016875 * pi1 $$

S1,S2,S1 => $$ pi1 * 0.5 * 0.1 * 0.75 * 0.8 * 0.5 = 0.0135 * pi1 $$

S1,S2,S2 => $$ pi1 * 0.5 * 0.1 * 0.75 * 0.2 * 0.75 = 0.005625 * pi1 $$

S2,S1,S1 => $$ pi2 * 0.75 * 0.8 * 0.5 * 0.9 * 0.5 = 0.135 * pi2 $$

S2,S1,S2 => $$ pi2 * 0.75 * 0.8 * 0.5 * 0.1 * 0.75 = 0.0225 * pi2 $$

S2,S2,S1 => $$ pi2 * 0.75 * 0.2 * 0.75 * 0.8 * 0.5 = 0.045 * pi2 $$

S2,S2,S2 => $$ pi2 * 0.75 * 0.2 * 0.75 * 0.2 * 0.75 = 0.016875 * pi2 $$

pi1과 pi2가 같다고 하면 S2,S1,S1이 가장 그럴듯한 State Sequence가 된다. 즉, argmax of Q Prob( Q|O ) = 'S2,S1,S1' 이다.

2. Feasible Method

2. Three Algorithms

1. The Forword and Backward Algorithms

Given the model parameters, compute the probability of a particular output sequence.

2. The Viterbi Algorithm

Given the model parameters, find the most likely sequence of (hidden) states which could have generated a given output sequence.

3. The Estimation Algorithms

Given an output sequence, find the most likely set of state transition and output probabilities. Solved by the Baum-Welch algorithm.

3. Applications

1. Modeling Protein Families

2. Multiple Sequence Alignments

1. 어떻게 sequence의 family에 대해서 multiple sequence alignment를 할 것인가. 2. Viterbi알고리즘을 이용해서 그 sequence를 만들어낼만한 가장 그럴듯한 hidden state path를 찾아낸다. 3. same match state끼리 찾아서 Alignment를 한다. 4. 어떤 경우 이런 방법은 ambiguous 한 결과를 내는 경우도 있다. 5. 그런 경우 Krogh는 ambiguous한 부분을 소문자로 표시하고 alignment는 시도하지 않는다. 6. Dynamic Programming Algorithm으로는 50~100이상의 긴 sequence는 align하지 못하지만 이 방법은 상대적으로 적은 Computing Power를 사용하므로 가능하다.

3. Pfam

1. Pfam은 Protein Families database of alignments and HMMs로 query sequence의 protein domain을 결정하는데 사용된다. 2. Pfam은 수많은 protein domain과 family를 커버하는 많은 수의 multiple sequence alignments와 HMM 데이터를 갖고 있다. 3. Gene을 Annotation하는 것은 그들의 functional domain이 어디인지, 알려진 domain들과 homology가 있는 부분은 어디인지 그들의 기능은 무엇인지 아는것 부터 시작한다. 4. 기존의 domain database는 HMM을 사용하지 않았으므로 잘 Conserved되어 있는 motif(ungapped multiple sequence alignment가 가능한)만 검색할 수 있었다. Pfam은 HMM을 사용함으로써 모든 domain에 대해서 효과적인 characterization이 가능하다. 5. Pfam에서는 parameter를 Baum-Welch방법을 이용해서 결정하지 않는다. Alignment 그 자신을 이용해서 parameter를 맞춤.

4. Gene Finding

1. 많은 sequence 데이터가 밝혀지고 있다. 가장 중요한 것은 sequence중에서 gene은 어디에 있는가를 아는 것이다. 2. Gene을 찾는 프로그램 중 인기있고 성공적인 프로그램은 GENESCAN이란 프로그램이다.

1. Semihidden Markov Models

1. 자기 자신에 대해 transition 할 확률은 p라고 하면 n번 자기 자신이 될 확률은 p^(n-1)(1-p)이다. ==> 이때 시간의 길이를 분포로 나타내면 geometric distribution을 보인다. 2. semiHMM에서는 자기 자신(State)에 대한 transition 확률은 0이다. 그리고 한 State 상태에 있을때 하나의 symbol을 내는 것이 아니라 전체 sequence를 내어 놓는다. 그 sequence의 length는 어떤 정해진 확률분포를 따르고 각 length에 대한 sequence를 만드는 model도 정해진 확률 분포를 따른다. 3. 각 State는 random variable Ls와 연관된다. 그 Ls의 Range는 0,1,2... 이며 이는 Ls의 관측한 value l이다. 또한 Random Variable Ys,l 이 있는데 이것은 length l의 모든 sequence를 구성한다. S에서 Ls의 distribution에 따라 length l을 결정하면 Ys,l에 의해 length l의 sequence가 결정된다. 그리고 새로운 State로 process는 진행. 또 다른 sequence를 만든다. 이 모든 sequence를 이어 붙이면 semiHMM의 최종 output인 sequence가 생긴다. 4. semiHMM은 새 State가 만들어 내는 sequence가 어디부터 시작되는 지 알 수 없기 때문에 regular HMM보다 복잡하고 어렵다. 5. Burge(1997)는 long intergenic region의 length가 geometric distribution을 따르고, 이 Length가 sequence를 iid fashion으로 만든다면 Algorithm을 적용할 수 있다는 것을 밝혀냈다. 그리고 이 가정은 터무니없는 것이 아니며 prediction의 정확도에 많은 영향을 끼치지도 않는다. 6. Parse PI를 State의 sequence라고 하고 관찰된 sequence S에 대해 Viterbi Algorithm을 이용하여 optimal parse Piopt를 구할 수 있다. 그리고 이 Optimal Parse를 이용해 Gene을 Prediction할 수 있다.

2. Gene Structure

1. Gene은 noncoding region과 비교 해서 확연한 특징을 갖고 있다. 그렇지만 모든 gene들의 특징이 동일한것은 아니다. 2. 어떤 경우에는 nocoding region에도 gene이 갖고 있는 공통된 signal이 random하게 들어갈 수 있다. 3. Gene의 구성

• Intergenic region --- promoter --- TATA box --- ( Exon || Intron ) --- terminate codon --- poly A

3. The Training Data

1. 380개의 gene을 포함하는 250만 base의 Human DNA 사용. 그중의 142개의 gene은 single-exon gene이고 나머지 gene들에는 1492개의 exon과 1254개의 intron이 존재한다. 그리고 (intron을 뺀)coding region만 있는 1619개의 human gene 추가. 총 230만 coding bases.

4. The Model

1. 13 State의 semiHMM 모델을 만듦 2. 이제 각각의 State 마다 Ls와 Ys,l의 distribution을 구한다. 3. Intergenic Region (N)

• 3.1 gene들이 random하게 분포되었다고 가정하면, 주어진 길이안의 gene의 수는 Poisson distribution으로 모델링 할 수 있다. 그리고 각 gene 간의 거리는 exponential distribution(discrete일때는 geometric distribution)으로 모델링 한다. 그러므로 LN은 geometric distribution을 따른다. 현재 Human DNA에는 3억개의 base에 6만개의 gene이 있다고 생각함. 3.2 Ys,l ( The sequence of length l )은 fifth-order Markov 모델에 의해 생김. 이 모델은 앞으로 N1, N2와 같은 State의 모델이 된다. Intergeic null model이라고 명명.

4. TATA box (TATA)

• 4.1 15-base weight matrix model ==> See Section 5.3.2

5. N1

• 5.1 LN : Uniform distribution 28~34 base 5.2 Ys,l : Null intergenic model

6. Cap end

• 6.1 8-base weight matrix

7. N2

• 7.1 LN : mean 735 bases인 geometric distribution 7.2 Ys,l : Null intergenic model

8. TIE

• 8.1 18-base weight matrix

9. SEG

• 9.1 LN : Empirical distribution from the training set 9.2 Ys,l : fifth-order nonhomogenous Markov Model.(Multi exon과 가음 없다.)

  -> Intergenic Region은 homogenous하다. -> 각 codon의 position마다 다른 model을 써야 하므로 homogenous일때보다 parameter가 3배 더 많다. -> 그래서 1619개의 coding sequence가 필요했다.

10. Multiexon gene

• 10.1 복잡하다. 한가지 복잡한 예 : 한 codon이 두 exon에 의해 분리될 때 각각의 경우마다 계산해야된다. Intron이 reading frame을 1/3의 확률로 분리시킨다. 10.2 Ls of Exon : Empirical distribution from training set. ( length of initial, internal, terminal exons ) 10.3 Ls of Intron : a geometric distribution 10.4 Ys,l of Exon : fifth-order nonhomogenous Markov Model 10.5 Ys,l of Intron : fifth-order homogenous Markov Model, Null intergenic model 10.6 begining과 end에는 donor splice signal과 acceptor splice signal이 존재하는데 이 신호를 잡는게 intron/exon strucure를 잡아내는데 중요하다. 이 신호는 weight matrix를 쓰거나 first order Markov쓰는데 효과적으로 잡기가 불편하다. 그래서 Complete joint probability distribution을 쓰고 싶었으나 데이터 부족으로 second-order Markov Model을 사용했다.

11. 3'UTR

• 11.1 Ls : Geometric length of mean 450 11.2 Ys,l : Intergenic null model

12. Poly A

• 12.1 Ls : Constant length : 6 12.1 Ys,l : weight matrix

13. Transition 확률

• 13.1 대부분 1

  13.2 N->TATA : 0.7, N->N1 : 0.3 13.3 TIE->SEG : Proportion of SEG, TIE->E1 : 1 - Proportion of SEG 13.4 E<->I : Observed data proportion of training data

14. Testing

• 14.1 Uncharacterized sequence of DNA -> Viterbi Algorithm -> Optimal Parse구함 -> List of states & Length of sequence generated at those states

15. Further

• 15.1 다른 종류의 확률이 쓰일 수 있다. Burge model에서는 GC Content도 쓰인다. (GC가 높은 곳에 gene density가 높음) 15.2 여러가지 factor들이 고려되면 더 나은 model을 만들 수 있다.