情報(bào)生命科學(xué)特別講義課件

1、情報(bào)生命科學(xué)特別講義III（11） RNA二次構(gòu)造予測(cè)阿久津達(dá)也京都大學(xué)化學(xué)研究所講義予定第回:文字列第回：文字列構(gòu)造第回：込基第回：近似文字列第回：配列第回：配列解析第回：進(jìn)化系統(tǒng)樹推定第回：木構(gòu)造比較：順序木第回：木構(gòu)造比較：無(wú)順序木第回：文法圧縮第回：RNA二次構(gòu)造予測(cè)第回：質(zhì)立體構(gòu)造予測(cè)比較第回：固定部分k木第回：比較列挙第回：RNA二次構(gòu)造予測(cè)RNA二次構(gòu)造予測(cè)RNA二次構(gòu)造予測(cè)（基本版）入力： 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関數(shù)（最単純）(ai,aj)= -1 if ai,aj B(ai,aj)=0 otherwise最小二次構(gòu)造、最小最適二次構(gòu)造g,u 塩基対含場(chǎng)合AUGC塩基対AGAGCUAGAGCU二次構(gòu)造二次構(gòu)造RNA二次構(gòu)造二種類表現(xiàn) RNA二次構(gòu)造例RNA配列Nussinov 予測(cè)（Nussinov）入力配列： a=a1an動(dòng)的計(jì)畫法初期化最適解（ 塩基対個(gè)數(shù)）説明 Nussinov解析定理： 上記 O(n3) 時(shí)間最適解計(jì)算略証： W(i,j) O(n2)。1個(gè)要素計(jì)算O(n)時(shí)間（最後行）。 RNA二次構(gòu)造予測(cè)確率文脈自由文法RNA二次構(gòu)造予測(cè)確率文脈自由文法 （）文法表

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

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

5、Proc. WABI 2009 二十?dāng)?shù)年 2.3737 2.3736 、2.327 改善Wiliianms: Proc. STOC 2012Valiant概略（）基本的分割統(tǒng)治W(i,j)=k W(i,k)W(k+1,j) 計(jì)算（青赤乗算）高速化行列乗算適用、複數(shù) W(i,j) 計(jì)算実行左下三角計(jì)算不要Valiant概略（）基本戦略白黃計(jì)算済、青計(jì)算（青一部計(jì)算済）部分行列積計(jì)算後、青加算（結(jié)果緑）緑黃色行列作、再帰計(jì)算青計(jì)算（左下白不要OK）高速乗算再帰計(jì)算Valiant概略（）時(shí)間計(jì)算量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行列乗算計(jì)算量： 下図時(shí)間計(jì)算量：Valiant概略（）二次構(gòu)造予測(cè)平均計(jì)算時(shí)間改良Wexler et al.:J. Comp. Biol. 2007 平均計(jì)算時(shí)間改良： 最悪時(shí)間計(jì)算量 O(n3) 本質(zhì)的改良極困難高速行列乗算実用的Nussinov他動(dòng)的計(jì)畫法平均的 O(n3) 時(shí)間平均計(jì)算時(shí)間改良 Wexler et al.:J. Comp. Biol. 2007計(jì)算Valiant 型行列乗算改良： 必要 k 改良詳細(xì)（）

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

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

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