BiologicalSequenceAnalysis에서 HiddenMarkovModel을 사용하여, PairwiseAlignment를 수행하는 것.

DynamicProgramming(DP) --> FiniteStateAutomata(FSA) --> HiddenMarkovModel(HMM)

• HMM의 장점 : SequenceAlignment의 신뢰도를 평가하는 ProbabiliticModel로 사용가능.

Pair HMMs

FSA의 HMM으로의 변환 (fig4.1)

• EmissionProbability : Pab (aligned pair a:b, M state), Pa(a against gap, X and Y state)

• TransitionProbability

  • M->insert state (X,Y) : delta(d)

  • insert->insert : epsilon(e)

완전확률모델화 (fig4.2)

• Begin, End state필요 : DP의 초기화와 종료조건의 형식화

• (M,X,Y)->End TransitionProbability : tau(t) --> alignment의 평균길이결정

PairHmm

• 표준HMM의 단일서열대신, alignment를 emission하여 pair HMM이라 구별
• alignment pair생성과정 : 특정 alignment 생성확률은 아래 각단계확률의 곱
  • Begin state출발
  • 반복과정

    • 현상태에서 TransitionProbability분포에 따라 다음 상태를 선택

    • 선택된 상태의 emission probability에 따라 symbol pair를 결정
  • End state로 전이시 종료

The most probable path is the optimal FSA alignment

v*(i, j) - 확률치, V*(i, j) - log odds score

표준 DynamicProgramming과정을 위해 HMM으로부터 log odds score를 구하여 최적정렬을 구하는 과정

Algorithm: Viterbi algorithm for pair HMMs

ViterbiAlgorithm

     초기화 : vM(0,0) = 1, v*(i,0) = v*(0,j) = 0
     반  복 : i = 1,...,n,  j = 1,...,m
              vM(i,j) = pxi,yj max[(1-2d-t)vM(i-1, j-1), (1-e-t)vX(i-1, j-1), (1-e-t)vY(i-1, j-1)]
              vX(i,j) = qxi max[dvM(i-1,j), evX(i-1, j)]
              vY(i,j) = qyi max[dvM(i,j-1), evY(i, j-1)]
     종  료 : vE = tmax[vM(n,m), vX(n,m), vY(n,m)]

best alignment 찾기 -- DynamicProgramming, HMM에서처럼 traceback으로...

Random ProbabilisticModel (null model Probability)

P(x,y|R) = z^2 (1-z)^(n+m) Prod(i=1,n)qxi Prod(j=1,m)qxj

log odds score

s(a,b) = log(Pab/qaqb) + log((1-2d-t)/(1-z)^2)
d = -log(''d''(1-''e''-''t'')/(1-z)(1-2''d''-''t''))
e = -log(''e''/(1-''t''))

Algorithm: Optimal log-odds alignment

     초기화 : VM(0,0) = 1logz, VX(0,0) = VY(0,0) = - infinity, V*(i,-1) = V*(-1,j) = - infinity
     반  복 : i = 0,...,n, j = 0,...,m, (0,0)제외
              VM(i,j) = s(xi,yi) + max[VM(i-1,j-1), VX(i-1,j-1), VY(i-1,j-1)]
              VX(i,j) = max[VM(i-1,j)-d, VX(i-1,j)-e]
              VY(i,j) = max[VM(i,j-1)-d, VY(i,j-1)-e]
     종  료 : V = max[VM(n,m), VX(n,m)+c, VY(n,m)+c]
              c = log(1-2d-t) - log(1-e-t)

c : M,X,Y->End로의 log-odd score를 모두 같게하기 위함

A pair HMM for local alignment

LocalAlignment를 PairHmm으로 변환

update equation, boundary condition --> adding states and transitions LocalAlignment에서의 정렬되지 않은 서열을 설명하는 random ProbabilisticModel을 첨가

The full probability of x and y, summing over all paths

DynamicProgramming은 서열간 유사성이 약할 때 정확한 서열정렬을 확인하기 어렵다.

HMM에서는 모든 서열정렬에 대해 확률을 더하여 두 서열이 유사한 정도를 확인한다.

P(x,y) = Sum(phi) P(x,y,phi)

ForwardAlgorithm의 fK(i,j)는 K상태로 끝나고 (i,j)에 이르는 모든 서열정렬의 합이다.

Algorithm: Forward calculation for pair HMMs

    초기화 : fM(0,0) = 1, fX(0,0) = fY(0,0) = 0, f*(i,-1) = f*(-1,j) = 0
    반  복 : i = 0,...,n, j = 0,...,m, (0,0)제외
             fM(i,j) = pxiyi [(1-2d-t)fM(i-1,j-1) + 
                              (1-e-t)(fX(i-1,j-1) + fY(i-1,j-1))]
             fX(i,j) = qxi [dfM(i-1,j) + efX(i-1,j)]
             fY(i,j) = qyj [dfM(i,j-1) + efY(i,j-1)]
    종  료 : fE(n,m) = t[fM(n,m) + fX(n,m) + fY(n,m)]

fE(n,m)이 full probability로 null model probability에 대한 log-odds score를 구하여 두서열의 유사정도을 가늠

이 score를 x,y서열이 phi정렬을 하는 P(phi | x,y)를 구하는데 사용된다.

P(phi | x,y) = P(x,y,phi)/P(x,y)

이때, phi가 phi* 즉, Viterbi경로라면 vE(n,m)/fE(n,m)으로부터 optimal scoring alignment에서 구한 정렬이 얼마나 정확한지를 판단한다.

Suboptimal alignment

최적정렬과 거의 같은 score을 같는 정렬인 suboptimal alignment

• 최적정렬과 몇군데만 다른 경우 : 서열길이가 늘어날수록 그 수가 지수함수적으로 증가한다. 최적정렬과 확연히 다른 경우

Probabilistic sampling of alignments

suboptimal alignment는 주어진 서열쌍에서 생겨날 수 있는 정렬정보 형태를 보여주고, 특정한 관심있는 특성을 이러한 정렬들에 대한 평균으로부터 알아낼수 있다(HMM PosteriorDecoding).

sample alignment생성법(traceback)

   fM(i,j) = pxiyi [(1-2d-t)fM(i-1,j-1) + 
                    (1-e-t)(fX(i-1,j-1) + fY(i-1,j-1))]
   M(i,j) 상태
          M(i-1,j-1)    pxiyj(1-2d-t)fM(i-1,j-1)/fM(i,j)
          X(i-1,j-1)    pxiyj(1-e-t)fX(i-1,j-1)/fM(i,j)
          Y(i-1,j-1)    pxiyj(1-e-t)fY(i-1,j-1)/fM(i,j)
   X(i,j) 상태
          M(i-1,j)      qxidfM(i-1,j)/fX(i,j)
          X(i-1,j)      qxiefX(i-1,j)/fX(i,j)
   Y(i,j) 상태
          M(i,j-1)      qyjdfM(i,j-1)/fY(i,j)
          X(i,j-1)      qyjefY(i,j-1)/fY(i,j)

sample alignment상에 나타나는 score에 강하게 기여하는 pairing은 정렬신뢰도의 자연지표로 쓰일수 있다.

Finding distinct suboptimal alignments

최적정렬과 확연히 다른 정렬찾기 (Waterman & Eggert)

최적정렬이 확인된 후 최적정렬에 대한 cell을 0으로 만들고 다시 Viterbi DP matrix계산, traceback, 정렬점수가 T 이하일때까지 반복 --> matrix가 메모리상에 있으면 최적정렬cell을 mark하고 그부분만 update

The posterior probability that xi is aligned to yi

정렬의 일부분은 conserved, 일부분은 variable --> 정렬의 일부분에 대한 신뢰척도를 주는 것이 유용

신뢰척도 - (xi,yj)pair를 갖는 모든 정렬의 확률의 합을 구하고 full probability로 나눈다. 1에 가까울수록 신뢰도가 높음

P(x,y,xiㅇyj) = P(x1..i,y1..j,xiㅇyj)P(xi+1..n,yj+1..m|x1..i,y1..j,xiㅇyj) 
              = P(x1..i,y1..j,xiㅇyj)P(xi+1..n,yj+1..m|xiㅇyj) 
              = fM(i,j)bM(i,j)

Algorithm: Backward calculation for pair HMMs

BackwardAlgorithm

    초기화 : bM(n,m) = bX(n,m) = bY(n,m) = t, b*(i,m+1) = b*(n+1,j) = 0
    반  복 : i = n,..,1, j = m,..,1,  (n,m)제외
             bM(i,j) = (1-2d-t)pxi+1yj+1bM(i+1,j+1) + d[qxi+1bX(i+1,j) + qyj+1bY(i,j+1)]
             bX(i,j) = (1-e-t)pxi+1yj+1bM(i+1,j+1) + eqxi+1bX(i+1,j)
             bY(i,j) = (1-e-t)pxi+1yj+1bM(i+1,j+1) + eqyj+1bY(i,j+1)

P(xiㅇyj|x,y) = P(x,y,xiㅇyj)/P(x,y)

The expected accuracy of an alignment

최대 전체 정확도를 가진 완전정렬

A(phi) = Sum((i,j)->phi)P(xiㅇyj)

phi의 전체 정확도의 자연척도, 두 서열이 유사정도에 대한 분별점수를 제공않음

gap cost없이 P(xiㅇyj) score로 표준DP후 traceback

Recursion

A(i,j) = max[A(i-1,j-1) + P(xiㅇyj), A(i-1,j), A(i,j-1)]

Pair HMMs versus FSAs for searching

확률모델링의 강점 중 하나는 대량의 data D가 모델 M의 샘플에 대응한다면, D의 M에 대한 가능성이 최대를 이룬다는 것으로 모델 파라미터에 의한다

따라서, PairHmm에 대한 파라미터 수치가 유사서열쌍의 통계를 잘 묘사한다면, 검색에 그 파라미터수치를 가진 모델을 사용해야 한다.

그러나 현재 사용중인 비HMM알고리즘은 두가지 점에서 여기에 미흡하다.

• Viterbi 경로를 따름으로 full probability를 계산치 않는다
  • 전체확률보다 best match를 고려하는 모델비교는 심지어 큰 데이타집합에서도 데이타원을 감지 못할 수 있다.
• FSA를 사용하면 파라미터를 쉽게 확률로 바꿀수 없다.
  • 지역정렬중의 초기및 마지막의 unpaired sequence는 FSA는 0이고, 확률모델에선 0이 아님

  • 같은 FSA 점수에 맞는 LogOddsRatio를 갖는 두 개의 pair HMM이 존재할 수 있다