分子生物情報学(5)
RNAの二次構造予測
阿久津 達也
京都大学 化学研究所
バイオインフォマティクスセンター
確率文脈自由文法と
RNA二次構造予測

確率文脈自由文法


HMM（正規文法に相当）の
文脈自由文法への拡張
構文解析アルゴリズム


U A U G C U C C G C A C G A
V
CYKアルゴリズム
C
学習アルゴリズム


RNA Sequence
U
内側外側アルゴリズム
RNA配列アライメント、RNA
二次構造予測への応用
U
A
C
C
G
G
C
U
A
Secondary
Structure of
RNA
C
G
A
RNA二次構造予測問題（基本
バージョン）の定義


ベースペア B={{a,u},{g,c}｝
RNA二次構造



スコア関数



M={(i,j)|1≤i<j≤n,{ai,aj}∈B}、かつ
i ≤h ≤j ≤k となる (ai,aj) ,(ah,ak) ∈M
は無い
μ(ai,aj)=1 if {ai,aj} ∈B
μ(ai,aj)=0 otherwise
最適RNA二次構造
 Σ(i,j)∈M μ(ai,aj) が最大となるM
ベースペア
a
u
g
c
二次構造
agagcu
agagcu
RNA二次構造
RNA二次構造予測のための
動的計画法アルゴリズム


入力配列：a=a1…an
アルゴリズム
S (i, j ) 
S (i  1, j 1)   (ai, aj )
maxmax{ S (i, k 1)  S (k , j) }
 ik  j

j-1
j
i+1
i
時間計算量
テーブルのサイズO(n2)
 1個のS(i,j)の計算O(n)
⇒ O(n3)時間

i
k-1 k
j
確率文脈自由文法とRNA二次
構造の対応関係
文法規則
X→ε
X→a
X→u
X→g
X→c
X→YZ
X→ a Y u
X→ u Y a
X→ g Y c
X→ c Y g
スコア
Xのスコア
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
score(X)+score(Y)
score(Y)+1
score(Y)+1
score(Y)+1
score(Y)+1
文法における生成規則と
二次構造の対応
X→ a
X→ YZ
X→ a Y u
Y
a
Z
i
k-1 k
j
Y
a
u
PseudoKnot つき二次構造予測


O(n4) 時間以上かかる
文脈自由文法より高次の文法（木文法など）が必要
講義のまとめ：
HMMと確率文脈自由文法の比較

文法



構文解析



HMM: Viterbiアルゴリズム
SCFG: CYKアルゴリズム
学習 (EM アルゴリズム)



HMM: 正規文法
SCFG: 文脈自由文法
HMM: Baum-Welch アルゴリズム
SCFG: 内側外側アルゴリズム
参考文献

阿久津、浅井、矢田 訳： バイオインフォマティクス －確率モデ
ルによる遺伝子配列解析―、医学出版、2001

SCFG-50DE1

SCFG-50FF3

1188000-13-02 SCFG－90 ガード