## page was renamed from NussinovAlgorithm
RnaSecondaryStructurePrediction에서 DynamicProgramming에 기반한 [RNA] 2차구조 예측 [Algorithm]. 정확한 예측은 무리. 그러나 짧은 [RNA]에 대해서는 비교적 정확한 결과를 제공한다.

본 계산은 [Recursion]을 이용한다. 짧은 서열에 대해 최적구조를 계산하고, 이를 크게 확장시켜나간다. 재귀의 키포인트는 짧은 서열에서의 최적구조 i, j는 다음의 4가지 종류만이 있다는 점이다.
 1. add unpaired position i onto bast structure for subsequence i+1, j
 1. add unpaired position j onto best structure for subsequence i, j-1
 1. add i, j pair onto best structure found for subsequence i+1, j-1
 1. combine two optimal substructures i, k and k+1, j

길이 L의 서열 x
{{{#!latex
$$ x_1, \ldots , x_L $$
}}}
에서 base pairing 이 일어나는 위치는 구하는 알고리즘은 다음의 두 단계로 이루어진다.

== Fill stage ==
{{{#!latex 
$$ \delta(i,j) $$ }}}를 정의하고 i, j가 complementary base pair이면 1, 아니면 0을 준다. 그리고는 점수 {{{#!latex 
$$ \gamma(i,j) $$ }}}를 다음처럼 구한다.

Initialisation
{{{#!latex
$$ \gamma(i, i-1) = 0 \textrm{  for  } i = 2 \textrm{  to  } L; $$
$$ \gamma(i, i) = 0 \textrm{  for  } i = 1 \textrm{  to  } L; $$
}}}

Recursion: starting with all subsequences of length 2, to length L:
{{{#!latex
$$ \gamma(i,j) = \textrm{max} \left \{ \begin{array}{ll} 
         \gamma(i+1,j), \\ 
         \gamma(i, j-1), \\
         \gamma(i+1, j-1) + \delta(i,j), \\
         \textrm{max}_{i<k<j} \biggl[ \gamma(i,k) +\gamma(k+1,j) \biggl] 
      \end{array} \right    $$
}}}

== Traceback stage ==

trace back은 [[Stack]]을 써서 다음처럼 한다.

{{{
Initialisation
 Push(l,L) onto stack.

Recursion: Repeat until stack is empty:
     - pop (i,j)
     - if i >= j continue;
       else if gamma(i+1,j) = gamma(i,j), push (i+1, j);
       else if gamma(i,j-1) = gamma(i,j), push (i, j-1);
       else if gamma(i+1, j-1) + delta(i,j) = gamma(i,j):
            - record i, j base pair.
            - push (i+1, j-1).
       else for k = i+1 to j-1: if gamma(i,k) + gamma(k+1, j) = gamma(i,j):
            - push (k+1, j).
            - push (i,k).
            - break.
}}}

[[Python]]Code: [Nussinov.py], UnitTest code [TestNussinov.py] 

 (''2001-12-11 현재 완료하긴 했는데 교재랑 결과값이 다르게 나옵니다. 책대로라면, 서열 GGGAAAUCC 에 대해 {{{[(2,9),(3,8),(4,7)]}}}가 나와야하는데 {{{[(2,9),(3,8),(6,7)]}}}이 출력됩니다. 책 그림을 봐도 마지막부분에 1에서 1로 가야하는데 0 으로 가버리네요'')
----
See also ScfgNussinovRnaFoldingAlgorithm (StochasticContextFreeGrammar-based algorithm)