RnaSecondaryStructurePrediction 에서 [RNA] 2차구조 예측을 위한 StochasticContextFreeGrammar(SCFG) version of the NussinovRnaFoldingAlgorithm.
이 문제의 SCFG는 하나의 nonterminal S와 13개의 production rules를 가지고 있다.
S --> aS | cS | gS | uS (i unpaired),
S --> Sa | Sc | Sg | Su (j unpaired),
S --> aSu | cSg | gSc | uSa ( i,j pair),
S --> SS (bifurcation).
여기서의 maximum Probability parse는 maximum Probability secondary structure와 동등하다. 비록 SCFG를 위한 production rule은 NoamChomsky normal form은 아니지만, CYK [Parsing] algorithm은 쉽게 쓰여질 수 있다.
SCFG production의 probability parameters들을 p(aS), p(aSu)... 이런식으로 놓으면,
Initialisation: gamma(i,i-1) = - infinity for i = 2 to L; gamma(i,i) = max { log p(xiS) { log p(Sxi) for i = 1 to L. Recursion: for i=1 to L-1, j=j+1 to L; { gamma(i+1, j) + log p(xiS); gamma(i,j) = max { gamma(i, j-1) + log p(Sxj); { gamma(i+1, j-1) + log p(xiSxj); { max(i<k<j){ gamma(i,k) + gamma(k+1,j) + log p(SS).
계산이 끝나면, gamma(1,L)은 log likelihood log P(x, π|θ) of the optimal structure π given the SCFG model θ. traceback은 NussinovRnaFoldingAlgorithm에 소개된 방법 혹은, filling stage에서 추가적인 trace pointer를 설정하는 방법도 있다.
NussinovRnaFoldingAlgorithm과의 차이점이라면, 본 방법은 ProbabilisticModel이라는 점이다. 따라서 기존의 정보를 활용한 더 나은 parameter estimation이 가능하다.
- counting state transition in known [RNA] structure에 의한 estimation
unknown : ExpectationMaximisation and inside-outside training
그러나, 아직 [RNA] 구조적 특징들을 반영하지 못한다.
- Preferences for certain loop lengths
- Preferences for certain nearest neighbours in the structure caused by stacking interaction between neighbouring base pairs in a stem.