生命科学基礎論 (第8回) 阿久津達也京都大学化学研究所バイオインフォマティクスセンター内容   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 二次構造 agag cu agag cu 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 Y j a u 遺伝子発現データの解析  DNAチップ・DNAマイクロアレイ   多数の遺伝子の発現量を同時測定可能遺伝子発現データ解析  クラスタリング   遺伝子ネットワーク推定   どの遺伝子が似ているか？どの遺伝子がどの遺伝子を制御しているか？腫瘍細胞分類  腫瘍のより細かな分類、抗がん剤の適切投与遺伝子ネットワーク推定発現量ネットワーク遺伝子発現量の時間変化 ACETYL-CoA OXALOACETATE 推定 CIT2 MDH2 ACO1 MLS1 ISOCITRATE 時間 GLYOXYLATE ICL1 ネットワークモデル・推定手法       ブーリアンネットワーク微分方程式系（線形・非線形）ニューロ型モデル時系列解析ベイジアンネットワークグラフィカルモデリングブーリアンネットワークの例状態遷移表 A B 時刻ｔ C A’ = B B’ = A and C C’ = not A A B C 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 時刻ｔ＋１ A’ 0 0 1 1 0 0 1 1 B’ 0 0 0 0 0 1 0 1 C’ 1 1 1 1 0 0 0 0 ブーリアンネットワークの同定    時刻 t, t+1 の状態の組（遷移表の一部） ⇒ 例例に無矛盾なネットーワークが一意かを判定例は発現パターンの変化に相当時刻ｔ A B C 1 0 0 0 1 0 0 1 1 時刻ｔ＋１ A’ 0 0 1 B’ 0 1 0 C’ 1 1 0 A’ = C B’ = B and (not C) C’ = not C A’ = C B’ = B xor C C’ = not C 入次数   ネットワーク形状に制約が無い場合 ⇒状態遷移表の全部の行（ 2n ）行が必要入次数が定数 K 以下 ⇒（全部で２ｎ行あるうちの）たったO(log n)行で十分入次数＝２ A 入次数＝３ A ベイジアンネットワーク     条件付き確率で知識やネットワークを表現 AI分野で数多くの研究グラフィカルモデリングと深い関係ブーリアンネットワークとは異なり、時間を陽には取り扱わない NOT回路の例 A Prob(B=0|A=1) = 1.0 B Prob(B=1|A=0) = 1.0 Prob(B=1|A=1) = 0.0 Prob(B=0|A=0) = 0.0 AND回路の例 A B Prob(C=1|A=1,B=1) = 1.0 Prob(C=0|A=1,B=1) = 0.0 Prob(C=1|A=0,B=1) = 0.0 C Prob(C=0|A=0,B=1) = 1.0 線形微分方程式系の推定 (D’haeseleer et al. 1999) dX   X β dt  X (t  t )  X (t )   X t i i i i i i   i (t )  β 微分方程式を離散化 ⇒ 連立一次方程式 ⇒ 回帰分析時系列データが既知なら、Xi (t)やΔt などは定数を考えることができる S-system n n dX i   g  h    X X j j i i dt j 1 j 1 ij ij 例 dX     3 X X dt 1 1.5 2.0 2 3  3  X 2.5 4 遺伝子発現データを用いた腫瘍細胞分類   発現データを観測することにより、腫瘍細胞の詳細な分類を行う抗がん剤の適切な投与などに応用できる可能性腫瘍細胞 DNAマイクロアレイ Type A 腫瘍のタイプ Type B Eric Landerらの研究I  (1999) 急性白血病の分類     ６８００個程度の遺伝子の発現データを利用７２サンプル ALL (acute lymphoblastic leukemias) AML (acute myeloid leukemias) Eric Landerらの研究II      急性白血病のデータ(Golub et al, 1999) 38+34の患者の6817遺伝子の発現量を AffymetrixのDNAチップで計測 ALL と AML のクラス分け B-CELL ALL と T-CELL ALL のクラス分け多数決により決定（ただし、差が少ない場合には判定不能とする） Eric Landerらの研究III  クラス予測    クラス発見    与えられたデータがどの既知クラスに入るかを推定（重み付き）多数決により推定新たな腫瘍のタイプを発見自己組織化マップ（クラスタリング技法の一種）を利用 Informative Gene    クラス予測に有用な遺伝子セットクラス分けとの相関に基づき選択 Feature Selection （AI分野で数多くの研究）サポートベクタマシン   分類のための学習方式特徴      正負の例(トレーニングデータ) からマージンを最大化するパラメータを学習過学習を起こしにくい様々なカーネルを利用可能二次計画法を利用（最適性の保証）バイオインフォマティクスにおいても既に様々な応用テストデータ margin SVMによる腫瘍細胞分類（クラス予測）   ALLを正例、AMLを負例として与えて、超平面を学習新たなサンプルがきたらば、超平面のどちらにあるかを判定し、 ALLかAMLかを予測サンプル k x+y = k ALL AML 発現データからの細胞分類 Sample1 Sample2 Sample3 Sample4 Sample5 Sample6 Sample7   遺伝子１遺伝子２遺伝子３遺伝子４遺伝子５遺伝子６タイプ 1.1 2.2 1.3 0.8 4.5 2.6 4.8 4.6 4.1 5.0 2.5 4.3 2.1 5.3 3.9 4.5 0.4 0.5 0.8 0.3 4.3 3.4 4.8 3.5 ALL 0.9 0.9 1.7 0.2 3.0 2.5 2.7 0.5 1.1 1.1 2.8 3.1 0.4 1.2 0.2 3.7 4.3 4.2 AML ALL ALL ALL AML AML 実際には発現量はアナログ値 (遺伝子２の発現量)＋(遺伝子３の発現量)＋(遺伝子４の発現量)>10.0 ⇒ALL と推定タンパク質―タンパク質相互作用の推定  タンパク間相互作用データ   酵母ツーハイブリッド法などで実験的に取得タンパク間相互作用からドメイン間相互作用を推定   アソシエーション法 EM(Expectation Maximization)法 P1 D1 D2 D3 ? ? D4 D6 D5 P2 ドメイン間相互作用に基づくタンパク間相互作用の推定  Pi 確率モデル[Deng et al., 2002]     どれか１組ドメインが相互作用すれば、タンパク質どうしが相互作用各ドメインペアの相互作用の確率は独立 Pij＝１: タンパク質 Pi と Pj が相互作用 Dmn＝１: ドメイン Dm と Dn が相互作用 Prob( Pij  1)  1  Dm Dn Pj  (1  Prob(D mn Dmn Pij  1)) アソシエーション法    既知データからのドメインどうしの相互作用の確率を頻度に基づいて推定 Imn: ドメインペア Dm, Dn を含むタンパク質のペアのうち、相互作用しているペアの個数 Nmn: ドメインペア Dm, Dn を含むタンパク質のペアの個数 Prob( Dmn I mn  1) : N mn Pi Dm Dn Pj 参考文献   RNA二次構造予測  Waterman: Introduction to Computational Biology, Chapman & Hall, (1995)  阿久津他訳：バイオインフォマティクス、医学出版 (2000) 遺伝子ネットワーク推定   発現データを用いた細胞分類   Cristianini, Shawe-Taylor: Support Vector Machines, Cambridge Univ. Press (2000) タンパク質タンパク質相互作用   Golub et al.: Science, 286, 531 (1999) サポートベクタマシン   北野編：システムバイオロジーの展開、シュプリンガー・フェアラーク東京 (2001) Ito et al.: Proc. Natl. Acad. Sci., 98, 4569 (2001) 相互作用推定  Deng et al.: Genome Research, 12, 1540 (2002)