ゲノム統合データベースからの知識発見

集中講義（東京大学）「化学システム工学特論第３」
バイオインフォマティクス的手法による
化合物の性質予測（６）
カーネル法を用いた化合物の性質予測
阿久津達也
京都大学化学研究所
バイオインフォマティクスセンター
内容
化合物の性質予測
 サポートベクタマシンとカーネル法
 グラフカーネル
 モーガンインデックスとカーネルの
組み合わせ
 計算機実験結果
 特徴ベクトルからの化学構造の推定

化合物の性質予測

化合物の性質予測


創薬のために重要
従来手法
定量的構造活性相関
QSAR: quantitative structure-activity relationship
 ３D-QSAR




立体構造情報などを利用
CoMFA法(Comparative Molecular Field Analysis)など
人工知能的手法

化合物から特徴ベクトル（分子量、原子の組成、電荷、log P
など）を生成し、決定木、ニューラルネット、サポートベクター
マシンなどを利用
定量的構造活性相関（QSAR）


化学構造と生物活性との相関を統計的手法
（回帰式など）を用いて解析
例
BR = a π ＋ b σ ＋ c Es + d





BR: 生物活性値
π：置換基の疎水性
σ：電子の吸引性
Es：メチル基を基準にした置換基のかさ高さ
a, b, c, d は回帰分析などにより決定
サポートベクターマシン




カーネル法の一つ、ニューラルネットワークと類似
1990年代に、Cortes と Vapnik が発明
トレーニングデータとして与えられた正例と負例から、
それらを分離する超平面を計算
機械学習、統計学、人工知能、パターン認識、バイオ
インフォマティクスなど様々な分野に応用






配列分類
タンパク質フォールド予測、二次構造構造
遺伝子発現データ解析
タンパク質相互作用予測
化合物の性質推定
c.f. Kernel Methods in Computational Biology, MIT Press,
2004
サポートベクターマシン


正例と負例を与
えて、それらを最
適（マージンを最
大）に分離する超
平面を学習
カーネルを適切に
定義することによ
り超平面以外で
の分離が可能
テストデータ
margin
SVMによるテストデータの分類


学習データより超平面
を学習(SVM)
テストデータは、対応す
る点の超平面に対する
位置（上下）で判定

テストデータ
テストデータとサポート
ベクター間のカーネル関
数値の重み付き和でテ
ストデータを類別
margin
f (x ) 
  K (x,x )  
i:xi  
i
i
j: x j  
j
K (x , x j )
カーネル




サポートベクターマシン：基本的には超平面で分離
Φ(x) (特徴ベクトル）：「非線形曲面⇒超平面」に写像
カーネル K(x,y)=φ(x)・φ(y)
x と y の類似度が高い ⇔ K(x,y)が大
φ(x)
カーネルの例




線形カーネル：
K(x,y) = x・y
多項式カーネル： K(x,y) = (x・y + c)d
RBFカーネル： K(x,y) = exp (-||x - y||2 /2σ2 )
シグモイドカーネル（厳密にはカーネルではない）：
K(x,y) = tanh (κx・y - δ)
カーネルとなるための条件


カーネルの定義： K(x,y)=φ(x)・φ(y)
Mercer条件を満たす ⇒ カーネル

連続値の場合
K
(
x
,
z
)
f
(
x
)
f
(
z
)
d
x
d
z

0


離散値の場合 ( x1,x2,…,xn が入力データ)
K  (K (x i , x j ))
n
i , j 1
が半正定値行列
カーネルの作り方
データから特徴ベクトル(feature vector)を
作るのが一般的、かつ、
多くの場合に実用的
 特徴ベクトル：実数値の列
 例えば、各化合物 x に対し、


Φ(x) = (分子量, 容積, 表面積, logP,…)
とすれば、化合物 x,y に対するカーネルは
Φ(x) と Φ(ｙ) の単なる内積
グラフ・カーネル

グラフ

情報科学において幅広く利用されているデータ表現法



頂点と辺で構造を表す(点と線で構造を表す)
V: 頂点の集合
E: 辺の集合
バイオインフォマティクスにおいても幅広い利用


G(V,E)
化学構造、遺伝子ネットワーク、代謝ネットワーク
グラフカーネル

二つのグラフ G1(V1,E1) 、G2(V2,E2) 間の類似性の指標
G(V,E)
Marginalized カーネル


Tsudaらが2002年に提案
定義
K ( x, y)    p(h | x) p(h'| y)K '(( x, h), ( y, h'))
h h'


h,h’: 隠れ変数群、K’:カーネル
配列解析やRNA二次構造解析に応用
Marginalized グラフ・カーネル(1)

Kashimaらが2003年に提案
K (G1,G2 )    p(h) p(h')K '(l (h), l (h'))
hV1* h'V2*




h: グラフ G1 におけるパス
h’: グラフ G2 におけるパス
l(h): パス h のラベル（原子名）の列
K’(x,y): ラベル列間のカーネル関数
（例： K’(x,y)=1 if x=y, otherwise 0
）
Marginalized グラフ・カーネル(2)
G1
u3
u1
H
u2
C
O
u4
Cl
G2
H
v1 v2
H
h  (u1 , u2 , u3 ), h'  (v1 , v2 , v5 ) 
l (h)  (H, C, O), l (h' )  (H, C, O)
K ' (l (h), l (h' ))  1
v4
C
v3
v5
O
v6
H
H
h' '  (u1 , u 2 , u3 , u 2 , u 4 ) 
l ( h' ' )  ( H, C, O, C, Cl)
h' ' '  (v1 , v2 , v5 , v2 , v1 ) 
l ( h' ' ' )  ( H, C, O, C, H )
K ' (l ( h' ' ), l ( h' ' ' ))  0
Marginalized グラフ・カーネル(3)
x
H
O
C
φ(x)
Cl
H
C
N
( 0.03 0.03 0.0
H
C
H
O
C
H
H
C
H
0.02
0.0
0.01
0.002
)
Marginalized グラフ・カーネル(4)
p(v1 , v2 , v3 ) 
0.25 0.9  0.3  0.1
p(v2 , v4 , v2 , v3 ) 
0.25 0.3  0.9  0.3  0.1
p0 (vi )  0.25 pq (vi )  0.1
pa (v2 | v1 )  1.0
(1  p0 ) pa (v2 | v1 )  0.9
pa (v3 | v2 )  1 / 3
(1  p0 ) pa (v3 | v2 )  0.3
G1
START
0.25
0.25
0.25
0.25
O
0.3
v1
H
0.3
v2
0.9
C
0.3
0.9
0.9
0.1
v3
0.1
v4
Cl
0.1
END
0.1
Marginalized グラフ・カーネル(5)
p s ( v )  p0 ( v ) p q ( v )
pt (u | v) 
1  pq (v )
pq ( v )
pa (u | v) pq (u )
n
p(v1 ,, vn )  ps (v1 ) pt (vi | vi 1 )
i 2
Marginalized グラフ・カーネル(6)
 s (u1 , v1 )  ps(1) (u1 )  ps( 2) (v1 )
 t ((ui , vi ) | (ui 1 , vi 1 ))  pt(1) (ui | ui 1 )  pt( 2) (vi | vi 1 )
n
 ((u1 , v1 )(u2 , v2 )  (un , vn ))   s (u1 , v1 )  t ((ui , vi ) | (ui 1 , vi 1 ))
i 2
G1 u 1
H
G2
Cl
K
O
v1
u2 G1×G2 ( u1 , v1 ) ( u1 , v2 ) ( u1 , v3 )
v2
v3
H
H,K
H,O
H,H
Cl,K
Cl,O
Cl,H
( u2 , v1 ) ( u2 , v2 ) ( u2 , v3 )
Marginalized グラフ・カーネル(7)
K (G1,G2 )    p(h) p(h')K '(l (h), l (h')) 
hV1* h'V2*
 s  ( s (v))vV (V  V1  V2 )
 t  ( t (u' | u))u 'V ,uV


 (h)
h(V1V2 )*
 (h)   s  ( t ) n 1  1
hV * , |h|  n



 
n 1


K (G1,G2 )  
 (h)    s ( t ) 1



*
n 1 hV , |h| n
 n1
2

1
1

x

x
   1 /(1  x)
  s  (I  t ) 1


Marginalized グラフ・カーネル⇒逆行列の計算
Marginalized グラフカーネルの問題点

パス（の集合）だけを用いて化学構造を表現


反応中心などの情報を十分に取り入れることが困
難？
行列のサイズが大きく（数千×数千）なるため、
逆行列の計算に時間がかかる

すべてのトレーニングデータのペア（化合物のペア）
について、それぞれ、逆行列を計算することが必要
⇒ 構造情報(Morgan Index)との組み合わせ
Morganインデックス

化学構造の一意名を計算機により計算するために
1960年代に考案



CAS(Chemical Abstract Service)で利用
等価な原子に同じ番号（整数値）が与えられるような、
各原子への番号づけを計算
簡単な繰り返し計算による番号づけ

等価で無い原子にも同じ番号がつく可能性（でも、低い）
⇒ Marginalized グラフカーネルにおいて、原子名ととも
に、モーガンインデックスを利用
原子名およびモーガンインデックスの両者が一致するパス
のみを考慮
⇒ 部分構造に関する特徴も、ある程度、取り入れられる

Morganインデックスの計算法


すべての原子に番号１を割り当てる
すべての原子 x について以下を実行

x に結合している原子の番号を総和を、x の番号とする
1
2
1
1
1
1
1
1
1
1
N
O
1
2
2
1
4
3
2
2
3
2
2
1
5
4
3
7
5
5
7
5
6
7
1
1
N
1
3
N
3
O
O
3
O
O
5
O
計算機実験

MUTAG データを利用





標準的ベンチマークテストの一つ
化合物のサルモネラ菌の変異性への影響データ
125個の正例、６３個の負例を利用
各例1個のみをテストデータとし、他を学習データと
したテストを繰り返した
ソフトウェア
SVMソフトとして、GIST
(http://microarray.cpmc.columbia.edu/gist)
を利用
 他は C++ で記述

結論

モーガンインデックスの利用により以下を達成



Marginalizedカーネルと、同様の精度
他手法と比べても同等以上
数十倍以上、高速
今後の課題



他のインデックス手法の利用、開発
他手法との比較
大規模な計算機実験
参考文献

SVMおよびカーネル一般


バイオインフォマティクスにおけるカーネル


N. Cristianini & J. Shawe-Taylor: An Introduction to Support Vector
Machines and Other Kernel-based Learning Methods, Cambridge Univ.
Press, 2000. （日本語訳：大北剛：サポートベクターマシン入門, 共立出
版, 2005）
Kernel Methods in Computational Biology, MIT Press, 2005.
Marginalized Graph Kernel + Morgan Index

P. Mahe, N. Ueda, T. Akutsu, J-L. Perret, J-P. Vert: Extensions of
marginalized graph kernels, Proc. 21st Int. Conf. Machine Learning,
552-559, 2004.

Download Report