Probability of RNA 2D structure
RNA配列\(x\)が取りうる全ての２次構造全体の空間を\(S(x)\)としよう。\(S(x)\)は巨大で、\(x\)が100塩基でもその大きさは天文学的数字となる。
与えられた\(x\)が特定の２次構造\(\sigma_0\)を取る条件付確率は式\eqref{eq:RNA_Boltzmann}のボルツマン分布で与えられる。
ここで、\(E(\sigma,x,\theta)\)は\(x\)の２次構造\(\sigma\)における自由エネルギーであり、もっとも広く用いられているエネルギーモデルでは、式\eqref{eq:RNA_energy}のように、２次構造に含まれる全てのループ（塩基対と主鎖で囲まれた領域）の自由エネルギーの和で表される。
\(Z(x,\theta)\)は分配関数で、式\eqref{eq:RNA_partition}のように全ての構造に対するBoltzmann因子の和で与えられる。
\[ \begin{eqnarray}
P(\sigma_0 |x,\theta) = \frac{1}{Z(x,\theta)} e^{-E(\sigma_0,x,\theta)/kT}
\tag{R.1.1.1} \label{eq:RNA_Boltzmann}
\end{eqnarray} \]
\[
E(x,\sigma,\theta_e) = \sum_{L \in \sigma} E_L
\tag{R.1.1.2} \label{eq:RNA_energy}
\]
\[\begin{eqnarray}
Z(x,\theta) = \sum_{\sigma \in S(x)} e^{-E(\sigma,x,\theta)/kT}
\tag{R.1.1.3} \label{eq:RNA_partition}
\end{eqnarray} \]
各2次構造に対する自由エネルギーを求めるモデル（パラメータ\(\theta\)）が与えられれば、\eqref{eq:RNA_Boltzmann}から各2次構造をとる確率が求められるわけである。
さらに、最も自由エネルギーの低い2次構造、最小自由エネルギー（MFE）構造は最も確率の高い構造であるから、それを求めることも重要である。
2次構造全体の空間\(S(x)\)は巨大であるから、例え2次構造の自由エネルギーを求めるモデルが与えられたとしても、それらについてのボルツマン因子を合計して分配関数を求める式\eqref{eq:RNA_partition}を計算するのは容易ではない。最もボルツマン因子の大きい構造、最小自由エネルギー構造を求めることも容易ではないと思えるかもしれない。しかし、シュードノットの無い構造だけを考慮することにすれば、十分に合理的な自由エネルギーモデルに関して、塩基配列長\(L\) に対して\(O(L^3)\) の計算時間で分配関数、最小自由エネルギー構造を計算できる動的計画法アルゴリズムが存在する。
Let \(S(x)\) be the space of all the possible secondary structure (2D structure) of RNA sequence \(x\).\(S(x)\) is huge, even for an RNA sequence of the length 100nt.
The conditional probability that a given RNA sequence \(x\) forms 2D structure \(\sigma_0\) is given by \eqref{eq:RNA_Boltzmann}.
\(\theta_e\) is an energy model, \(E(x,\sigma,\theta_e)\) is the free energy given as the sum of the free energy of every loop \(L\) in \(\sigma\),
and \(Z(x,\theta_e)\) is the partition function, sum of the Boltzmann factors of all the possible 2D structures
For Turner energy model, McCaskill Algorithm is known as the algorithm that calculated the partition function \(Z(x)\) by dynamic programming (DP).
RNA2次構造のエネルギーと確率を求めるためには、以下の要素が必要である。
特定の2次構造の自由エネルギーを求めるためのモデル（パラメータ）
ボルツマン因子を2次構造全体の空間で合計して分配関数を求めるアルゴリズム
最も自由エネルギーの低い構造（＝確率の高い構造）を求めるアルゴリズム
2D structure prediction
Given an RNA sequence \(x\), predict 2D structure \(\sigma\).
Clearly, the maximum likelihood estimator (MLE) of \(\sigma\) that maximize \(p(\sigma|x,\theta_e)\)is the minimum free energy (MFE) structure that maximize \(E(x,\sigma,\theta_e)\).
More on 2D structure prediction, including Maximum Expected Accuracy, go to 2D structure prediction.
Log Linear Model (Exponential Family)
Logarithm of (1) can be rewritten in the form of log linear model (exponential family)
\[
\log p(\sigma|x,\theta_e) = \exp \left[ \sum_i \theta_e^i y_i(x,\sigma) – \psi(x,\theta_e) \right]
\]
where \(\theta_e^i\) is the energy parameter, the free energy of a loop of type \(i\) (stack by AU-GC, for example), and \(y_i\) is the number of the type \(i\) loops observed in the structure \( (x,\sigma) \). \(\psi\) is the logarithm of the partition function \(Z\).
\[
\psi(x,\theta_e) = Z(x) = \log \sum_{\sigma} \exp \left[ \sum_i \theta_e^i y_i(x,\sigma) \right]
\]
Stochastic Context Free Grammar (SCFG)
RNA 2D structure can be modeled by SCFG, which is a generative grammar and gives the joint probability of the RNA sequences and parsing. If the grammar is unambiguous, the parsing \(\sigma_p\) corresponds 1-to-1 to the 2D structure \(\sigma\). For Chomsky normal form of SCFG (not actually used for RNA), that joint probability can be written as
\[
p(x,\sigma_p|M_{SCFG}) = \prod_{v,y,z} P(W_v -> W_y W_z)^{n_1(v,y,z)} \prod_{v,a} P(W_v ->a)^{n_2(v,a)}
\hspace{3cm} (2)
\]
There are constraints in probability of production rules,
\[ \begin{align}
\sum_{y,z} P(W_v -> W_y W_z) = 1\\
\sum_{a} P(W_v ->a) = 1
\end{align} \]
The logarithm of (2) can be written in a form of log linear model,
\[
\log p(x,\sigma_p|M_{SCFG}) = \exp \left[ \sum_i \theta_p^i t_i(x,\sigma_p) – \psi(x,\theta_p) \right]
\]