産業技術総合研究所 生命情報工学研究センター 津田宏治

Presentation on theme: "産業技術総合研究所 生命情報工学研究センター 津田宏治"— Presentation transcript:

1 産業技術総合研究所 生命情報工学研究センター 津田宏治
講義２：バイオインフォマティクス 産業技術総合研究所 生命情報工学研究センター 津田宏治

2 授業の構成 1. 生物学データのカタログ ２．新規カーネルの設計法 3. 生物配列解析 4. 生物ネットワーク解析
Marginalized kernel (Fisher Kernel) 4. 生物ネットワーク解析 ネットワーク推定のためのカーネル法 (Diffusion kernel) 複数のネットワークを用いたタンパク質機能予測 (SSL) 5.　生物学におけるグラフデータ Marginalized graph kernels

3 Part 1: 生物学データのカタログ

4 生物配列 DNA配列 (A,C,G,T) ＲＮＡ配列 (A,C,G,U) アミノ酸配列：タンパク質 (20 symbols)
遺伝子発見, スプライス部位発見 ＲＮＡ配列 (A,C,G,U) MicroRNA発見、二次構造予測 アミノ酸配列：タンパク質 (20 symbols) Remote homolog発見, フォールド発見 etc.

5 配列に隠されている構造 (I) 遺伝子のExon/intron

6 配列に隠されている構造 (II) 隠された構造を推定し、その後の推定に生かす RNA 二次構造 タンパク質 3D構造 生物学的グラフ

7 遺伝子発現量データ 細胞における多種のmRNAの量の計測値 タンパク質の量の目安 時系列の場合もある 隠された動的システムのスナップショット

8 生物学的ネットワーク タンパク質相互作用ネットワーク 代謝ネットワーク 遺伝子制御ネットワーク 配列の類似度ネットワーク
Thousands of nodes (genes/proteins) 100000s of edges (interactions)

9 タンパク質相互作用ネットワーク

10 代謝ネットワーク

11 多様な予測問題が存在する

12 タンパク質のプロファイル 進化プロファイル（Phylogenetic Profile） ドメインプロファイル そのタンパク質を含む種のリスト
プロテインが含むドメイン (small fraction of 3D structures) のリスト Human, Chimp, Mouse, Dog, Yeast, E.coli (0, , , , , )

13 Part 2: 新規カーネルの設計法

14 Simple (linear) learning algorithm
Kernels and Learning カーネル法では、データからの学習問題は次の二つに分割される 汎用的な学習アルゴリズム (e.g. SVM, PCA, …) – 線形関数に基づくもの 問題依存のカーネル関数 Simple (linear) learning algorithm Complex Learning Task Specific Kernel function

15 (not necessarily stored)
学習手法の生成 モジュール化、再利用 同じカーネルを、異なるアルゴリズムに適用 異なるカーネルを、同じアルゴリズムに適用 Data 1 (Sequence) Learning Algo 1 Kernel 1 Gram Matrix (not necessarily stored) Data 2 (Network) Learning Algo 2 Kernel 2 Gram Matrix

16 カーネル法の直感的解釈 都合のいい射影 f を見つけ、射影先で線形の問題を解く
カーネルは、二つの対象間の類似度を表しており、射影先の空間での内積に対応 でも、射影は陽には求めない 内積のみによって記述されるアルゴリズムは、カーネル化できる

17 Kernel Methods : the mapping
f f f Original Space Feature (Vector) Space

18 有効なカーネル Theorem: k(x,y) is a valid kernel if k is positive definite and symmetric (Mercer Kernel) A function is P.D. if In other words, the Gram matrix K (whose elements are k(xi,xj)) must be positive definite for all xi, xj of the input space One possible choice of f(x): k(•,x) (maps a point x to a function k(•,x)  feature space with infinite dimension!)

19 新しいカーネルを作るには 有効性を保つ演算:

20 デザインの指針 Convolution Kernels: 部分同士の類似度を表すカーネルを、まとめあげて、全体同士のカーネルを作り出す
Generative model-based kernels: データの生成モデル（確率モデル）が与えられているときに、そこからカーネルを導き出す Ｆｉｓｈｅｒ　Ｋｅｒｎｅｌ，　ＴＯＰ　ｋｅｒｎｅｌ

21 Family of kernels Kernels for biological sequences Tree Kernels
Spectrum kernel (Leslie et al., 2002) Marginalized kernel (Tsuda et al., 2002) Profile kernel (Kuang et al., 2004) Local alignment kernel (Saigo et al., 2004) Tree Kernels Kernel for phylogenetic profiles (Vert, 2002) Kernel for natural language (Suzuki et al., 2003) Kernel for RNA sequences (Kin et al., 2002) Kernel Methods in Computational Biology, MIT Press, 2004

22 Family of kernels Kernels for nodes in a network Graph Kernels
Diffusion kernel (Leslie et al., 2002) Locally constrained diffusion kernel (Tsuda and Noble, 2004) Graph Kernels Marginalized Graph Kernels (Kashima et al., 2003) MGK without tottering (Mahe et al., 2004) Acyclic Pattern Kernels (Horvath et al., 2004)

23 カーネル法の弱点 学習結果が解釈しにくい 密なカーネル行列: 遅い データのどのような特徴が使われたのか
-> Graph Mining, Boosting 密なカーネル行列: 遅い 大部分の演算に O(n^3)時間必要 -> 半教師付き学習 (Semi-supervised learning)

24 Part 3: 生物配列解析

25 生物配列の教師あり分類の例 DNA配列 (A,C,G,T) RNA配列 (A,C,G,U) アミノ酸配列 (20 symbols)
Gene Finding, Splice Sites RNA配列 (A,C,G,U) MicroRNA discovery, Classification into Rfam families アミノ酸配列 (20 symbols) Remote Homolog Detection, Fold recognition

26 配列のためのカーネル ACGGTTCAA ATATCGCGGGAA 長さの異なる配列の類似度をどのように測るか
ＳＶＭや、その他のカーネル法と組み合わせて用いられる ACGGTTCAA ATATCGCGGGAA

27 3.1 Marginalized kernels K. Tsuda, T. Kin, and K. Asai.
Marginalized kernels for biological sequences Bioinformatics, 18(Suppl. 1):S268-S275, 2002.

28 カウントカーネル シンボルのカウントによるカーネル 先ほどのSpectrum kernelはカウントカーネルの拡張
全てのk-merの数をカウントする 文脈の変化を伴う配列の場合には適当でない E.g., coding/non-coding regions in DNA

29 隠れマルコフモデル（ＨＭＭ）による文脈の推定
顕在変数　　　　　 : シンボル列 隠れ変数 　　　　　 : 文脈 HMMは、隠れ変数の事後確率　　　　　をデータから計算できる

30 Marginalized kernels （周辺化カーネル）
連結カーネル　　　　　　　を設計する。ここで、 しかし、隠れ変数は観測できないので、計算できない 隠れ変数に関して条件的期待値を計算する 顕在変数に関する周辺化カーネル

31 結合カーネルの設計 シンボル数を、各文脈ごとにカウントする : 結合シンボル (k,l) のカウント
結合カーネル：　文脈つきのカウントカーネル

32 結合カーネルの周辺化 結合カーネル 周辺化カウントカーネル

33 周辺化カウントをHMMから計算 周辺化カウントは、以下のように表される
第i番目の隠れ変数の条件つき確率は以下のように、Dynamic Programmingを用いて計算される

34 ２次の周辺化カウントカーネル もしシンボル間の隣接関係が意味を持つ場合には、周辺化カウントカーネルでは不足 ２次の周辺化カウントカーネル
4つの隣接するシンボル (２つが顕在変数、２つが隠れ変数)を組み合わせて数える

35 Fisher Kernel 確率モデル Fisher Kernel 特徴ベクトルへの射影 (Fisher score vector)
Z: Fisher情報行列

36 HMMから導かれたFisher Kernel
HMMからのFisher Kernel (Jaakkola et al. 2000) Emission Probabilityに関してしか微分を計算しない Fisher情報行列は用いない このカーネルは、周辺化カーネルの一つの場合 カウントが中心化され、重みが付け加えられている

37 タンパク質のクラスタリング実験 84本のアミノ酸配列、５クラス ５種のバクテリアからのgyrBタンパク質 クラスタリング法
HMM + {FK,MCK1,MCK2}+K-Means 評価：真のクラスラベルとの比較 Adjusted Rand Index (ARI)

38 Kernel Matrices

39 クラスタリング結果の評価

40 周辺化カーネルの応用 Marginalized Graph Kernels (Kashima et al., ICML 2003)
Sensor networks (Nyugen et al., ICML 2004) Labeling of structured data (Kashima et al., ICML 2004) Robotics (Shimosaka et al., ICRA 2005) Kernels for Promoter Regions (Vert et al., NIPS 2005) Web data (Zhao et al., WWW 2006)

41 まとめ (周辺化カーネル) 確率モデルから、カーネルを導き出すための一般的な枠組み Fisher kernelは、特別なケース 応用は多様

42 Part 4: 生物学ネットワーク解析

43 生物学的ネットワーク タンパク質相互作用ネットワーク 代謝ネットワーク 遺伝子制御ネットワーク 配列の類似度ネットワーク
Thousands of nodes (genes/proteins) 100000s of edges (interactions)

44 タンパク質相互作用ネットワーク

45 代謝ネットワーク

46 二種類の問題を扱う ネットワークの中の未知の部分を他のデータ（遺伝子発現量など）を用いて推定する
Training network Extra nodes ネットワークの中の未知の部分を他のデータ（遺伝子発現量など）を用いて推定する ノードにつけるラベルを推定する（タンパク質機能予測）

47 4.1 カーネルを用いたネットワーク推定 T. Kato, K. Tsuda, and K. Asai.
Selective integration of multiple biological data for supervised network inference. Bioinformatics, 21(10): , 2005.

48 ネットワークの統計的推定 タンパク質のデータから、ネットワークを推定 カーネルを用いた推定法を提案
遺伝子発現データ, 進化プロファイル etc カーネルを用いた推定法を提案 特徴1. 教師ありネットワーク推定 ネットワークに一部分かっている部分があり、残りを推定 特徴２．多種のデータの重みつき統合（取捨選択） どの種類のデータが、ネットワーク推定に寄与するかがわかる

49 教師なし推定 教師あり推定 教師なしネットワーク推定 教師ありネットワーク推定
教師なし推定 教師あり推定 教師なしネットワーク推定 ベイジアンネット (Friedman et al., 2000) 全てのノードペアに関してエッジの有無を推定 教師ありネットワーク推定 ネットワークの一部が分かっている (訓練ネットワーク) ネットワークの残りを、データから推定する

50 Supervised Network Inference
Extra nodes Training network

51 １種類のデータ 多種のデータ 複数のデータを用いてネットワーク推定を行う ネットワーク推定に寄与するデータを見つける
１種類のデータ 多種のデータ 複数のデータを用いてネットワーク推定を行う 遺伝子発現データ 細胞内局在データ 進化プロファイルデータ ネットワーク推定に寄与するデータを見つける 複数データの重みつき統合 特徴選択の延長としてのデータ選択

52 ネットワークを複数のデータから推定 遺伝子発現 相互作用ネット 機能カテゴリ 代謝ネット 進化プロファイル 遺伝子相互作用ネット 細胞内局在
遺伝子制御ネット ３次元構造

53 アウトライン カーネル行列からのネットワーク推定 訓練ネットワークを考慮する 複数データの重みつき統合 教師なし, 単一データ
教師なし, 単一データ 閾値処理: 近傍にある点をつなげる 訓練ネットワークを考慮する 教師あり, 単一データ カーネル行列補間 (Tsuda et al., 2003) 複数データの重みつき統合 教師あり, 複数データ 重みは、ＥＭアルゴリズムによって決定

54 教師なし, 単一データ データをカーネル行列に変換する タンパク質間の類似度 遺伝子発現データ: Pearson 相関行列
進化プロファイル: Tree kernel (Vert 2002) 3D 構造: Graph kernel (Borgwardt et al., 2005)

55 閾値処理によってネットワークを構築 カーネルの値が、閾値ｔより大きいところに、エッジを張る t=0.1 t=0.2 t=0.4

56 教師付き, 単一データ Kernel Matrix 分かっている訓練ネットワーク 全タンパク質に関するカーネル行列
(最初のｎ個のノードのみ) 全タンパク質に関するカーネル行列 Kernel Matrix

57 訓練ネットワークから不完全なカーネル行列へ
訓練ネットワークから、カーネル行列を導く ネットワークの表現をデータの表現と一致させる 拡散カーネルDiffusion kernel (Kondor and Lafferty, 2002) ノード間の類似度をランダムウオークによって測る *Thresholding approximately recover the original network

58 拡散カーネル A: 隣接行列, D: 度数の対角行列 L = D-A: ラプラシアン行列 拡散カーネル行列 ノード間の近さを測る
：Diffusion paramater ノード間の近さを測る

59 隣接行列と度数の行列

60 ラプラシアン行列 L

61 拡散カーネルの実際の値 “中心ノード”から の近さ

62 カーネル行列補間 P Q Minimize w.r.t. P: データのカーネル行列（完全） Q: 不完全なカーネル行列
欠損値は KL距離の最小化によって推定 解析解 Q* Q*を閾値処理して最終的なネットワークを得る Minimize w.r.t.

63 教師あり, 複数データ Diffusion Kernel Matrix Kernel Matrices 訓練ネットワーク
全タンパク質に関する複数のカーネル行列 Diffusion Kernel Matrix Kernel Matrices

64 手法の概要 Diffusion completion kernel threshold Weighted Combination
Adjacency Matrix Q Diffusion kernel completion threshold Kernel Matrices P(b) Result Weighted Combination

65 未知： Submatrices Qvh,Qhh，Weights b
Notations =b b b b4 P(b) K1 K2 K3 K4 未知： Submatrices Qvh,Qhh，Weights b

66 目的関数 KL距離 Minimize w.r.t. Q Submatrices Qvh,Qhh， Weights b P(b)
EMアルゴリズムで求解

67 EMアルゴリズム 次の二種類のステップを繰り返す E-step: 単一カーネルの場合と同じ M-step: 最適解は解析的には得られない
E-step: minimize w.r.t. Qvh,Qhh M-step: minimize w.r.t. b E-step: 単一カーネルの場合と同じ M-step: 最適解は解析的には得られない

68 拡張カーネル行列上でのEM Algorithm
where 次の問題の局所最適解は、元の問題の局所最適解になっている

69 各ステップの解析解 E-step M-step

70 ネットワーク推定実験 Network ・代謝ネットワーク （KEGG） ・タンパク質相互作用ネットワーク（von Mering, 2002）
Data ・exp: 遺伝子 ・y2h: yeast2hybridによるネットワーク ・loc: 細胞内局在データ ・phy: 進化プロファイルデータ ・rnd1,…,rnd4: ノイズデータ Methods ・Q: 提案法 ・P: カーネル行列の和 ・cca: kernel CCA (without noises) Evaluation エッジ推定に関するＲＯＣスコア (10-fold 交差検定)

71 代謝ネットワーク LIGAND Database (KEGG)より作成 (Vert and Kanehisa, NIPS, 2003)
　連続する化学反応を触媒する酵素をつなげる 769 nodes, 3702 edges

72 タンパク質相互作用ネット 複数の実験で確かめられた相互作用 984nodes, 2438 edges
High-throughput yeast two hybrid Correlated mRNA expression Genetic interaction Tandem affinity purification, High-throughput mass-spectrometric protein complex identification 984nodes, 2438 edges

73 代謝ネットワーク

74 タンパク質相互作用ネットワーク

75 ランダムデータの数を増やしてみる (代謝ネットワーク)
Sensitivity at 95% specificity

76 まとめ (ネットワーク推定) ネットワークの教師つき推定 ネットワークの一部がわかっている 複数のデータの取捨選択
カーネル行列補間問題としての定式化 代謝ネットワークと、相互作用ネットワークにおける実験

77 4.2 複数のネットワークに基づくタンパク質機能予測
K. Tsuda, H.J. Shin, and B. Schoelkopf. Fast protein classification with multiple networks. Bioinformatics (ECCB'05), 21(Suppl. 2):ii59--ii65, 2005.

78 複数のネットワークを用いた機能予測 タンパク質相互作用ネットワーク 代謝ネットワーク 遺伝子制御ネットワーク 配列類似度によるネットワーク
全てのネットワークを機能予測に役立てよう 関係のないネットワーク, 冗長なネットワーク 自動でネットワークを取捨選択する

79 単一のネットワークにおける機能予測 +1/-1： ある機能を持つ・持たないタンパク質 ?: 機能不明なタンパク質

80 複数のネットワーク

81 ラベル伝搬法の複数ネットワークへの拡張 ネットワークをラプラシアン行列で表す
疎な線形連立方程式を解いてラベル伝搬を行う（Zhou et al., NIPS 2003) New: 複数ネットワークの拡張 各ネットワークに自動的に重みが割り当てられる

82 単一ネットワークにおけるラベル伝搬 W: ネットワークの隣接行列 訓練ノードのラベル テストノードのラベルを予測 スコア 学習問題
訓練ノードにおいては、スコア　　は、ラベル　　に近い 隣接しているノードのスコアは互いに近い 学習問題

83 ラプラシアン行列 学習問題 正則化項（第二項）は以下のように書き換えられる はラプラシアン行列

84 学習問題の解 解は、次の線形方程式を解いて得られる ラベルは、得られたスコア を閾値処理
ラベルは、得られたスコア　　　　　を閾値処理 計算時間：エッジの数にほぼ線形 (Spielman and Teng, 2004)

85 複数ネットワークへの拡張 単一ネットワークの問題を書き直す 複数のラプラシアン: 複数ネットワークの学習問題 上限を用いて正則化する

86 最適化 ラグランジュ乗数を導入してｆに対して解く 　　　：ｋに対する重み（ラグランジュ乗数） 双対問題

87 機能予測実験 3588個のイースト菌のタンパク質 13個の機能カテゴリ 5 種のネットワーク 各カテゴリに対するニ値分類問題を解く
精度は、5-fold交差検定で計測

88 Functional Categories
MIPS Comprehensive Yeast Genone Database 1. metabolism 2. energy 3. cell cycle and DNA processing 4. transcription 5. protein synthesis 6. protein fate 7. cellular transportation and transportation mechanism 8. cell rescue, defense and virulence 9. interaction with cell environment 10. cell fate 11. control of cell organization 12. transport facilitation 13. others 13 CYGD functional Classes

89 Genetic interactions (MIPS genetic interactions)
5 Networks Network created from Pfam domain structure. A protein is represented by a 4950-dimensional binary vector, in which each bit represents the presence or absence of one Pfam domain. An edge is created if the inner product between two vectors exceeds The edge weight corresponds to the inner product. Co-participation in a protein complex (determined by tandem affinity purification, TAP). An edge is created if there is a bait-prey relationship between two proteins. Protein-protein interactions (MIPS physical interactions) Genetic interactions (MIPS genetic interactions) Network created from the cell cycle gene expression measurements [Spellman et al., 1998]. An edge is created if the Pearson coefficient of two profiles exceeds 0.8. The edge weight is set to 1.

90 Methods in Comparison MRF SDP/SVM
Label propagation with optimized weights Label propagation with uniform weights MRF Markov Random Field, proposed by Deng et al [2003] SDP/SVM Semi-definite Programming based Support Vector Machines, proposed by Lanckriet et al [2004]

91 各カテゴリに関するROC score

92 得られたウエイト

93 Comparison of Methods White: MRF, Green: SDP/SVM,
Blue: FIX, Black: OPT

94 計算時間 Label propagation（ Fixed Weights） : 1.41 seconds* (std. 0.013)
Label propagation（Optimized Weights） : 49.3 seconds* (std. 14.8) Nearly linearly proportional to the number of non-zero entries of sparse matrices SDP/SVM : Approx. 60 min (G. Lanckriet, personal communication) O(n3)+ O((m+n)2n2.5) * measured in a standard 2.2Ghz PC with 1GByte memory

95 まとめ (機能予測) Extended Label Propagation for Multiple Networks
Good Prediction Accuracy in Yeast Protein Function Experiments Fast and Scalable Redundant / Irrelevant Networks Excluded Biological Implications??

96 Part 5: グラフカーネル

97 グラフデータ解析 通常の機械学習法は、「表」を仮定 構造データは、この枠組みを超える → 新しい手法が必要 … Osaka Female
→　新しい手法が必要 … Osaka Female 31 ×× 0002 Tokyo Male 40 ○○ 0001 Address Sex Age Name Serial Num

98 ＲＮＡ２次構造を表すグラフ

99 生物学におけるグラフ DNA配列 RNA テキストデータ 化合物 A C G H C CG U UA H C C O H C C H C H
フェノール Amitriptyline inhibits adenosine uptake

100 5.1 Marginalized Graph Kernels （周辺化グラフカーネル）
H. Kashima, K. Tsuda, and A. Inokuchi. Marginalized kernels between labeled graphs. ICML 2003, pages , 2003.

101 周辺化グラフカーネル グラフＧとＧ‘の間のカーネルを設計 ノードとエッジに両方ラベルが付いている
(Kashima, Tsuda, Inokuchi, ICML 2003) グラフＧとＧ‘の間のカーネルを設計 ノードとエッジに両方ラベルが付いている

102 Label path ノードとエッジのラベルの順列 ランダムウオークで生成 均一な、初期、遷移、終末確率

103 Path-probability vector

104 カーネルの定義 A c D b E B c D a A Pathのカーネル すべてのパスに関して期待値を取る 周辺化グラフカーネル

105 計算 : Set of paths ending at v
Transition probability : Initial and terminal : omitted 計算 : Set of paths ending at v KV : Kernel computed from the paths ending at (v, v’) KV is written recursively Kernel computed by solving linear equations （polynomial time） v’ v A(v) A(v’)

106 グラフカーネルの応用 Chemical Compounds (Mahe et al., 2005)
Protein 3D structures (Borgwardt et al, 2005) RNA graphs (Karklin et al., 2005) Pedestrian detection Signal Processing

107 変異原性予測 MUTAG benchmark dataset 化合物が、ＤＮＡに変異を起こさせる性質
125 positive data (effective for mutations) 63 negative data (not effective for mutations) Mahe et al. J. Chem. Inf. Model., 2005

108 タンパク質３次元構造の分類 タンパク質３次元構造のグラフ 類似度を、グラフカーネルで測る Node: 二次構造要素
Edge: 二つの要素の間の距離 類似度を、グラフカーネルで測る Borgwardt et al. “Protein function prediction via graph kernels”, ISMB2005

109 Classification of proteins: Accuracy
Borgwardt et al. “Protein function prediction via graph kernels”, ISMB2005

110 Pedestrian detection in images (F. Suard et al., 2005)

111 Classifying RNA graphs (Y. Karklin et al.,, 2005)

112 グラフカーネルの長所 比較的高速な計算 O(n^3) 正定値カーネル Support Vector Machines Kernel PCA
Kernel CCA And so on…

113 グラフカーネルの短所 大域的な類似度 結果が、解釈できない 構造的な特徴は完全には捉えられない (e.g. loops)
細かい違いを見分けるのが苦手 長いパスの重みが小さくなりすぎる 結果が、解釈できない 構造的な特徴は完全には捉えられない (e.g. loops) No labels -> kernel always 1

114 講義のまとめ２ 生物学的データは、他のドメインのデータ（画像、音声、テキストなど）と比べて、次の特徴を持つ 複数のデータを持つことが多い
構造データ 結果を解釈する必要性 カーネル法は、これまで有効に使われてきたが、まだまだ新しいアプローチの余地がある。