京都大学 化学研究所 バイオインフォマティクスセンター 生命情報学基礎論 (第１１回)　 阿久津　達也 京都大学　化学研究所 バイオインフォマティクスセンター

講義予定 １２月7日 12月21日 (担当：上田展久) 1月11日 2月1日 タンパク質立体構造予測 配列データおよび化学構造データ解析のためのカーネル法 1月11日 相互作用推定 2月1日 スケールフリーネットワーク

講義の内容 遺伝子ネットワーク推定 ブーリアンネットワーク推定 発現データに基づく細胞のクラス分け タンパク質相互作用の推定

遺伝子ネットワーク推定

発現データからの遺伝子ネットワークの推定 環境変化（熱ショック、栄養状態）や発生、細胞分裂時の遺伝子の時系列データを観測 時系列データから遺伝子の制御関係（ネットワーク）を推定 解析にはクラスタリングが有効

ネットワーク推定のための離散モデル ブーリアンネットワーク 定性モデル ニューロ的モデル ベイジアンネットワーク ペトリネットモデル

ネットワーク推定のための連続モデル クラスタリング 微分方程式モデル（線形、S-system） 各種統計的モデル （時系列解析、多変量解析） 各種統計的モデル　　　　　　　　　　　　　　　　（時系列解析、多変量解析） グラフィカルモデリング ハイブリッドペトリネット　　　　　　　　　　　　　（微分方程式　＋　ペトリネット）

ブーリアンネットワーク同定 ブーリアンネットワーク ブーリアンネットワーク同定 遺伝子制御ネットワークのモデル 　　　頂点⇔遺伝子、ブール関数⇔制御規則 ブーリアンネットワーク同定 遺伝子破壊・過剰発現を用いた同定 (Akutsu et al. 98) REVEALアルゴリズム (Liang et al. 1998) 　⇒　少ないパターンから同定可能を示唆 O(log n)パターンから同定可能(n は頂点数) (Akutsu et al. 99)

ブーリアンネットワークの例

状態遷移 状態遷移 アトラクター：同じ状態系列が繰り返される 初期状態が与えられれば、状態遷移表より、どのような変化がおきるかがわかる 011 ⇒ 010 ⇒ 101 ⇒ 010 ⇒ 101 ⇒ … 111 ⇒ 110 ⇒ 100 ⇒ 000 ⇒ 001 ⇒ 001 ⇒　001 ⇒ …

ブーリアンネットワークの同定 時刻 t, t+1 の状態の組（遷移表の一部） ⇒ 例 例に無矛盾なネットーワークが一意かを判定 例は発現パターンの変化に相当

入次数 ネットワーク形状に制約が無い場合 入次数が定数 K 以下 ⇒状態遷移表の全部の行（ ）行が必要 ⇒状態遷移表の全部の行（　　　）行が必要 入次数が定数 K 以下 ⇒（全部で２ｎ　行あるうちの）たったO(log n)行で十分

ブーリアンネットワーク同定の ためのアルゴリズム 基本的にはしらみつぶし(Akutsu et al. 1999) 例えば、K=2の場合 xi’=xj, xi’=NOT xj, xi’=xj AND xk,…　とすべての可能な論理関数を調べる いくつかの改良 情報量の利用(Liang et al. 1998) 貪欲算法の利用(Akutsu et al. 2000) 行列演算の利用(Akutsu et al. 2000) しかし、本質的にしらみつぶし法より良い方法は知られていない（Kを固定しない場合はNP完全）

アルゴリズム 例えば右図の場合、遺伝子Dの制御規則を推定するには D’=A, D’=B D’=C, D’=D D’=NOT A, D’=NOT B D’=NOT C, D’=NOT D 　　というすべての可能な規則を生成し、入力データと矛盾がないかをチェック(K=1) ５行目までだと、D’=NOT A と D’=NOT C　が残る 6行目まで調べると、D’=NOT C　のみが残る

理論的結果：定理１ 状態遷移表の中からランダムに選んだ 個の行が与え られれば、確率 以上で 与えられた例に無矛盾な入次数限定の 　　　　　　　　　　　　　　　　　個の行が与え 　られれば、確率　　　　　以上で 　与えられた例に無矛盾な入次数限定の 　ブーリアンネットワークが一意に定まる。

ブーリアンネットワーク同定に関する結果 少数の遺伝子の発現パターンのみが変化 多数の遺伝子の発現パターンが変化 具体例 ⇒多くの発現パターンが必要　 多数の遺伝子の発現パターンが変化 ⇒少ない発現パターンで十分 多少のノイズがあってもOK 具体例 　　パターン数：　100億個　vs　数百個

ノイズありブーリアンネットワークの同定 確率ｐ以下でエラーを起こす（ベイジアンネットワークと類似） 同定アルゴリズム： 　しらみつぶしに可能な論理関数を調べ、エラーが最小の関数を出力 pが小さければ、ノイズ無しの場合と同様の結果（O（log n)パターンから同定可能）

ベイジアンネットワーク 条件付き確率で知識やネットワークを表現 AI分野で数多くの研究 グラフィカルモデリングと深い関係 ブーリアンネットワークとは異なり、時間を陽には取り扱わない

実データ解析における問題点 時間間隔の長い（数十分以上）、数点から数十点程度のデータしか利用できない 正確な発現量を測定できるわけではなく、　同じ測定を行っても数十％の差 同じような時間変化を示す遺伝子が多い　　（数百が同じような変化）

遺伝子発現データを用いた 腫瘍細胞分類 発現データを観測することにより、腫瘍細胞の詳細な分類を行う 抗がん剤の適切な投与などに応用できる可能性

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 与えられたデータがどの既知クラスに入るかを推定 （重み付き）多数決により推定 クラス発見 新たな腫瘍のタイプを発見 自己組織化マップ（クラスタリング技法の一種）を利用 Informative Gene クラス予測に有用な遺伝子セット クラス分けとの相関に基づき選択 Feature Selection （AI分野で数多くの研究）

発現データからの細胞分類 遺伝子１ 遺伝子２ 遺伝子３ 遺伝子４ 遺伝子５ 遺伝子６ タイプ Sample1 1.1 4.5 4.1 2.1 0.4 4.3 ALL Sample2 2.2 2.6 5.0 5.3 0.5 3.4 Sample3 1.3 4.8 2.5 3.9 0.8 Sample4 4.6 0.3 3.5 Sample5 0.9 0.2 2.7 3.7 AML Sample6 3.0 2.8 1.2 Sample7 1.7 3.1 4.2 (遺伝子２の発現量)＋(遺伝子３の発現量)＋(遺伝子４の発現量)>10.0 　　⇒ALL と推定

発現データ解析に関するまとめ ３つの主要な問題 クラスタリング・分類←既存の情報技術を応用可能 今後の課題 クラスタリング、ネットワーク推定、細胞分類 クラスタリング・分類←既存の情報技術を応用可能 自己組織化マップ、k-means法 ニューラルネットワーク、サポートベクタマシン 今後の課題 より多くの解析例の蓄積 誤差の大きなデータの取り扱い 複数のアレイデータベースや他のゲノム情報との統合利用

確率モデルに基づく タンパク質相互作用推定 タンパク質相互作用の確率モデル 既存手法（アソシエーション法、ＥＭ法） 線形計画法を用いる方法 計算機実験 推定問題の困難性

背景 タンパク間相互作用データ 配列の進化的関係から推定する方法は多数存在（文献１参照） Ito et al. (2000, 2001) Uetz (2000) 配列の進化的関係から推定する方法は多数存在（文献１参照） タンパク間相互作用からドメイン間相互作用の推定の既存手法 アソシエーション法 EM法 我々の研究 線形計画法を利用

研究の概要

ドメイン間相互作用とタンパク間相互作用 確率モデル[Deng et al., 2002] どれか１組ドメインが相互作用すれば、 　　タンパク質どうしが相互作用 各ドメインペアの相互作用の確率は独立 Pij＝１: タンパク質 Pi と Pj が相互作用 Dmn＝１: ドメイン Dm と Dn が相互作用

アソシエーション法(Sprinzak et al., 2001) 既知データからのドメインどうしの相互作用の確率を頻度に基づいて推定 Imn: ドメインペア Dm, Dn を含むタンパク質のペアのうち、相互作用しているペアの個数 Nmn: ドメインペア Dm, Dn を含むタンパク質のペアの個数

EM法 (Deng et al., 2002) 尤度を以下(L)のように定義し、それを極大化する一般手法である ＥＭ法 を適用 fp: false positive rate, fn: false negative rate Pij: Pi と Pj が相互作用する確率 Oij: Pi と Pj の相互作用が観測される確率

LPBN法(1) Pi と Pj が相互作用 ⇔ この式を以下のように変形

LPBN法(2) 右の条件を線形計画問題として記述 ただし、完全に制約を満たすのは難しいので、スラック変数を導入

LP法とEM法の組み合わせ LPEM法 EMLP法 LPBN を実行後に、その結果を初期値として EM を実行 EM の結果からあまりずれない範囲で LPBN を実行 具体的には以下の制約式を追加

SVM法 各タンパクペアから、ドメインペアの有無により特徴ベクトルを構成 各ペア Pij ごとに特徴ベクトル (fij)mn を以下のように定義

サポートベクターマシン 正例と負例を与えて、それらを最適（マージンを最大）に分離する超平面を学習 カーネルを適切に定義することにより超平面以外での分離が可能

計算機実験 ニ値化データ（相互作用の有無のみ） 計算機環境 DIPデータベース(Xenarios et al. 2002)を利用 1767ペアのデータを利用 テストの場合： 2/3を学習、1/3をテスト 計算機環境 XEON 2.8GHz LPソルバー： loqo

結果(1): トレーニングデータ（ニ値化データ）

結果(2): テストデータ(二値化データ）

推定問題のNP困難性 「正例のうち を満たすPijの個数＋ 負例のうち を満たすPijの個数」を最大化 完全に分離できるなら多項式時間 良い近似を得ることも困難（MAXSNP困難）

タンパク間相互作用推定に関する結論 結論 ドメイン間相互作用に基づく方法の利点 ドメイン間相互作用に基づく方法の問題点 単純な確率モデルで、ある程度の予測精度 EMアルゴリズムが比較的、有効 ドメインのかわりにモチーフを利用 ドメイン間相互作用に基づく方法の問題点 １個のドメインから成るタンパク質には不適切 将来は、ドメイン間相互作用を、実験により決定可？ ドメイン間相互作用だけでは予測精度に限界

参考文献 藤 博幸, タンパク質機能解析のためのバイオインフォマティクス, 講談社, 2004. 藤　博幸, タンパク質機能解析のためのバイオインフォマティクス, 講談社, 2004. 阿久津達也, 遺伝子ネットワークの推定アルゴリズム, 数理科学, 432:40-46, 1999. 阿久津達也, 代謝および遺伝子ネットワーク解析のための情報技術, システム/計測/制御, 48:92-97, 2004. T. R. Golub, et al., Molecular classification of cancer: class discovery and class prediction by gene expression monitorin, Science, 286:531-537, 1999.

レポート課題 以下のいずれか一つのトピックを選び、インターネット上で利用可能なソフトを２種類以上利用し、得られた結果について比較、考察せよ。ただし、各サーバーに負荷をかけすぎないように気をつけること。 タンパク質構造予測（２次構造予測も可） 遺伝子発現データ解析 タンパク質相互作用推定 提出先：１０号館事務室のレポート提出ＢＯＸ 提出期限：２月８日(火)