情报生命科学特别讲义课件

1、情報生命科学特別講義III（11） RNA二次構造予測阿久津達也京都大学化学研究所講義予定第回:文字列第回：文字列構造第回：込基第回：近似文字列第回：配列第回：配列解析第回：進化系統樹推定第回：木構造比較：順序木第回：木構造比較：無順序木第回：文法圧縮第回：RNA二次構造予測第回：質立体構造予測比較第回：固定部分k木第回：比較列挙第回：RNA二次構造予測RNA二次構造予測RNA二次構造予測（基本版）入力： RNA配列 a=a1an出力： 以下満、(i,j)M (ai,aj) 最小塩基対 集合 M=(i,j)|1i+1jn,ai,ajB(ai,aj) ,(ah,ak) M i h j k 存在塩

2、基対： B=a,u,g,c関数（最単純）(ai,aj)= -1 if ai,aj B(ai,aj)=0 otherwise最小二次構造、最小最適二次構造g,u 塩基対含場合AUGC塩基対AGAGCUAGAGCU二次構造二次構造RNA二次構造二種類表現 RNA二次構造例RNA配列Nussinov 予測（Nussinov）入力配列： a=a1an動的計画法初期化最適解（ 塩基対個数）説明 Nussinov解析定理： 上記 O(n3) 時間最適解計算略証： W(i,j) O(n2)。1個要素計算O(n)時間（最後行）。 RNA二次構造予測確率文脈自由文法RNA二次構造予測確率文脈自由文法 （）文法表

3、現 XaYu, XXY 、SaSu, SSS 正式RNA場合、置換必要確率文脈自由文法（SCFG）： 導出確率最大構文解析木計算 確率代用RNA二次構造予測確率文脈自由文法 （）最大（確率最大）構文解析木 最適二次構造実際、NussinovCYK（文脈自由文法構文解析）類似Valiant利用Akutsu: J. Comb. Opt. 1999 Zakov et al.: Alg. Mol. Biol. 2011二次構造予測計算量改良文脈自由文法構文解析高速行列乗算基 Valiant 用 O(n) 時間O(n) nn 行列乗算計算時間高速行列乗算基RNA二次構造予測基本的 Valiant 適用、

4、行列乗算基本演算 (+,) (max,+) 変必要(max,+) 行列演算、少 O(n3) 良O(n3(log log n)/(log n)1/2)時間 Akutsu: J. Comb. Opt. 1999O(n3(log3(log n)/log n)時間 Zakov et al.: Alg. Mol. Biol. 2011SCFG内側Akutsu: J.Comb.Opt. 1999、外側Zakov et al.:Alg. Mol. Boil. 2011 (+,)演算済 O(n) 時間可能Four-Russian 基RNA二次構造予測O(n3/log n)時間 Frid, Gusfield:

5、Proc. WABI 2009 二十数年 2.3737 2.3736 、2.327 改善Wiliianms: Proc. STOC 2012Valiant概略（）基本的分割統治W(i,j)=k W(i,k)W(k+1,j) 計算（青赤乗算）高速化行列乗算適用、複数 W(i,j) 計算実行左下三角計算不要Valiant概略（）基本戦略白黄計算済、青計算（青一部計算済）部分行列積計算後、青加算（結果緑）緑黄色行列作、再帰計算青計算（左下白不要OK）高速乗算再帰計算Valiant概略（）時間計算量T2(n)= T2(n/2)+ 2T3(3n/4)+ T4(n)+ O(n2)T3(n)= M(n/3)

6、+ 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)nn行列乗算計算量： 下図時間計算量：Valiant概略（）二次構造予測平均計算時間改良Wexler et al.:J. Comp. Biol. 2007 平均計算時間改良： 最悪時間計算量 O(n3) 本質的改良極困難高速行列乗算実用的Nussinov他動的計画法平均的 O(n3) 時間平均計算時間改良 Wexler et al.:J. Comp. Biol. 2007計算Valiant 型行列乗算改良： 必要 k 改良詳細（）

7、W(i,j): 部分配列 ai.j 対最適解 V(i,j): aiaj塩基対結合場合最適解詳細（）前述 ji+4 場合考簡略化定理： V(i,j)V(i,k)+W(k+1,j) k (i k j V(i,j)+W(j+1,j) V(i,k)+W(k+1,j) 成立必要 k 計算定理： V(i,j)V(i,k)+W(k+1,j) k (i k 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 )：塩基対作減場所 k 候補V(i,j)W(i,j) j 以降 k 候補採用(n): 長 n 配列対 L

8、大最大値期待値定理： CandidateFold 平均的 O(n2 (n) 時間動作妥当現実的仮定（polymer-zeta property） (n) 定数知 RNA二次構造予測平均的 O(n2) 時間実行可能単純擬似二次構造予測Akutsu: Disc. Appl. Math. 2000擬似擬似i h j k 満塩基対 (ai,aj) ,(ah,ak) M 単純擬似：下図示擬似（定義省略） AGAGCU単純擬似対動的計画法 （） W(i,j) 加、種類用WL(i,j,k): ai aj 塩基対場合 WR(i,j,k): aj ak 塩基対場合 WM(i,j,k): ai , aj, ak

9、塩基対場合 単純擬似対動的計画法（）WL(i,j,k) 計算説明複雑擬似二次構造予測木接合文法基方法 Uemura et al.: Theoret. Comp. Sci. 1999O(n4) 時間、 O(n5) 時間（再帰的構造含場合）PKNOTS Rivas, Eddy: J. Mol. Biol. 1999擬似組合構造対応、O(n6)時間平面的擬似： NP困難 Akutsu: Disc. Appl. Math. 2000RNA二次構造予測動的計画法 O(n3)時間Valiant 利用少改善Polymer-zeta property仮定、平均的O(n2) 時間擬似RNA二次構造予測計算量対象擬似複雑依存補足Valiant、RNA構造同時予測問題結合RNA二次構造