Differences between revisions 2 and 8 (spanning 6 versions)
⇤ ← Revision 2 as of 2006-02-20 21:51:57 →
Size: 2104
Editor: 127
Comment:
← Revision 8 as of 2011-08-03 11:01:17 → ⇥
Size: 2835
Editor: localhost
Comment: converted to 1.6 markup
Deletions are marked like this. Additions are marked like this.
Line 1: Line 1:
#acl yong27:admin ## page was renamed from NussinovAlgorithm
Line 4: Line 4:
[Recursion]으로 다음처럼 계산한다. 본 계산은 [Recursion]을 이용한다. 짧은 서열에 대해 최적구조를 계산하고, 이를 크게 확장시켜나간다. 재귀의 키포인트는 짧은 서열에서의 최적구조 i, j는 다음의 4가지 종류만이 있다는 점이다.
Line 10: Line 10:
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.		 길이 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; $$
}}}
Line 16: Line 28:
                 { 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) ].		 {{{#!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 $$
Line 22: Line 37:
trace back은 ["Stack"]을 써서 다음처럼 한다. == Traceback stage ==

trace back은 [[Stack]]을 써서 다음처럼 한다.
Line 24: Line 42:
Initialisation: Push(l,L) onto stack. Initialisation
 Push(l,L) onto stack.
Line 40: Line 59:
["Python"]Code: [Nussinov.py], UnitTest code [TestNussinov.py] [[Python]]Code: [Nussinov.py], UnitTest code [TestNussinov.py]
Line 42: Line 61:
 (''DeleteMe 12월 11일 현재 완료하긴 했는데 교재랑 결과값이 다르게 나옵니다. 책대로라면, 서열 GGGAAAUCC 에 대해 {{{[(2,9),(3,8),(4,7)]}}}가 나와야하는데 {{{[(2,9),(3,8),(6,7)]}}}이 출력됩니다. 책 그림을 봐도 마지막부분에 1에서 1로 가야하는데 0 으로 가버리네요'')  (''2001-12-11 현재 완료하긴 했는데 교재랑 결과값이 다르게 나옵니다. 책대로라면, 서열 GGGAAAUCC 에 대해 {{{[(2,9),(3,8),(4,7)]}}}가 나와야하는데 {{{[(2,9),(3,8),(6,7)]}}}이 출력됩니다. 책 그림을 봐도 마지막부분에 1에서 1로 가야하는데 0 으로 가버리네요'')
Line 44: Line 63:
See also ScfgNussinovAlgorithm (StochasticContextFreeGrammar-based algorithm) See also ScfgNussinovRnaFoldingAlgorithm (StochasticContextFreeGrammar-based algorithm)

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

본 계산은 [Recursion]을 이용한다. 짧은 서열에 대해 최적구조를 계산하고, 이를 크게 확장시켜나간다. 재귀의 키포인트는 짧은 서열에서의 최적구조 i, j는 다음의 4가지 종류만이 있다는 점이다.

  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

길이 L의 서열 x $$ x_1, \ldots , x_L $$

에서 base pairing 이 일어나는 위치는 구하는 알고리즘은 다음의 두 단계로 이루어진다.

Fill stage

$$ \delta(i,j) $$

를 정의하고 i, j가 complementary base pair이면 1, 아니면 0을 준다. 그리고는 점수 $$ \gamma(i,j) $$

를 다음처럼 구한다.

Initialisation $$ \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: $$ \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.

PythonCode: [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)

NussinovRnaFoldingAlgorithm (last edited 2011-08-03 11:01:17 by localhost)