情報生命科学特別講義III （11） RNA二次構造予測

Presentation on theme: "情報生命科学特別講義III （11） RNA二次構造予測"— Presentation transcript:

1 情報生命科学特別講義III （11） RNA二次構造予測
阿久津　達也 京都大学　化学研究所 バイオインフォマティクスセンター

2 講義予定 第１回: 文字列マッチング 第２回： 文字列データ構造 第３回： たたみ込みとハッシュに基づくマッチング
第１回:　文字列マッチング 第２回：　文字列データ構造 第３回：　たたみ込みとハッシュに基づくマッチング 第４回：　近似文字列マッチング 第５回：　配列アラインメント 第６回：　配列解析 第７回：　進化系統樹推定 第８回：　木構造の比較：順序木 第９回：　木構造の比較：無順序木 第１０回：　文法圧縮 第１１回：　RNA二次構造予測 第１２回：　タンパク質立体構造の予測と比較 第１３回：　固定パラメータアルゴリズムと部分k木 第１４回：　グラフの比較と列挙 第１５回：　まとめ

3 RNA二次構造予測

4 RNA二次構造予測 RNA二次構造予測（基本版） 塩基対 入力： RNA配列 a=a[1]…a[n] 出力： 以下を満たし、スコア 二次構造
U G C 塩基対 二次構造 二次構造でない RNA二次構造予測（基本版） 入力： RNA配列 a=a[1]…a[n] 出力： 以下を満たし、スコア 　Σ(i,j)∈M μ(a[i],a[j]) が最小となる塩基対 の集合 M={(i,j)|1≤i+1<j≤n,{a[i],a[j]}∈B} (a[i],a[j]) ,(a[h],a[k]) ∈M となる i ≤h ≤j ≤k が存在しない 塩基対： B={{a,u},{g,c}｝ スコア関数（最も単純なもの） μ(a[i],a[j])= -1 if {a[i],a[j]} ∈B μ(a[i],a[j])=　0 otherwise スコアが最小でないものも二次構造とよび、最小のものを最適二次構造とよぶこともある {g,u} も塩基対に含まれる場合がある

5 RNA二次構造の二種類の表現

6 RNA二次構造の例 RNA配列

7 Nussinovアルゴリズム

8 予測アルゴリズム（Nussinovアルゴリズム）
入力配列： a=a[1]…a[n] 動的計画法 初期化 メインループ 最適解（＝ －塩基対の個数）

9 アルゴリズムの説明 メインループ

10 Nussinovアルゴリズムの解析 定理： 上記アルゴリズムは O(n3) 時間で最適解を計算
略証： テーブル W(i,j) のサイズはO(n2)。1個のテーブル要素の計算にO(n)時間（最後の行）。

11 RNA二次構造予測と 確率文脈自由文法

12 RNA二次構造予測と確率文脈自由文法 （１）
確率文脈自由文法（SCFG）： 導出確率が最大となる構文解析木を計算 ⇒ 確率の代わりにスコアを用いる 文法表現としては X→aYu, X→XY などではなく、S→aSu, S→SS などが正式 RNAの場合はスコアは１ではなく、－１に置き換えることが必要

13 RNA二次構造予測と確率文脈自由文法 （２）
スコア最大（≒確率最大）の構文解析木 ⇔ 最適二次構造 実際、NussinovアルゴリズムはCYKアルゴリズム（文脈自由文法の構文解析アルゴリズム）に類似

14 Valiantアルゴリズムの利用 [Akutsu: J. Comb. Opt. 1999] [Zakov et al.: Alg. Mol. Biol. 2011]

15 二次構造予測の計算量の改良 文脈自由文法の構文解析 高速行列乗算に基づくRNA二次構造予測
高速行列乗算に基づく Valiant アルゴリズムを用いれば O(nω) 時間 O(nω) は n×n の行列乗算にかかる計算時間 高速行列乗算に基づくRNA二次構造予測 基本的に Valiant アルゴリズムを適用 しかし、行列乗算の基本演算を (+,×) から (max,+) に変える必要 (max,+) の行列演算は、ほんの少し O(n3) より良くなるだけ O(n3((log log n)/(log n))1/2)時間 [Akutsu: J. Comb. Opt. 1999] O(n3(log3(log n))/log n)時間 [Zakov et al.: Alg. Mol. Biol. 2011] SCFGの内側アルゴリズム[Akutsu: J.Comb.Opt. 1999]、外側アルゴリズム[Zakov et al.:Alg. Mol. Boil. 2011] は(+,×)演算で済むので O(nω) 時間で可能 Four-Russian アルゴリズムに基づくRNA二次構造予測 O(n3/log n)時間 [Frid, Gusfield: Proc. WABI 2009] ω は二十数年ぶりに から へ、さらに、2.327 へ改善された　[Wiliianms: Proc. STOC 2012]

16 Valiantアルゴリズムの概略（１） 基本的に分割統治 W(i,j)=Σk W(i,k)×W(k+1,j) の計算（青のベクトルと赤の
　　ベクトルの乗算）を 　　高速化 行列乗算を適用する 　　ため、複数の W(i,j) 　　の計算をまとめて 　　実行 左下三角は計算不要

17 Valiantアルゴリズムの概略（２） 基本戦略 白と黄が計算済みとして、青を計算（青は一部計算済み）
ピンクの部分の行列積を計算後、青と加算（⇒結果は緑） 緑と黄色からなる行列を作り、再帰計算により青を計算 　　　　　　　　　　　　（左下の白は不要なのですべて０としてOK） 高速 乗算 再帰計算

18 Valiantアルゴリズムの概略（３） 時間計算量 T2(n)= T2(n/2)+ 2T3(3n/4)+ T4(n)+ O(n2)
T3(n)= M(n/3)+ T2(2n/3)+ O(n2) T4(n)= 2M(n/4)+ T2(n/2)+ O(n2) ⇒ T2(n)= 4T2(n/2)+ 4M(n/4)+ O(n2) M(n)はn×n行列の乗算の計算量

19 Valiantアルゴリズムの概略（４） メインルーチン： 下図のとおり 時間計算量：

20 二次構造予測の 平均計算時間の改良 [Wexler et al.:J. Comp. Biol. 2007]

21 最悪の時間計算量の O(n3) からの本質的改良は極めて困難 高速行列乗算は実用的でない
平均計算時間の改良： アイデア 最悪の時間計算量の O(n3) からの本質的改良は極めて困難 高速行列乗算は実用的でない Nussinovアルゴリズムや他の動的計画法アルゴリズムは平均的にも O(n3) 時間かかる ⇒　平均計算時間の改良 [Wexler et al.:J. Comp. Biol. 2007] ブランチループの計算がボトルネックとなっていた Valiant 型のアルゴリズムでは行列乗算により改良 アイデア： 必要な k のみをチェックすることにより改良

22 詳細なエネルギーモデル（１） W(i,j): 部分配列 a[i..j] に対する最適解
V(i,j): a[i]とa[j]が塩基対として結合する場合の最適解

23 詳細なエネルギーモデル（２） 前述のモデルを j≧i+4 の場合のみを考えて簡略化
定理： V’(i,j)≧V’(i,k)+W’(k+1,j) がある k (i < k < j)について 　　　　成立すれば、すべての j’>j について 　　　　V’(i,j)+W’(j+1,j’) ≧ V’(i,k)+W’(k+1,j’) が成立

24 必要な k のみの計算 定理： V’(i,j)≧V’(i,k)+W’(k+1,j) がある k (i < k < j)について
　　　　成立すれば、すべての j’>j について 　　　　V’(i,j)+W’(j+1,j’) ≧ V’(i,k)+W’(k+1,j’) が成立 V’(i,j’) の計算においては、V’(i,j)≦V’(i,k)+W’(k+1,j) (i < k < j) が成立する j について計算すれば良い ( j’>j ) アイデア：塩基対を作ることによりエネルギーが減る場所のみを k の候補とする

25 アルゴリズム V’(i,j)<W’(i,j) となる j のみを以降では k の候補として採用
ψ(n): 長さ n の配列に対する L の大きさの最大値の期待値 定理： CandidateFold は平均的に O(n2 ψ(n)) 時間で動作 妥当な現実的な仮定（polymer-zeta property）のもとで ψ(n) は定数になることが知られている ⇒ RNA二次構造予測は平均的に O(n2) 時間で実行可能

26 単純擬似ノットつき 二次構造の予測 [Akutsu: Disc. Appl. Math. 2000]

27 擬似ノット 擬似ノット i ≤h ≤j ≤k を満たす塩基対ペア (a[i],a[j]) ,(a[h],a[k]) ∈M A G C U
単純擬似ノット：　下の図に示される擬似ノット（定義は省略）

28 単純擬似ノットに対する動的計画法 （１） もとの W(i,j) に加え、３種類のテーブルを用いる
WL(i,j,k): a[i] と a[j] が塩基対をなす場合 WR(i,j,k): a[j] と a[k] が塩基対をなす場合 WM(i,j,k): a[i] , a[j], a[k] のどのペアも塩基対をなさない場合

29 単純擬似ノットに対する動的計画法（２） WL(i,j,k) 計算の説明 より複雑な擬似ノットつき二次構造の予測
木接合文法に基づく方法 [Uemura et al.: Theoret. Comp. Sci. 1999] O(n4) 時間、 O(n5) 時間（再帰的構造を含む場合） PKNOTSアルゴリズム [Rivas, Eddy: J. Mol. Biol. 1999] 擬似ノットを組み合わせた構造にも対応、O(n6)時間 平面的擬似ノット： NP困難 [Akutsu: Disc. Appl. Math. 2000]

30 まとめ RNA二次構造予測 擬似ノットつきRNA二次構造予測 補足 動的計画法により O(n3)時間
Valiant アルゴリズムなどの利用により少しだけ改善 Polymer-zeta propertyを仮定すると、平均的にO(n2) 時間 擬似ノットつきRNA二次構造予測 計算量は対象とする擬似ノットの複雑さに依存 補足 Valiantアルゴリズムは、RNAアラインメント・構造同時予測問題や結合RNA二次構造予測問題にも適用可 [Zakov et al.: Alg. Mol. Biol. 2011] 擬似ノットなしRNA二次構造予測の（クリークによる）下限は Ω(nω-ε) 時間[Abboud et al.: FOCS 2015]。現状では上限 とのギャップ。 ⇒　肯定的に解決された(O(n2.8…) time) [Bringmann et al.: FOCS 2016]