スライド 1

Size: px

Start display at page:

Download "スライド 1"

そうりんおいもり
5 years ago
Views:

1 生物配列解析アルゴリズム RNA 編渋谷東京大学医科学研究所ヒトゲノム解析センター ( 兼 ) 情報理工学系研究科コンピュータ科学専攻

2 今回の話題 RNA 構造予測アルゴリズム Nussikov Zuker Akutsu 準最適解アルゴリズム Eppstein 木の edit distance について

3 RNA とその構造 RNA ( リボ核酸 ) A(Adenine), C(Cytosine), G(Guanine), U(Uracil) の 4 種類の塩基からなる細胞内の塩基鎖 C-G, A-U, G-U( 弱い ) が結合する立体構造結合した塩基鎖は逆方向ホットトピック non-coding RNA RNA-seq 5' 5' bulge hairpin or palindrome 3' stacked pair bifurcation loop or multiple loop or branch stem loop or internal loop 5' 3'

4 RNA2 次構造 2 次構造とは (i:j) と (k:m) という結合がある場合に i<k ならば j>m であるような構造 (i:j): i 番目の塩基と j 番目の塩基の結合 i-j 4 計算をこれに限定すると探索空間が減るのでよくこれに限定した構造予測がなされる 4 以上

5 2 次構造の表現方法様々な表現方法がある root Tree Representation Circular Representation 5' 3'

6 二次構造ではない構造 Pseudo-knot 決して珍しいわけではない

7 古典的予測手法 : Nussinov et al. '78 (1) 最も結合するペアの数が多い二次構造を求めるアルゴリズム時間計算量 O(n 3 ) 空間計算量 O(n 2 ) Pseudo-knot は考えない branch も考えなければ O(n 2 ) にできる考え方長さ 1 の部分文字列は二次構造を持たないすべての長さ k の部分文字列に対して結合ペア数が最大の二次構造を求める長さ k-1 以下の部分文字列に対する解を利用して一つの解を得るのに O(n) 対応する部分文字列の数はn-k+1 k=n まで順番に計算していく

8 Nussinov et al. '78 (2) 実際の漸化式 MMS(i, j) : i 番目から j 番目までの部分文字列に対する解 MMS( i, j) = max( MMS( i, j 1), MMS( i, k 1) + MMS( k + 1, j 1) + 1 for all k( i k < j, match( k, j) = 1)) i j i j O(n 2 ) 種類 i k j O(n) 通りブランチがなければ O(n 2 )

9 ギャップペナルティ的なものを考えるには? 途中に変なものが混じるようなものにはペナルティーを課したい左の方が良さそうだが結合数は同じ

10 Waterman and Smith '78 (1) ペナルティのつけ方 = エネルギーを定義するエネルギー最小化の問題 k 連続結合 : -1.0 A-U: 0.25 G-C: 1.3 G-U: +1.9 m k (m=0) (k+m) (k, m>0) h h

11 Waterman and Smith '78 (2) Branch は無視して最適な構造を求めるアルゴリズム同様の DP で O(n 3 ) で計算できる Linear なパラメータな場合 O(n 2 ) にできる cf. gap penalty in alignment stack 3'bulge O(n) 通り 5'bulge stem O(n 2 ) 種類 hairpin O(n) 通り Stem 計算用に別メモリが必要

12 Zuker and Stiegler '81 (1) いろいろ条件を追加しても O(n 3 ) dangling bases 結合ペアのとなりの塩基のエネルギーは通常と異なる hairpins 長さが 4 の時にエネルギーが低い = 長さに対する表を用意また隣とさらに隣の結合している塩基の影響がある =4 つの塩基から表をひく 5' branches/stems/bulges a+b s+c t (s=#basepairs, t=#singletons) 3' 4つの塩基から表をひく stacking pairs ペアを組んでいない塩基のエネルギー singletons

13 Zuker and Stiegler '81 (2) 考え方はやはり同じようにして計算できる! stack bulge/stem/etc bulge/stem/etc branch O(n 2 ) 種類 hairpin O(n) 通り

14 Rivas and Eddy '99 さらに pseudo-knot を追加すると O(n 6 ) stack bulge/stem/etc bulge/stem/etc branch O(n) 通り O(n 2 ) 種類 hairpin pseudo knot O(n 3 ) 通り O(n 4 ) 種類 O(n) 通り x4 O(n 2 ) 通り

15 Simple Pseudo-Knot (1) [Akutsu '00] 制限つきならばもう少し小さくできる O(n 4 ) この間の塩基と他の部分の塩基との結合がない

16 Simple Pseudo-Knot (2) pseudo-knot 区間内の DP 計算 O(n 3 ) これを始点となる i すべてに関して計算 O(n 4 ) i j k 始める i こちらはどこまでも計算する DP i j k DP i j k O(n 3 ) 種類 DP

17 Simple Pseudo-Knot (3) Multiple simple pseudo-knot にしても問題なく O(n 4 ) 既に求めているこの区間の pseudo-knot 分割 O(n) 通り O(n 2 ) 種類 knot をまたぐようなものも考える

18 Context Free Grammar との類似点やっていることはかなり文脈自由文法チックなこと Nussinov's algorithm S asu usa gsc csg gsu usg SS as cs us gs ε それぞれの生成規則にスコアがついていると思えばよいこの考えを用いてスコアの学習が可能 ( 確率文法 ) 遷移確率を定義構造がわかっていれば遷移確率がわかるあるいは EM アルゴリズム等で文章の期待値を最大化するただしえられるものは局所解確率がわかれば HMM に対する Viterbi アルゴリズムと同様にして構造を予測することもできる Cocke-Younger-Kasami algorithm

19 Suboptimal Structures [Zuker '89] こうやってエネルギー最小の構造を求めても正しい構造を予測できる確率は実際にはかなり低いエネルギーが低い構造を列挙することができればその中から選択することが可能になる方法 Zukerのアルゴリズムではすべての区間において最適解を求めているがそれらのうちの上位のいくつかを出力するすべての区間 [i..j] において k 番目までの解を求める O(kn 3 ) すべての区間 [i..j] において最適解より Δ 以上悪くない解をすべて求める計算時間不明最短路問題に帰着される問題ならばもっと効率のよい解法あり DPやA* アルゴリズムで求めたアラインメントの準最適解 HMMにおけるViterbiアルゴリズムの準最適解

20 O(kn 3 ) アルゴリズム Branch の計算において k 番目まで同士の和の上位 k 番目までの計算をしないといけないヒープを用いて O(k log k) がんばれば O(k) にもできるが難しいそれ以外の場合も O(k) ソートする方が楽でその場合 O(k log k) stack bulge/stem/etc bulge/stem/etc branch hairpin

21 k 最短路問題 k 最短路問題とその関連問題について 2 点間のパスを短いものから k 本求める順番に求めるかセットを求めるか? 準最適解問題 2 点間のパスで最短路 +Δ の長さ以下のものをすべて求める GΔ 問題最短路 +Δ 以下の長さの準最適解が通過することのある点と枝からなる部分グラフを求める

22 Path Heap 全パス集合を表すヒープルート : 最適解 ( のひとつ ) Sidetrack 終点への最短路木上にない枝子パス k 最短路 Eppstein '94 (1) 親パス P の途中まで (P )+sidetrack+ 最短路 P は P の最後の (= 終点に一番近い ) sidetrack を必ず含むようにする親がルートである場合を除く必ず子パス長親パス長となるヒープを作成して上から辿る準最適解列挙ヒープを DFS で探索最適解

23 Eppstein '94 (2) Path Heap の問題点パスの子供の数が O(n) になってしまうそのまま上から辿るときに効率が悪いひとつのパスの子供についてはヒープで管理次数を制限 4 無限の大きさになってしまう O( E + V ) の大きさのグラフで表現可能その計算時間は O( E + V ) 簡易アルゴリズムでは O( E + V log V ) 超ナイーブアルゴリズムだと O( E + V 2 )

24 Eppstein '94 (3) Path Heap Graph の作成方法 Dijkstra 法 ( アラインメントの場合 DP も可 ) で終点への最短路木を作成し各 sidetrack e に対し e を用いた時に損する量を loss(e) として計算ある点 v に関してそれを始点とする枝のうち最小の loss(e) を持つ枝を sidetrack(v) とおく各点から出て行く sidetracks に対して loss(e) の値に基づきヒープを作成する出次数 d の点における計算量は O(d) で OK! 全体で O(m) すべての点に関してその点から終点への最短路上の点 v の sidetrack(v) を loss(sidetrack(v)) に基づいてヒープを作成する線形時間で可能 ( ただし難しい )

25 Eppstein '94 (4) ヒープの線形時間の古典的構成法適当な順番で配列に押し込む後ろから順番に自分の子孫を全て修正していく n/2 + 2n/4+3n/8+4n/ O(n) 3 下から計算必ず子より親の方が小さい値を持つ i 番目の親は i/2 番目 ( ルートを 1 番目とした場合 )

26 Eppstein '94 (5) PathHeap の作成方法うまくバランスさせながら必要なところしか記憶しない AVL 木を使う ( バランスできるが余計なメモリが必要 ) もっと賢い方法一番右側のパスに挿入し一番左側に持ってくるより高度のアルゴリズムを用いれば O( V + E ) も可能だがかなり難しいこれ以外に sidetrack(v) 以外の枝を管理終点長さ log n の部分だけ記憶し他は一つ前へのポインタで表現可能ここのヒープポインタ

27 Eppstein '94 (6) あとは上から辿るだけ O(k log k) ヒープを用いるソートされている O(k) [Frederickson '93] ソートされていない最短路 +Δ 以内 DFS で可能解のパス ( や対応するアラインメント ) を出力する場合 O(nk+k log k) や O(nk) その出力サイズが O(n) であるため

28 もう少し応用 [Shibuya '97] 少しヒープに細工をするだけでより有用な準最適解だけの列挙を行うことも可能最適解準最適解 REAFSQAIWRATFAQVPESRSLFKR== ADFLV-ALF-EKFPDSANFFADFKGKS KNG-S-LLFGLLFKTYPDTKKHFKHFD LAAVF-TAYPDIQARFPQFAGK-DVAS GSGVE-ILY-FFLNKFPGNFPMFKKLG REAFSQAIWRATFAQVPESRSLFKR== ADFLV-ALF-EKFPDSANFFADFKGKS KNG-S-LLFGLLFKTYPDTKKHFKHFD LAA-VFTAYPDIQARFPQFAGK-DVAS GSG-VEILY-FFLNKFPGNFPMFKKLG REAFSQAIWRATFAQVPESRSLFKR== ADFLV-ALF-EKFPDSANFFADFKGKS KNG-S-LLFGLLFKTYPDTKKHFKHFD LAAVF-TAYPDIQARFPQFAG-KDVAS GSGVE-ILY-FFLNKFPGNFPMFKKLG 組み合わせによる準最適解 ( 列挙不要 ) 無視! REAFSQAIWRATFAQVPESRSLFKR== ADFLV-ALF-EKFPDSANFFADFKGKS KNG-S-LLFGLLFKTYPDTKKHFKHFD LAA-VFTAYPDIQARFPQFAG-KDVAS GSG-VEILY-FFLNKFPGNFPMFKKLG 最適解と 2 箇所以上異なっている

29 GΔ 最短路 +Δ 以下の長さの準最適解が通過することのある点と枝からなる部分グラフを求めるアルゴリズム終点への最短路木を求め loss(e) をすべての枝について計算する枝の長さをloss(e) だと思って始点からDijkstra 法等を用いて Δ 以内で到達できる点と枝の集合を求める=GΔ 最短路 +Δ 以下の長さのパス s t

30 簡単な方法類似構造を持つと思われる配列集合の予測マルチプルアラインメントを行う i 列と j 列が結合するかどうか? 何も考えずにエネルギー計算してエネルギーの和を求める相互情報量を求める結合することが多いのであれば片方が A であればもう片方は T となることが多い結合するペアは互いに独立ではないどの配列においても結合していれば相互情報量は非常に高くなるあとはその情報を用いて普通に Zuker アルゴリズムを走らせる問題点アラインメントする時に文字列が似ていないかもしれない

31 2 本以上の配列の同時構造予測 [Sankoff '85] 最適解はかなりの力技 k 本に対して O(n 3k ) Nussikov 版簡略版アルゴリズム Zuker に拡張しても基本は同じ O(n 4 ) 種類 O(n 2 ) 通り

32 木構造の比較をする予測した RNA 構造の比較はどうする? RNA は木で表現できるため木は ordered tree やりたいこと unordered だとさらに NP-hard な問題になることが多い String pattern matching の種々の問題の木への拡張木構造がどれほど似ているか? 保存されている構造はどこか? 部分構造の検索類似検索等接尾辞木の木への拡張の話は既出ただし生物学的な根拠に基づく比較とは言い難い

33 Tree Edit Distance vs Tree Alignment 配列の場合両者はほとんど同じ概念だったが木では異なる概念 Edit Distance できるだけ少ない回数の挿入削除変異によって片方の木を別の木に変換する当然ながらmetric distanceである ( 三角不等式を満たす ) Alignment それぞれに適当にノードを挿入して topological に同じ木を作る edit distanceにおいて挿入した後に削除することに相当すなわちedit distance 以上の値をとる metric distanceではない ( 三角不等式を満たさない ) ラベルは必ずしも同じでなくてもよいがラベル同士のスコアを比較する

34 Tree Edits 3 種類の操作 a a e d b c a b c d 変異削除挿入 b a b c d a e d b c

35 DP for Tree Edit Distance [Zhang et al '89] 簡単なバージョンポストオーダーで番号をつける T[i..j] をその間の番号だけからなる森とする left(i) を i の子孫で一番左の孫とする T において j を i の子孫 T' において l を k の子孫として edit_distance(t[left(i)..j], T'[left(k)..l]) を DP で計算するマッチさせるかどうかで場合わけ O(n 4 ) 種類

36 まとめ RNA 構造予測アルゴリズム Nussikov Zuker Akutsu 準最適解アルゴリズム Eppstein 木の edit distance について

A Constructive Approach to Gene Expression Dynamics

A Constructive Approach to Gene Expression Dynamics 配列アラインメント (I): 大域アラインメント http://www.lab.tohou.ac.jp/sci/is/nacher/eaching/bioinformatics/ week.pdf 08/4/0 08/4/0 基本的な考え方バイオインフォマティクスにはさまざまなアルゴリズムがありますがその多くにおいて基本的な考え方は配列が類似していれば機能も類似しているというものである例えば