バイオインフォマティクス ( 第 5 回 ) 慶應義塾大学生命情報学科 榊原康文
多重アライメントの解 0 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 Q -6 2 0-6 -4-25 -34-52 2 S -32 5 30 4 6-5 -4-32 3 Y -48-4 2 38 27 8 0 4 P -64-27 -2-3 22 4 32 4 5 R -80-43 -8-9 6 25 62 44 6 Y -96-59 -34-35 5 9 46 66 多重アライメント : QTSYTRY QT-YTRK QS-YPRY s(a, -)=s(-, a)=-8, s(-, -)=0
クラスタリングとは 類似性にしたがって分類 ( グループ分け ) クラスター : 内部の要素はお互いに似ているが 外部のものとは異なる集合 クラスタリングにより 3 つのグループに分類
遺伝子のグループ化 遺伝子 ( それがコードするタンパク質 ) の機能の同定 同じ機能を持つ遺伝子をグループ化 ( アミノ酸 ) 配列の相同性に基づくグループ化 タンパク質のファミリー, スーパーファミリー, など 2 マイクロアレイデータの発現プロファイルを用いた遺伝子のクラスタリング
DNA チップとマイクロアレイ解析
DNA マイクロアレイによる遺伝子発現プロファイルの解析法 対象とする遺伝子の mrna から cdna を合成 ( 長さを 500 塩基程度にそろえる ) ガラス基板上にスポットし乾燥 固定化 正常細胞 mrna cdna+ 蛍光色素 Cy3( 緑 ) 腫瘍細胞 mrna cdna+ 蛍光色素 Cy5( 赤 ) 蛍光強度差を検出
遺伝子発現プロファイルのクラスタリング 発現情報のみを用いて発現パターンの類似した遺伝子をクラスター ( グループ ) にしていく 酵母 (S. cerevsae) の既知遺伝子で, 似た機能をもつものは同じクラスターに分類されることを確認 (Esen et al.,pnas, 998.) 赤 : 好気性 緑 : 嫌気性 クラスタリングによって得られた結果に対し, 同一クラスター内の既知遺伝子の生物学的な注釈 ( アノテーション情報 ) をもとに未知遺伝子の機能を推定
マイクロアレイデータの発現プロファイル 条件 ( 時間 ) 遺伝子 遺伝子 2 遺伝子 6 条件 条件 2... 条件 0 遺伝子 遺伝子 2 条件 2 ( 時間 2) 発現プロファイル. 条件 0 ( 時間 0) 遺伝子 6
発現プロファイルのクラスタリング 発現プロファイル 遺伝子 遺伝子 2. 条件 条件 2... 条件 0 クラスター クラスター 2 遺伝子 6 クラスター 3
クラスタリングを用いたマイクロアレイ解析 発現データ ( 発現プロファイル ) M condtons 行 : 遺伝子 (cdna, EST, etc) 列 : 条件 ( サンプル, 時間, etc) からなる N M 行列 要素 : 各遺伝子の各条件における発現レベル N genes クラスタリング 行 / 列成分に適用
マイクロアレイ解析の実際例 び慢性大 B 細胞リンパ腫 (dffuse large B-cell lymphoma) 同一の組織学的所見だが, 臨床経過が著しく異なる患者の存在 階層クラスタリングを用いてがん化前の分化状態で分類 ( 臨床経過の予測が可能に ) マイクロアレイ実験からの大規模なデータは, コンピュータによる解析が不可欠!! Dstnct types of dffuse large B-cell lymphoma dentfed by gene Expresson proflng, Alzadeh et al., Nature, 2000
クラスタリングの対象 : 二通り 条件にしたがって, 遺伝子をクラスタリング 基本 : 遺伝子の分類 協調的に機能する / 類似の遺伝子セットの同定 ( 仮定 : 類似遺伝子なら発現プロファイルも似ている ) 典型的な発現パターンの同定 ( 細胞周期, 胞子形成, etc) 2 遺伝子にしたがって, 条件をクラスタリング サンプルの分類 ( 組織の状態の分類, 疾患の分類 ) 条件の検定 ( 既知の機能分類に分けられたかどうか, etc)
クラスタリングとは 類似性にしたがって分類 ( グループ分け ) 良いクラスタリングの条件 : 内部の要素はお互いに似ているが, 外部のものとは異なる集合 良いクラスタリング 悪いクラスタリング
クラスタリング解析 類似性にしたがって分類 ( グループ分け ) [ 類似性の尺度 ] Dstance-based : ユークリッド距離, マンハッタン距離, etc Correlaton-based : ピアソン相関係数, cosne 相関係数, etc Lnk-based : 隣接共通ノード, 密度, etc ( グラフ理論 ) Pattern-based : 2 3 4 5 6
類似性の尺度入力ベクトル x = (x,, x n ), y = (y,, y n ) ユークリッド距離 : マンハッタン距離 : ( ピアソン ) 相関係数 : = - = n E y x y x d 2 ) ( ), (. ), ( = - = n M y x y x d = = = - - - - = 2 2 ) ( ) ( ) )( ( ), ( C y y x x y y x x y x d ( 値域 :- d C )
どの尺度を使えばいいのか? どの尺度を使うか 何を検出したいのか 4 3 2 B A ユークリッド距離 de(a, B) = 3.54 de(a, C) = 0 C 2 3 4.0 2.0 3.0 4.0 A.0.0.5.5 B 2.5 2.5 3.5 3.5 C.5.5.0.0 ピアソン相関係数 dc(a, B) = dc(a, C) = -
どの尺度を使えばいいのか? どの尺度を使うか 何を検出したいのか Dstance-based : 発現変化の絶対量をみる ( 一般に, マンハッタン距離の方が outlner に対してロバスト ) Correlaton-based : 発現変化の相関をみる ( ピアソン相関係数, など ) 条件が経過時間ならば Corrleaton-based 条件が様々な環境 ( 熱ショック, 飢餓 ) ならば Dstance-based
クラスタリングアルゴリズム 類似性にしたがって分類 ( グループ分け ) Unsupervsed ( 教師なし, 事前ラベルなし ) : 階層クラスタリング, k-means 法, fuzzy k-means 法, SOM( 自己組織化マップ ) 法 [ 目標 ] クラスタ内の類似度 = 最大, クラスタ外の類似度 = 最小
階層的クラスタリング ボトムアップ的手法 Step. 各要素分のクラスタを考える Step2. 全てのペアの類似度を調べ, 類似度が最大のペアを つにマージする 現在のクラスタペアをマージしたクラスタを生成 Step3. Step4. 全てのペアについて類似度を再計算 クラスタが つになるまで,Step2, 3 を繰り返す
階層的クラスタリング 階層的クラスタリングの結果 : 系統樹 (dendrogram)
階層クラスタリング クラスタの類似度の計算 最短距離法. クラスタ間の最短距離 最長距離法. クラスタ間の最長距離 群間平均法. クラスタ間の平均距離 ), ( mn ), (, y x d G G d G j y G x j = ), ( max ), (, y x d G G d G j y G x j = ), ( ), (, y x d G G G G d G j y G x j j =
階層クラスタリング クラスタの類似度の計算 最短距離法. クラスタ間の最短距離伸長したクラスタが得られる 最長距離法. クラスタ間の最長距離コンパクトなクラスタが得られる 群間平均法. クラスタ間の平均距離 平均的なサイズのクラスタが得られる
階層クラスタリング クラスタの類似度の計算 A C 最短距離法 A, C をマージ 最長距離法 B 群間平均法
階層クラスタリング クラスタの類似度の計算 A C 最短距離法 最長距離法 B, C をマージ B 群間平均法
階層クラスタリング クラスタの類似度の計算 A C 最短距離法 最長距離法 B 群間平均法 A, C をマージ
階層クラスタリング Step. データセット Step2-. 類似度計算 Step2-2. マージ Step3. 類似度再計算
階層クラスタリング例 : ユークリッド距離 ( 群間平均法 ) 入力ベクトル [] [2] A: 0 B: 2 2 C: 3 3 D: 0 - E: - 距離行列 A: B: C: D: B: 2.236 C: 3.605.44 D:.44 3.605 5.000 E: 2.236 3.62 4.472 2.236 B C 系統樹 E D A E 距離マップ B C A D
階層クラスタリング例 : ユークリッド距離 E E A D B C B C A D 最短距離法 最長距離法
階層クラスタリング例 : ピアソン相関係数 ( 群間平均法 ) [] [2] A: 0 B: 2 2 C: 3 3 D: 0 - E: - A: B: C: D: B: 0.292 C: 0.292 0.000 D:.000.707.707 E:.707.000.000.707 入力ベクトル距離行列距離マップ系統樹 A B D C E B D E C A = = = = 2 2 ), ( C y x y x y x d
階層的クラスタリングの応用例と問題点 Systematc Varaton n gene expresson patterns n Human cancer cell lnes, Ross, D., et al. Nature Genetcs, 2000 がんの種類に関して, 関連する遺伝子を正しくグループ分けすることができた CNS: 中枢神経,renal: 腎臓,ovaran: 卵巣,leukaema: 白血病, colon: 結腸,melanoma: メラノーマ ( 黒色腫 ) クラスタ間の境界が不明瞭
k-means 法 トップダウン的手法 Step. Step2. 最終的なクラスタ数 k を設定 任意の k 個のクラスタ中心を設定 (random) Step3-. 各要素を最も近いクラスタ中心に割り当てる ( 一般に, ユークリッド距離に関して ) Step3-2. Step4. 各クラスタ中心を, そのクラスタ内の全要素の重心で置き換える 重心が変化しなくなるまで,Step3 を繰り返す
k-means 法 Step. データセット Step2. クラスタ中心設定 2 Step3-. クラスタ割り当て Step3-2. 新クラスタ中心算出 2 2 2 2 2 2 2 2 2 2 2 2 2 2
k-means 法 : ユークリッド距離 C C B B E E D A D A k=2 k=3
k-means 法の問題点 得られた結果は k 個のクラスタのみ 各クラスタ間の関係などは不明 初期値に強く依存する クラスタ数 : k 多くのヒューリスティックな解法が提案 ( ベイズ推論を用いる, など ) クラスタ中心の初期設定 事前に制約を設定する (Constraned k-means, etc)
SOM ( 自己組織化マップ ) 法 2 層ニューラルネットワークに基づく学習 Step. Step2. Step3. 最終的なクラスタ数 k, 繰り返し回数 T を設定 k 個のクラスタ中心ノード配列を設定 (random) 各要素に最も近いクラスタ中心 ( 最整合ノード ), および最整合ノードの半径 () 以内の近傍クラスタ中心を決定 最整合ノードおよびその近傍ノードを, ( d, ) 該当要素の方向へ移動させる だけ Step4. 繰り返し回数 T に達するまで, もしくは全てのクラスタ中心が変化しなくなるまで,Step3 を繰り返す
まとめ クラスタリングによるマイクロアレイ解析は一般的だが 様々なアルゴリズムが存在する それぞれに長所 短所があるので, 目的に合わせて最適なアルゴリズム パラメータを選択する クラスタリング結果の妥当性 有意性評価は困難 ランダムデータからでも相関のあるクラスタは生成される. 注意深く, 結果を解釈する ( 生物学的に ) 2. 複数のソース (DNA 配列情報, etc) と組み合わせて有意性の高い結果を得るようにする
階層クラスタリング演習問題 下記の 4 つの入力ベクトルを, 階層クラスタリングを用いて, クラスタリングした結果の系統樹を書きなさい. この時, 距離関数はユークリッド距離と群間平均法を用いなさい. 入力ベクトル 系統樹