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

[Recursion]으로 다음처럼 계산한다.

  1. add unpaired position i onto bast structure for subsequence i+1, j
  2. add unpaired position j onto best structure for subsequence i, j-1
  3. add i, j pair onto best structure found for subsequence i+1, j-1
  4. combine two optimal substructures i, k and k+1, j

delta(i,j)를 정의하고 i, j가 base pair이면 1, 아니면 0을 준다. 

Initialisation:    gamma(i, i-1) = 0   for i = 2 to L;
                   gamma(i, i) = 0     for i = 1 to L.

Recursion: starting with all subsequences of length 2, to length L:
                 { gamma(i+1, j),
gamma(i,j) = max { gamma(i, j-1),
                 { gamma(i+1, j-1) + delta(i,j),
                 { max(i<k<j, [ gamma(i,k) + gamma(k+1,j) ].

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]

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

See also ScfgNussinovAlgorithm (StochasticContextFreeGrammar-based algorithm)

web biohackers.net