バイオインフォマティクスⅠ

ポストゲノム生命科学方法論

（榊原担当の第２回）

慶應義塾大学生命情報学科

榊原康文

遺伝子発現プロファイルの解析手法

①

クラスタリング（

_{Unsupervised ）}

_

◆ 階層クラスタリング，k-means法，自己組織化マップ （ＳＯＭ）

②

識別（

Supervised）

◆ 線形識別関数，k-近傍法，サポートベクターマシン （ブール関数，ニューラルネットワーク）

遺伝子発現データの識別

正常細胞 _識別： 腫瘍細胞 識別規則（関数） を学習する 予測： 未知のサンプル を識別する

？

マイクロアレイの遺伝子発現データを２つのクラスに分類： ◆ （例）がん細胞の遺伝子発現データと正常細胞の発現データ の識別 ◆ （例）遺伝子発現データによるがん診断

さまざまな識別の問題

（例）メタボリックシンドローム：内臓脂肪型肥満に高血糖・高血圧・ 高脂血症のうち2つ以上を合併した状態 正常の男子 症候群の男子 識別の属性： 腹囲， 血圧， 中性脂肪， HDLコレステロール， 血糖 識別関数： （≧85cm，≧130/85mmHg， ≧150mg/dL，≦40mg/dL，≧110mg/dL） サンプルから統計的に見出したもの

さまざまな識別問題と識別関数の学習と予測

◼ 化合物の分類（標的タンパクへの結合） ◼ タンパク質の分類（タンパク質の機能分類） ◼ 脳波形の分類（脳のシグナルの検出） ◼ などなど

学習データと識別関数を用いた予測 （統計的手法）

◆ 学習データ：２つのクラス（正と負のクラス）にすでに分類 されている遺伝子発現データの集合 ◆ 学習：学習データを用いて発現データを正と負のクラス に正確に分類する識別関数を学習 ◆ 予測：学習された識別関数を用いて，未分類（未知）の 発現データを識別してそのクラス（正または負）を予測

識別の例：

化合物

サポートベクター マシン （SVM) 入力データ： コーディング 作用する クラス 作用しない クラス

化合物

の分類

大量の結合 データ 学習

ターゲットタンパク質

（受容体）を固定

Brain-Machine Interface （BMI）

Hwang H et al., Neurofeedback-based motor imagery training for brain–computer interface (BCI), J Neurosci Methods 179:150–156, 2009.

コマンドの指令

パターン認識

脳波の計測

Magneto-encephalography (MEG) Electro-encephalography (EEG) Functional magnetic resonance imaging (fMRI)

BMIにおけるパターン識別：

脳波パターン１ 統計モデル 脳波の 特徴量 コマンド１ 無し [コマンド１]の実行 (0.1, 3.2) 統計モデル 脳波の 特徴量 コマンド１ 無し コマンド実行無し (-0.5, 0.0) 脳波パターン２

遺伝子発現データの識別

クラス１ （正常細胞） ＋ x₁ x₂ テンプレートマッチング法： ◆ 代表ベクトル（テンプレート，プロトタイプ）をクラス平均として， 入力ベクトルと各クラスの代表ベクトルとの間の距離を計算 して，最も近いクラスに識別 クラス２ （腫瘍細胞） ー 未知サンプル ？ クラス１平均 _{クラス２平均}

テンプレートマッチング法と線形識別関数

x₂ クラス１平均 クラス２平均 テンプレートマッチング法： ◆ 実は，クラス間の境界に線（超平面）を引いて，識別をする ことと同じ ⇒ 線形識別関数 線形識別関数（超平面） 等距離 0 ) ( ) ( ) ( 2 ) ( ) , ( ) , ( 2 2 2 1 2 1 2 1 2 1 2 2 2 1 2 1 2 1 2 2 1 2 1 1 1 1 2 1 = + − − − = − + − = − = =             x x x x x x x x x 境界線は， 間の ２つのクラスの領域の 二乗） の （ユークリッド距離 間の距離： の クラス平均 と 点 0 ) ( 2 1_{2 2}2 1 2 1 2 1 −  −  +    x 0 ) ( 2 1_{2 2}2 1 2 1 2 1 −  −  +    x x

線形識別（閾値）関数

◆ n 次元空間上の線形識別関数： n 次元ベクトル： x = (x₁,…,x_n) 重み係数ベクトル： _{w = (w1},…,w_n) 閾値係数： _{b (= w0)} ◆ 線形識別関数による分類： b x w b x w x w x g j n j j n n +  = +  + +  =



=1 1 1 ) (      −  + = のとき のとき 0 ) ( , 1 0 ) ( , 1 ) ( x g x g x f _   x₁ x₂ 0 ) (x = w₁ x₁ + w₂  x₂ +b = g ＋１ ー１ g(x)  0 0 ) (x  g

テンプレートマッチング法（マハラノビス距離）

x x₂ クラス１平均 クラス２平均 テンプレートマッチング法： ◆ データの分散を考慮して距離を計算 ⇒ マハラノビス距離 x マハラノビス距離： ２次曲線になる （ユークリッド距離） ) ( ) ( −₁  1 − ₁ = − x x d

識別規則の２つの方向

◆ 単純なテンプレート法から，「テンプレート（代表ベクトル）の 数を増やす」 ① k-近傍法： テンプレートの数を増やし，最も近いk個のテンプレートが属す るクラスの多数決を取る ② サポートベクターマシン： テンプレートの数を増やし，テンプレート間に線形識別関数を 引く

テンプレートを増やす

x₂ クラス１の 複数の代表ベクトル クラス２の 複数の代表ベクトル テンプレートマッチング法： ◆ 代表ベクトルを複数に増やす⇒ 入力ベクトルを最も近い代表ベクトルが属するクラスに分類 等距離にある折線 x

1-近傍法

x₁ x₂ クラス１の サンプルベクトル クラス２の サンプルベクトル 1-近傍法： ◆ すべてのサンプルをテンプレートとする⇒ 入力ベクトルを最も近いサンプルベクトルが属するクラスに分類 等距離にある折線 x

k-近傍法

x₂ クラス１の サンプルベクトル クラス２の サンプルベクトル k-近傍法： ◆ 入力ベクトルを最も近いk個のサンプルベクトルを選択し， k個の中で最も多いクラスに分類 k=3の場合：

サポートベクターマシン

x₁ x₂ クラス１の サポートベクトル クラス２の サポートベクトル ◆ 複数のサンプルベクトル（サポートベクター）からの距離 （マージン）を最大にする線形識別関数を引く マージンを最大化 x1 x₂ 線形識別関数（超平面） クラス１ 平均ベクトル クラス２ 平均ベクトル 0 ) ( 2 1_{2 2}2 1 2 1 2 1 − −  +  =  x p₁ p₂ サポートベクトル でない サポートベクトル でない q₁

サポートベクターマシン

サポートベクターマシンの学習： ◆ サポートベクターからマージンを最大にする線形識別関数 を求める 2 1 2 1 2 2 2 1 2 1 2 1 2 1 , ) ( ) (         + − = − = + − − = b w x x f すなわち， 場合： ２つの代表ベクトルの b x w x w b wx x f b w w w + + = + = = 2 2 1 1 2 1 ) ( ), , ( 閾値 重みベクトル 線形識別関数： とする ただし， とすると， サポートベクター： 合： サポートベクターの場 1 ), ( , , , 1 2 1 2 1 1 3 2 2 1 1 1 2 1 = + + + − =  +  +  = b wp wq wp wp b q p p w q p p i   

線形識別関数の学習

識別関数の学習問題： ◆ 学習データが与えられたときに，どのように適切な識別関数 を学習するのか？ x₁ x₂ 0 ) (x = w₁ x₁ + w₂ x₂ +b = g x₁ x₂ 学習データ −1 +1 −1 +1

線形識別関数の学習アルゴリズム

パーセプトロンのアルゴリズム ; 1 ; ; 0 ) ( 1 ||; || max ; 0 ); 0 , , 0 ( } 1 , 1 { ), , , ( )}, , ( , ), , {( 2 1 1 0 0 1 1 ここで， 学習サンプル for end if end then if to for repeat k k R y b b x y w w b x w y m i x R b w y x x x y x y x S i k k i i k k k i k i j j j j j j m m m n + = + =  + =  +   = = = = + −  = = + +                x₁ x₂ x₂ −1 +1

学習された重み係数と識別関数

① _{パーセプトロンのアルゴリズムによって学習されたサンプル S} を正しく識別する重み係数は，サンプルベクトルの線形結合 で表される： ② 線形識別関数



=  = m i i i i y x w 1   _ b x x y b x x y b x w x g m i i i i m i i i i +   = +  = +  =





= = 1 1 ) ( ) (       





     = のとき のとき 0 ) ( , 0 0 ) ( , 1 ) ( x g x g x f _   ベクトルの内積 )} , ( , ), , {(x₁ y_m x_m y_m S =   

サポートベクターマシン法 （SVM）

サポートベクターマシンの３つの特徴

①

カーネル関数：

① ベクトルの内積の効率的計算 ② 線形分離不可能な場合の高次元空間への写像 ②

汎化理論

① 高い予測精度 ② マージン最大化 ③

線形学習マシンの最適化：

① 凸２次計画問題，ラグランジュ未定乗数法

線形識別（閾値）関数

◆ 線形分離可能な学習パターンと決定境界の例

サポートベクターマシン法

(SVM)

線形分離不可能な場合 高次元(超空間)へマッピング

学習データを高次元へマッピング

F

（

カーネル関数

）

カーネル関数の種類

①

線形カーネル：

②

多項式カーネル：

③

_{RBF（radial basis function）カーネル：}

y

x

y

x

K

(



,



)

=







k

c

y

x

y

x

K

(



,



)

=

(







+

)

















₋

−

=

₂ 2

2

exp

)

,

(



y

x

y

x

K









前ページの例は，

_c=0

，

_k=2

の場合の多項式カーネルとなる

c

，

_k

は自由パラメータ（ハイパーパラメータ） RBFカーネルを持つヒルベルト空間は十分豊かな非線形 関数を含んでいる  は自由パラメータ（ハイパーパラメータ）

さまざまな種類のデータからの特徴抽出

① _{n 個の遺伝子がスポットされたマイクロアレイデータ} ⇒ n 次元ベクトル：

x = (x

₁

,…,x

_n

)

② 「（特徴）ベクトル」で表されたデータに関しては，様々な解析 手法が存在する クラスタリング，線形識別関数，主成分分析（PCA)，など ③ 「非数値的な，構造的なデータ」から，どのように特徴ベクトル を抽出するか？ ④ DNA配列やアミノ酸配列（タンパク質），ペプチドなどの配列， タンパク質立体構造，糖鎖，低分子化合物，などの種々の データ

配列データのベクトル化

配列データから n 次元の実数値ベクトルへの変換

 ： 

*

→ R

n

：

_{w = GGCAATTGA → x}

n

₌

(1, 10, 3, 0.5) ① カウントベクトル：最も単純なベクトル化 配列中の各塩基（アミノ酸）の出現頻度をベクトルとする すなわち，（塩基やアミノ酸）組成のベクトルとなる （例） DNA配列の場合：  : GGCAATTGA → (3,1,3,2) ４次元ベクトル （_Aの出現回数，_Cの出現回数，_Gの出現回数，_Tの出現回数） （例） アミノ酸配列の場合： ２０次元ベクトル  : ALTDTGLST → (1,0,1,0,0,1,0,0,0,2,0,0,0,0,0,1,3,0,0,0) A,C,D,E,F,G,H,I,K,L,M,N,P,Q,R,S,T,V,W,Y カウントベクトルは，配列の特徴を十分に表したベクトルであるか？ 類似した配列と異なる配列をカウントベクトルで分類できるか？

配列データのベクトル化

文字列ベクトル ② k-スペクトラムベクトル： すべての長さ k 文字列の出現頻度を数えてベクトル化する （例） DNA配列の2-スペクトラムベクトル： １６次元ベクトル （_{AA,AC,AG,AT,CA,CC,CG,CT,GA,GC,GG,GT,TA,TC,TG,TT}）  : GGCAATTGA → (1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1) （例） アミノ酸配列の3-スペクトラムベクトル：２０3_{（＝８０００）次元ベクトル}  : ALTDTGLST → ( 0, 0, … , 1, … , 1, … … , 0 ) AAA,AAC,…,ALT,…,DTG,……,YYY k-スペクトラムベクトルは，カウントベクトルよりも特徴ベクトルとして精度

配列データのベクトル化

文字列ベクトルの問題点： ① ベクトルの次元数が指数関数的に増加してしまう ◆ 例えば，アミノ酸のk-スペクトラムベクトルの次元数は，20k 次元 ② ベクトルの内積であれば次元数が増加しても効率よく計算 する手法が存在する ◆ 配列データの特徴ベクトルを直接扱わないで，その内積を計算する ③ 文字列ベクトルのカーネル関数と効率的計算 ⇒ 「文字列カーネル関数」

文字列カーネル関数

① ベクトルの内積であれば次元数が指数関数的に増加しても 効率よく計算する手法が存在する ② ベクトルの内積を計算する時には，必ずしもベクトルのすべ ての次元数の要素を直接取り扱う必要は無い ◆ 例えば，スペクトラムベクトルでは，与えられた配列中に現れない文 字列のベクトル値は０となり，その要素の内積を計算しても０となる ため，内積を計算する時には省略することができる  : GGCAATTGA → ( 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1) AA,AC,AG,AT,CA,CC,CG, … TT ③ 文字列の「カーネル関数」の定義： ２つの配列 v と w に対して ) ( ) ( ) , (v w v w K =  

文字列カーネルを用いたサポートベクターマシン

① 配列データから特徴ベクトルへ変換  したベクトル空間上 で定義される線形識別関数 ② 特徴ベクトルの内積：カーネル関数 ③ 文字列カーネル関数を用いた線形識別関数による識別と 予測： b w v K y b w v y w g m i i i i m i i i i +  = +     =





= = 1 1 ) , ( )) ( ) ( ( ) (





) ( ) ( ) , (v w v w K =  

カーネル関数の計算：スペクトラムカーネル

k-スペクトラムカーネル K_k(v,w)： k-スペクトラムベクトルの内積 ① ２つの配列 v, w から長さ k のすべての部分文字列を切り出しそれぞれ list_k(v), list_k(w) とする ② 内積を表す変数 innerproduct を用意して，０に初期化する ③ _{listk(v) の中の各文字列に対して， listk(w) 中に同じ文字列が存在する} 場合に innerproduct を１増加する ; 1 ) ( ; 0 ) ( ; 1 ) ( ; 2 ) ( ; 0 ) ( ; 0 } , , , , { ) ( }, , , , , { ) ( 3 , , 3 3 3 3 3 3 3 + →  + →  + →  + →  + →  = = = = = = ct innerprodu v list ct innerprodu v list ct innerprodu v list ct innerprodu v list ct innerprodu v list ct innerprodu w list v list k w v ATA TAT ATA CAT GCA CAT ACA TAC ATA CAT ATA TAT ATA CAT GCA CATACAT GCATATA

カーネル関数の計算：スペクトラムカーネル

① _{DNA配列の場合では， k-スペクトラムベクトルの次元数} は４k のため，k-スペクトラムベクトルの内積の直接の計算 では，４k 時間かかる ◆ 上記の例の k = 3 の場合，43 = 64 次元 ② _{上記のk-スペクトラムカーネルのアルゴリズムの計算時間} は， O(|v|  |w|) ◆ 上記の例の場合，両方の配列中に現れた長さ３の文字列は全部 で６種類，したがって６４－６＝５８種類の次元数を省略することが できた ③ O(|v| + |w|)の計算時間で計算する効率的なアルゴリズム が存在する

カーネル関数の応用：リモートホモログの検出

BLASTなどの相同性検索では，検出できないリモートホモロジー （superfamily）の検出 ⇒ 文字列カーネル関数を用いた検出 ◆ 配列の比較では検出できないような，進化関係にある遠縁配列（リモート ホモログ）の検索 ◆ 一般に，配列間に30%の一致が認められれば，それは相同性がある． ところが，15～20%の一致率でも，立体構造や機能の一致が見られる ⇒リモートホモログの考え ◆ 配列相同性の非常に低い複数のタンパク質が共通の立体構造をとる例 （グロビンフォールドなど）が数多く知られており，これらのタンパク質群は リモートホモログと呼ばれている

◆ （例）ATP binding protein とchaperone proteinは，アミノ酸配列の相同性は

非常に低いため通常の配列比較では相互の関連が見出せないが，両者の3 次元構造上の類似性は非常に高く，また機能的にも関連が強い

SCOPデータベース

タンパク質の立体構造を階層的に分類した代表的なデータベース ① タンパク質の立体構造を形状を中心に，人手で，階層的に，分類した データベース ② SCOPにおける構造類似性の評価は，タンパク質単位でなくドメイン 単位で行われている点が特徴 class1

fold1 fold2 fold n

superfamily1 superfamily2 superfamily i superfamily j

family1 family2 family3

Class: Fold: Superfamily: Family: SCOP class m Root:

SCOPデータベース

SCOPの分類 ◆ class: 構成している主要な二次構造による分類 ⇒ _{all α, all β, α/β, α+β, その他（マルチドメイン, 膜タンパク質, 小さいタン} パク質, コイルドコイル, ペプチド, 人工タンパク質, 低解像度の構造) ◆ common fold: 二次構造の構成，その空間的な配置が共通しているもの ◆ superfamily: 配列の一致度は高くないが，構造や機能が共通の進化的起 源をもっていると判断されるもの ◆ family: 配列一致度が30%以上，もしくは構造や機能が非常に似ているもの Root: scop

Class: All alpha proteins [46456] Fold: Globin-like [46457]

core: 6 helices; folded leaf, partly opened Superfamily: Globin-like [46458]

Family: Globins [46463] Heme-binding protein

SCOPデータベース

SCOPデータベース

SCOPの分類（例題）

◆ Common fold: Globin-like 中のsuperfamily

◆ Superfamily: Globin-like 中のfamily

Truncated hemoglobin： lack the first helix (A)

Nerve tissue mini-hemoglobin (neural globin)：

lack the first helix but otherwise is more similar to conventional globins than the truncated ones

Globins：

Heme-binding protein

Phycocyanin-like phycobilisome proteins：

oligomers of two different types of globin-like subunits containing two extra helices at the N-terminus binds a bilin chromophore

Globin-like：

alpha-helical ferredoxin：

階層別のタンパク質の検索手法

① _{Fold：２次構造予測手法（ニューラルネットワーク，など）} ② Superfamily：PSI-BLAST，隠れマルコフモデル，など ⇒ 文字列カーネル関数とサポートベクターマシン ③ Family：BLAST，などの相同性検索 superfamily内の類似性（リモートホモロジーの検出） ⇒ 文字列カーネル関数＋サポートベクターマシン superfamily1 superfamily2

family1 family2 family3

リモートホモログの検出実験

◆ SCOPデータベースを用いたリモートホモロジーの検出の実験 PSI-BLAST 隠れマルコフモデル 文字列カーネル SVM