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.