ProfileHiddenMarkovModel

BiologicalSequenceAnalysis에서, MultipleAlignment되어있는 Protein family 연구. 이를 통해 unknown protein서열이 특정 패턴과 관련있는가를 알 수 있다.

We are given a correct MultipleAlignment, from which we will build a model that can be used to find and score potential matches to new sequences.

Introduction

1. functional biological sequence typically come in families
2. sequence analysis : based on identifying the relationship of an individual sequence to a sequence family

3. PairwiseAlignment : may not find sequences distantly related to the ones you have already

4. alternative approach : use statistical feature of the whole set of sequences in the search, MultipleAlignment

5. our approach to consensus modelling - ProbablisticModel : develop a particular type of HiddenMarkovModel "Profile HMMs"

6. Chapter 5의 목적 : correct MultipleAlignment가 주어졌을 때 model을 만드는 것

7. 이 모델을 통해서 new sequence에 potential match scores을 찾는 것 : Chapter 6 (MultipleAlignment)

Ungapped score matrices

1. PositionSpecificScoreMatrix (PSSM)

Adding insert and delete states to obtain profile HMMs

1. gap
2. position specific gap score : HMM로 해결 가능

3. transition 을 줄이는 방법 : SilentState

4. D -> D transition 은 확률이 틀릴 수 있으나, I -> I transition 은 same cost를 갖는다.

Profile HMMs generalise pairwise alignment

Deriving profile HMMs from multiple alignment

1. 만들고자 하는 model 은 특정한 sequence 하나가 아니라 family 의 consensus sequence 를 나타낸다.

Non-probabilistic profiles

1. 문제점
   1. anomalies : sequence 가 많이 관찰될수록 확실성이 증가하지만 이 경우에는 하나에서 관찰되는것과 100개에서 관찰되는것이 동일한 score
   2. gap : 모든 deletion 이 동일한 score

Basic profile HMM parametrisation

1. parametrisation의 목표 : 모든 sequence 의 space 에서 모델이 나타내는 sequence 의 disribution 이 family의 member들에서 peak를 만들도록 함.
2. control 할 수 있는 parameter

   1. values of probabilities : sequence 들의 수가 작을때 zero probability 때문에 문제가 됨. LaplaceRule.

   2. length of the model : 어떤 column 을 match 로, 어떤 column 을 insert 로 둘 것인가? (sequence 가 하나가 아니기 때문에...) : 잘 작동하는 간단한 heuristic rule 은 gap 이 반이 넘으면 insert 로 하는 것.

Searching with profile HMMs

1. 어떤 sequence 의 family에서의 potential membership을 detection : 점수(score)만 있으면 됨.
2. HMM에 대하여 match를 score하는 방법

   1. Viterbi equations : sequence x의 최적의 경로 찾음 (ViterbiAlgorithm)

   2. Forward equations : P(x｜M) 으로 가는 모든 경로들의 합 (ForwardAlgorithm)

Viterbi equations

1. Insert state 에서의 emission 은 background 와 같은 것으로 가정한다.

Forward algorithm

1. Viterbi 에서의 max function 을 sum 으로 대신

Alternatives to log-odds scoring

1. LL (log likelihood) score : length dependent 하기 때문에 length 로 나눠줘야 되고, standard deviation 으로 regularize 한 Z-score 사용
2. lod-odds 가 더 나음

Alignment

1. Viterbi variable 을 tracing back 하면 됨.

Profile HMM varients for non-global alignments

1. local, repeat, overlap

More on estimation of probabilities

Simple pseudocounts

1. LaplaceRule

2. Add a quantiti proportional to the background distribution
3. Dirichlet prior

Dirichlet mixtures

1. P(k|cj) : 실제 count 가 cj 일때 이것이 distributio k 에 의할 확률
2. 일반적으로 50 이상의 sequence 가 있어야 제대로된 HMM 만들 수 있으나, Dirichlet mixture 쓰면 10 - 20 개로 만들 수 있음.

Substitution matrix mixture

1. single Dirichlet formulation 에서 pseudocounts 를 조절함으로써 Dirichlet mixtures 대체 가능. (SubstitutionMatrix)

2. s(a,b)를 사용하여 P(a|b)를 계산하여 pseudocount value인 alpha 값 구하는데 사용. (어떤 column 에서 b 가 나오는 확률에 b 가 a 로 바뀔 확률을 곱함)
3. constant A : A = 5R 이면 적절 (R 은 서로 다른 residue type 의 수)

Deriving P(b|a) from ana arbitrary matrix

Estimation based on an ancestor

1. 보다 이론적이고 직접적인 방법. pseudocount 사용하지 않음. 모든 관찰된 sequence 가 common ancestor 로부터 독립적으로 나왔다고 가정.
2. Different column 은 conservation 정도가 다르다는 문제점이 있음. 따라서 conserved 된 column 에는 conserved matrix를 쓰고(PAM30), varied column 에는 divergent matrix 를 써야 함 (PAM500)

3. 그렇다면 optimal matrix 를 어떻게 아는가? observed data 의 likelihood 를 최대화시키는 matrix 고르면 됨. (MaximumLikelihood time-dependent approach)

Testing the pseudocount methods

Optimal model construction

1. model construction

2. L column 을 marking 하는데 2^{L combination 존재 : 2}L 개의 서로 다른 ProfileHmm 존재

3. marking 방법
   1. manual construction
   2. heuristic construction

   3. DynamicProgramming 에 의한 MAP construction

MAP match-insert assignment

1. i column 이 match state 로 mark 되어 있을때, j를 i 다음에서 sequence 끝까지 증가시켜나가면서 어디에서 j를 match state 로 잡을때, likelihood 가 최대화되는지를 결정한다.

Weighting training sequences

Simple weighting schemes derived from a tree

1. evolutionary tree 에 기반
2. 두가지 방법이 있음.

Root weighed from Gaussian parameters

1. weight 는 root distribution 에 대한 leaves 의 영향을 나타낸다. -> root distribution 의 mean 은 각 leaves 에 대한 weight 에 의해 좌우된다.

Voronoi weights

1. tree 에 의하지 않는 방법
2. sequence space 에서 어떤 것들은 몰려 있고, 어떤 것들은 흩어져 있다.
3. joining neighbor 들을 가지고 polygon (Voronoi diagram)을 만듬. 어떤 sequence 주위의 empty space 양에 비례해서 sequence 에 weight를 준다.

Maximum discrimination weights

1. 간접적인 방법
2. discrimination D 를 최대화하면 family 에서 멀리 떨어진 member 들을 강조하는 효과를 낳는다.
3. weight 는 1 - P(M|xi)

4. ExpectationMaximisation 의 일종

5. misclassification 있을 때는 문제가 됨

Maximum entropy weight

1. 각 column 에 대해 구한 weight를 averaging 하는 방법
2. entropy 를 사용해서 서로 다른 column 에서 나온 정보를 결합할 수 있음. uniform 할수록 entropy가 높기 때문에 entropy를 maximize 시키는 weight를 고름.
3. Maximum discrimination weights 과 유사하며, 마찬가지로 outlier 가 있을때는 문제가 됨.