BioHackersNet어떤 State에서의 Probability는 그 전단계의 State에 의해서만 영향을 받는다.
Contents
MarkovChain
BiologicalSequenceAnalysis에서 DNA서열을 예로 들면, 4개의 State A,C,G,T가 있고 이들사이에 Arrow로 MarkovChain을 표현하면, Probability parameter는 각 Arrow에 연합되어 있고, 이것은 특정 residue다음에 나오는 특정 residue의 Probability를 결정한다. 이 Probability parameter를 TransitionProbability라고 표현하며, a(st)로 표기할때
a(st) = P (xi = t | x(i-1) = s)
P(x) = P (x(L), x(L-1), ..., x1)
= P (x(L) | x(L-1), ..., x1) P (x(L-1) | x(L-2), ..., x1) ... P(x1)
P(xi|x(i-1), ..., x1) = P(xi|x(i-1)) = a(x(i-1)xi)
P(x) = P (x(L) | x(L-1)) P (x(L-1) | x(L-2)) ... P(x2|x1) P(x1)
= P (x1) Production(i=2,L) ( a(x(i-1)xi) )서열 x가 있을 때 xi symbol은 그 전단계의 symbol x(i-1)에 의존하지, 전체의 이전서열에 의존하지 않는다는것.
Modelling the beginning and end of sequences
Start state {Begin} and End state {End}의 첨가.
P(x1=s) = a{Begin}
P({End} | x(L)=t) = a(t{End})
Using MarkovChain for discrimination
임의의 서열에 대해 CpG_island인지를 구분짓기 위한 MarkovChain. CpG_island인 서열 (+)와 아닌 서열(-)에 대해 각각 특정서열 다음에 어떤서열이 나올 확률을 MaximumLikelihood estimation으로 구한다. (여기서 data set이 작으면 BayesianEstimation을 쓸 수 있으나, 충분히 많을 경우 ML도 적당하다.)
+ A C G T - A C G T ----------------------------- ----------------------------- A 0.180 0.274 0.426 0.120 A 0.300 0.205 0.285 0.210 C 0.171 0.368 0.274 0.188 C 0.322 0.298 0.078 0.302 G 0.161 0.339 0.375 0.125 G 0.284 0.246 0.298 0.208 T 0.079 0.355 0.384 0.182 T 0.177 0.239 0.292 0.292
%. G following C is lower than that for C following G
discrimination을 위해서 LogOddsRatio를 계산하면,
P(x|model+) a+(x(i-1)x)
S(x) = log------------ = SUM(i=1,L) { log----------- } = SUM(i=1,L) { β(x(i-1)xi }
P(x|model-) a-(x(i-1)x)β table은 다음과 같다. (base 2 logarithm were used)
β A C G T ----------------------------- A -0.740 0.419 0.580 -0.803 C -0.913 0.302 1.812 -0.685 G -0.624 0.461 0.331 -0.730 T -1.169 0.573 0.393 -0.679
이로부터, CpG_island에 대한 resonable discrimination이 가능하다.
Extensions to MarkovChain
More complex MarkovChain
High order Markov chains
지금까지의 MarkovChain은 바로 이전단계 n event를 이용한다. --> order 1.
n th order 와 1st order는 이론적으로 equivalent하나, 때로 high order model이 보다 유용할때가 있다.
Finding prokaryotic genes
ORF 에서 non-coding ORF와 real gene을 구분하고자 할때 3th order MarkovChain을 쓰면 DNA codon이 thriplet이기에 좋은 결과를 얻을 수 있다.
3th order MarkovChain은 64 state.