バイオインフォマティクス
（第５回）
慶應義塾大学生命情報学科
榊原康文
QTSYTRY
QT-YTRK
QS-YPRY
多重アライメントの解
i 0 1 2 3 4 5 6 7 j Q T S Y T R Y Q T - Y T R K 0 0 -9 -20 -44 -52 -63 -72 -90 1 Q -16 21 10 -6 -14 -25 -34 -52 2 S -32 5 30 14 6 -5 -14 -32 3 Y -48 -11 14 12 38 27 18 0 4 P -64 -27 -2 -3 22 41 32 14 5 R -80 -43 -18 -19 6 25 62 44 6 Y -96 -59 -34 -35 5 9 46 66 多重アライメント： s(a, -)=s(-, a)=-8 , s(-, -)=0クラスタリングとは
◆類似性にしたがって分類 (グループ分け)
クラスター : 内部の要素はお互いに似ているが、外部のもの とは異なる集合 クラスタリングにより ３つのグループに分類遺伝子のグループ化
遺伝子（それがコードするタンパク質）の機能の同定
同じ機能を持つ遺伝子をグループ化
① （アミノ酸）配列の相同性に基づくグループ化
◆タンパク質のファミリー，スーパーファミリー，など
② マイクロアレイデータの発現プロファイルを用いた
遺伝子のクラスタリング
DNAマイクロアレイによる
遺伝子発現プロファイルの解析法
対象とする遺伝子の mRNAから cDNA を合成 （長さを 500塩基程度にそろえる ） ガラス基板上に スポットし乾燥・固定化 正常細胞 ↓ mRNA ↓ cDNA+ 蛍光色素Cy3(緑) 腫瘍細胞 ↓ mRNA ↓ cDNA+ 蛍光色素Cy5(赤) 蛍光強度差を検出遺伝子発現プロファイルのクラスタリング
赤：好気性 緑：嫌気性 発現情報のみを用いて発現パターンの類似 した遺伝子をクラスター（グループ）にし ていく ◼ 酵母（S. cerevisiae）の既知遺伝子で，似た機能 をもつものは同じクラスターに分類されることを 確認（Eisen et al.,PNAS, 1998.） ◼ クラスタリングによって得られた結果に対し，同 一クラスター内の既知遺伝子の生物学的な注 釈（アノテーション情報）をもとに未知遺伝子の 機能を推定マイクロアレイデータの発現プロファイル
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● 条件１ （時間１） 条件２ （時間２） 条件10 （時間10） ● ● ● 遺伝子１ 遺伝子２ 遺伝子16 ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● 条 件 １ 条 件 ２ 条 件 10．．．
遺伝子１ 遺伝子２ 遺伝子16．
．
．
発
現
プ
ロ
フ
ァ
イ
ル
発現プロファイルのクラスタリング
● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● 条 件 １ 条 件 ２ 条 件 10．．．
遺伝子１’ 遺伝子２’ 遺伝子１６’．
．
．
クラスター１ クラスター２ クラスター３発
現
プ
ロ
フ
ァ
イ
ル
クラスタリングを用いたマイクロアレイ解析
◆
発現データ (発現プロファイル)
– 行 :
遺伝子 (ｃDNA, EST, etc)– 列 :
条件 (サンプル, 時間, etc) N genes M conditionsからなる N × M 行列
クラスタリング – 行 / 列成分に適用– 要素 :
各遺伝子の 各条件における発現レベル“Distinct types of diffuse large B-cell lymphoma identified by gene Expression profiling”, Alizadeh et al., Nature, 2000
び慢性大B細胞リンパ腫
(diffuse large B-cell lymphoma) 同一の組織学的所見だが， 臨床経過が著しく異なる患者の存在 階層クラスタリングを用いて がん化前の分化状態で分類 (臨床経過の予測が可能に)
マイクロアレイ解析の実際例
マイクロアレイ実験からの 大規模なデータは， コンピュータによる 解析が不可欠！！クラスタリングの対象：二通り
① 条件にしたがって，
遺伝子
をクラスタリング
– 基本：遺伝子の分類 – 協調的に機能する / 類似の遺伝子セットの同定 – 典型的な発現パターンの同定 (細胞周期, 胞子形成, etc)② 遺伝子にしたがって，
条件
をクラスタリング
– サンプルの分類（組織の状態の分類，疾患の分類） – 条件の検定 (既知の機能分類に分けられたかどうか, etc) (仮定 : 類似遺伝子なら発現プロファイルも似ている)クラスタリングとは
◆
類似性にしたがって分類 (グループ分け)
良いクラスタリングの条件 : 内部の要素はお互いに似ているが，
外部のものとは異なる集合
クラスタリング解析
◆ 類似性にしたがって分類 (グループ分け)
[類似性の尺度]
Distance-based : ユークリッド距離, マンハッタン距離, etc
Correlation-based : ピアソン相関係数, cosine相関係数, etc
Link-based : 隣接共通ノード, 密度, etc (グラフ理論)
Pattern-based :
類似性の尺度
入力ベクトル x = (x
1, …, x
n), y = (y
1, …, y
n)
◆ユークリッド距離 :
◆マンハッタン距離 :
◆（ピアソン）相関係数 :
=-=
n i i i Ex
y
x
y
d
1 2)
(
)
,
(
.
)
,
(
1
=-=
n i i i Mx
y
x
y
d
= = =-=
1 2 1 2 1)
(
)
(
)
)(
(
)
,
(
i i i i i i i Cy
y
x
x
y
y
x
x
y
x
d
（値域：-1≦ dC ≦ 1）どの尺度を使えばいいのか？
0 1 2 3 4 1 2 3 4 1.0 2.0 3.0 4.0 A 1.0 1.0 1.5 1.5 B 2.5 2.5 3.5 3.5 C 1.5 1.5 1.0 1.0 B A Cdc(A, B) = 1
dc(A, C) = -1
dE(A, B) = 3.54
dE(A, C) = 1
ユークリッド距離 ピアソン相関係数 どの尺度を使うか 何を検出したいのかどの尺度を使えばいいのか？
◆ Correlation-based : 発現変化の相関をみる ◆ Distance-based : 発現変化の絶対量をみる どの尺度を使うか 何を検出したいのか (ピアソン相関係数，など) (一般に，マンハッタン距離の方がoutlinerに対してロバスト) 条件が経過時間ならば Corrleation-based 条件が様々な環境(熱ショック, 飢餓)ならば Distance-basedクラスタリングアルゴリズム
Unsupervised (教師なし, 事前ラベルなし) :
階層クラスタリング, k-means法
,
fuzzy k-means法, SOM(自己組織化マップ)法
クラスタ内の類似度 = 最大, クラスタ外の類似度 = 最小
[目標]
階層的クラスタリング
◼ ボトムアップ的手法 • Step1. 各要素分のクラスタを考える • Step2. 全てのペアの類似度を調べ， 類似度が最大のペアを１つにマージする • Step3. 全てのペアについて類似度を再計算 • Step4. クラスタが1つになるまで，Step2, 3 を繰り返す 現在のクラスタペアをマージしたクラスタを生成階層的クラスタリング
系統樹（dendrogram） 階層的クラスタリングの結果：
階層クラスタリング
◼ クラスタの類似度の計算 • 最短距離法. クラスタ間の最短距離 • 最長距離法. クラスタ間の最長距離 • 群間平均法. クラスタ間の平均距離 ) , ( min ) , ( , d x y G G d j i y G G x j i = ) , ( max ) , ( , d x y G G d j i y G G x j i = ) , ( | || | 1 ) , ( , d x y G G G G d j i y G G x j i j i = 階層クラスタリング
◼ クラスタの類似度の計算 • 最短距離法. クラスタ間の最短距離 • 最長距離法. クラスタ間の最長距離 • 群間平均法. クラスタ間の平均距離 伸長したクラスタが得られる コンパクトなクラスタが得られる 平均的なサイズのクラスタが得られる階層クラスタリング
◼ クラスタの類似度の計算 A B C • 最短距離法 • 最長距離法 • 群間平均法 A, C をマージ階層クラスタリング
◼ クラスタの類似度の計算 A B C • 最短距離法 • 最長距離法 • 群間平均法 B, C をマージ階層クラスタリング
◼ クラスタの類似度の計算 A B C • 最短距離法 • 最長距離法 • 群間平均法 A, C をマージ階層クラスタリング
Step1. データセット Step2-1. 類似度計算
階層クラスタリング例：ユークリッド距離 （群間平均法）
[1] [2] A: 1 0 B: 2 2 C: 3 3 D: 0 -1 E: -1 1 A: B: C: D: B: 2.236 C: 3.605 1.414 D: 1.414 3.605 5.000 E: 2.236 3.162 4.472 2.236 入 力 ベ ク ト ル 距 離 行 列 距離マップ 系 統 樹 A B D C E A B C D E階層クラスタリング例：ユークリッド距離
最短距離法 最長距離法 A B C D E B D A C E階層クラスタリング例：ピアソン相関係数 （群間平均法）
[1] [2] A: 1 0 B: 2 2 C: 3 3 D: 0 -1 E: -1 1 A: B: C: D: B: 0.292 C: 0.292 0.000 D: 1.000 1.707 1.707 E: 1.707 1.000 1.000 1.707 入 力 ベ ク ト ル 距 離 行 列 距離マップ 系 統 樹 A B D C E B D E C A
= = = = 1 2 1 2 1 ) , ( i i i i i i i C y x y x y x d階層的クラスタリングの応用例と問題点
“Systematic Variation in gene expression patterns in
Human cancer cell lines”, Ross, D., et al. Nature Genetics, 2000
◼ がんの種類に関して，関連する遺伝子を正しくグループ分け
することができた
CNS：中枢神経，renal：腎臓，ovarian：卵巣，leukaemia：白血病， colon：結腸，melanoma：メラノーマ（黒色腫）
k-means法
◼ トップダウン的手法 • Step1. 最終的なクラスタ数k
を設定 • Step2. 任意のk
個のクラスタ中心を設定 (random) • Step3-1. 各要素を最も近いクラスタ中心に割り当てる (一般に，ユークリッド距離に関して) • Step4. 重心が変化しなくなるまで，Step3 を繰り返す 各クラスタ中心を，そのクラスタ内の全要素の重心で 置き換える • Step3-2.1 2 Step1. データセット Step2. クラスタ中心設定 Step3-1.クラスタ割り当て Step3-2. 新クラスタ中心算出
k-means法
1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2k-means法：ユークリッド距離
k=2 k=3 A B D C E A B D C Ek-means法の問題点
◼ 初期値に強く依存する クラスタ数 :k
多くのヒューリスティックな解法が提案 (ベイズ推論を用いる，など） クラスタ中心の初期設定事前に制約を設定する (Constrained k-means, etc)
◼ 得られた結果は
