Nussinov Algorithm for maximum number of possible base-pairs

Initialization:
for \( i=1 \) to \( L \)
\[ M(i,i) = 0, \]
Recurtion:
for \( \ell=1 \) to \( L-1 \), for \( i=1 \) to \( L-\ell\), \( j=i+\ell \)
\[
M(i,j) = \max
\left[ \begin{array}{l}
M(i+1,j) \\
M(i,j-1) \\
M(i+1,j-1) + \delta(i,j)\\
\max_{h} M(i,h) + M(h+1,j)
\end{array} \right.
\]

Traceback of Nussinov Algorithm

初期化： \((1,L)\)をスタックにpushする．
再帰： スタックが空になるまで繰り返す．
— pop \((i,j)\)
— if \(i>=j\) continue;
— else if \(\gamma(i+1,j) = \gamma(i,j)\)， \((i+1,j)\) を push;
— else if \(\gamma(i,j-1) = \gamma(i,j)\)， \((i,j-1)\) を push;
— else if \(\gamma(i+1,j-1)+\delta_{i,j} = \gamma(i,j)\),
—— 塩基対\((i,j)\)を記録．
—— \((i+1,j-1)\) を push
else for \(k=i+1\) to \(j-1\): if \(\gamma(i,k)+\gamma(k+1,j)=\gamma(i,j)\):
—— \((k+1,j)\) を push
—— \((i,k)\) を push
—— break

Production rules of the SCFG associated to the above Nassinov Algorithm

\[
\begin{eqnarray}
M &\longrightarrow xM & : P(M\rightarrow xM), & x\in\{a,c,g,u\}\\
M &\longrightarrow Mx & : P(M\rightarrow Mx), & x\in\{a,c,g,u\}\\
M &\longrightarrow xM\bar{x} & : P(M\rightarrow xM\bar{x}), &(x,\bar{x})\in \{(a,u),(c,g),(g,c),(u,a)\}\\
M &\longrightarrow MM & : P(M\rightarrow MM)\\
M &\longrightarrow x & : P(M\rightarrow x), &x\in\{a,c,g,u\}
\end{eqnarray}
\]

CYK Algorithm of the SCFG

Initialization:
for \( i=1 \) to \( L-1 \)
\[ \gamma(i,i,M) = P(M \rightarrow x_i) \]
Recurtion:
for \( \ell=1 \) to \( L-1 \), for \( i=1 \) to \( L-\ell\), \( j=i+\ell \)
\[
\gamma(i,j,M) = \max
\left[ \begin{array}{l}
\gamma(i+1,j,M) + \log P(M \rightarrow x_i M) \\
\gamma(i,j-1,M) + \log P(M \rightarrow M x_j) \\
\gamma(i+1,j-1,M) + \log P(M \rightarrow x_i M x_j) \\
\max_{h} \gamma(i,h) + \gamma(h+1,j) + \log P(M \rightarrow MM)
\end{array} \right.
\]

Inside algorithm of the SCFG

Initialization:
for \( i=1 \) to \( L-1 \)
\[ \alpha(i,i,M) = P(M \rightarrow x_i) \]
Recurtion:
for \( \ell=1 \) to \( L-1 \), for \( i=1 \) to \( L-\ell \), \( j=i+\ell \)
\[
\alpha(i,j,M) =
\left[ \begin{array}{l}
\alpha(i+1,j,M) P(M \rightarrow x_i M) \\
+ \alpha(i,j-1,M) P(M \rightarrow M x_j) \\
+ \alpha(i+1,j-1,M) P(M \rightarrow x_i M x_j) \\
+ \sum_{h=1}^{L-1} \alpha(i,h,M) \alpha(h+1,j,M) P(M \rightarrow MM)
\end{array} \right.
\]

Outside Algorithm of the SCFG

Initialization:
\[ \beta(1,L,M) = 1 \]
Recurtion:
for \( \ell=L-1 \) to \( 1 \), for \( i=1 \) to \( L-\ell \), \( j=i+\ell \)
\[
\beta(i,j,M) =
\left[ \begin{array}{l}
\beta(i-1,j,M) P(M \rightarrow x_{i-1} M) \\
+ \beta(i,j+1,M) P(M \rightarrow M x_{j+1}) \\
+ \beta(i-1,j+1,M) P(M \rightarrow x_{i-1} M x_{j+1}) \\
+ \sum_{h=1}^{i-1} \alpha(h,i-1,M) \beta(h,j,M) P(M \rightarrow MM) \\
+ \sum_{h=j+1}^{L} \alpha(j+1,h,M) \beta(i,h,M) P(M \rightarrow MM)
\end{array} \right.
\]

Partition Function on number of base-pairs

２次構造\(\sigma\)に含まれる塩基対の数\(N_\sigma\)を2次構造\(\sigma\)の自由エネルギーの符号を反転した値の乱暴な近似と考えると、２次構造\(\sigma\)の熱力学的確率は以下のボルツマン分布で与えられる。
\[ \begin{eqnarray}
P(\sigma |x) =\frac{1}{Z_N(x,\sigma)} e^{N_\sigma/k_N T}\\
Z_N(x,\sigma) = \sum_{\sigma \in S(x)} e^{N_\sigma/k_N T}
\end{eqnarray} \]
このボルツマン分布に対応するSCFGがどのようになるか、考察せよ