明治大学大学院理工学研究科 総合講義C バイオインフォマティクスにおける 数理的手法 阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター バイオインフォマティクス(1) • 生物学+情報科学 (+数理科学+統計学+物理学+化学+医学+農学+...) • 1990年代に大きく発展 ← ゲノム計画の急速な進展 (既に数百種類以上の生物種のゲノムが決定) • 情報解析の必要性 – DNA配列⇔プログラムのオブジェクトコード – 意味の解析が必要 – 配列以外のデータ解析も重要 • 立体構造、遺伝子発現データ、代謝パスウェイなど バイオインフォマティクス(2) • 主要トピック – – – – – – – データベース構築 遺伝子発見、遺伝子制御領域推定 配列検索、配列比較、進化系統樹 タンパク質構造予測、機能予測、相互作用予測 遺伝子発現データ解析 ネットワーク構造解析 化合物の性質推定 • 分野としての特徴 – 多くのデータベース・ソフトウェアがWEBなどから利用可能 – 研究成果が(生物学研究への)応用に直結 バイオインフォマティクスにおけるデータベース • 多くの重要なデータベースがWEBからアクセ ス可能 – DNA配列: GenBank, EMBL, DDBJ – タンパク質配列: UniProt (Swissprot) – タンパク質立体構造: PDB – モチーフ: Prosite, Pfam, … – 代謝パスウェイ: KEGG 講義内容 • 分子生物学における基礎事項 • 配列検索(動的計画法による配列アライメン ト) • カーネル法によるタンパク質構造予測 遺伝子とタンパク質 • 遺伝情報の流れ (セントラルドグマ) – DNA⇒RNA⇒タンパク質 • 遺伝子 – DNA配列中で直接的 に 機能する部分 • ゲノム DNA エキソン エキソン 転写制御領域 (プロモーターなど) 転写 ・ スプライシング mRNA GGU – アミノ酸(20種類)の鎖 GCA 翻訳 GGU → Gly GCA → Ala – 遺伝情報の総体 • タンパク質 エキソン タンパク質 • DNA: A,C,G,Tの4文 字の並び • DNAは二重ラセン構造 ⇒相補鎖 A C T DNAとタンパク質 • タンパク質: アミノ酸(20 種類)の鎖 • 固有の三次元構造をとる ものが多い • 構造は機能と深く関連 T G A G C A T C G (図はrasmolを用いて作成) DNAとアミノ酸 • DNA: A,C,G,Tの4 文字の並び • タンパク質: アミノ 酸の鎖 • アミノ酸: 20種類 • DNA3文字がアミノ 酸1文字に対応 コード表 2文字目 T T 1 文 字 目 C TTT TTC F TTA TTG L C CTT CTC CTA CTG A ATT ATC ATA I ATG M G GTT GTC GTA GTG L V TCT TCC TCA TCG CCT CCC CCA CCG ACT ACC ACA ACG GCT GCC GCA GCG A S P T A TAT TAC TAA TAG G Y stop CAT CAC H CAA CAG TGT TGC TGA TGG C stop W Q CGT CGC CGA CGG R AAT AAC N AGT AGC S AAA AAG K AGA AGG R GAT GAC D GAA GAG E GGT GGC GGA GGG G アミノ酸とタンパク質 • アミノ酸:側鎖の違 いにより20種類 • タンパク質:アミノ酸 の鎖 アミノ酸 R H 側鎖 OH C N アミノ基 C カルボシキル基 H H O タンパク質 R N H C H H C O N H C R ペプチド結合 O C 側鎖の例 Ala アラニン Phe フェニル アラニン CH 3 CH HC C Val バリン H3 C CH 3 CH O CH HC Asp アスパラ ギン酸 CH CH 2 O C - His ヒス チジン Cys シス テイン HN SH + NH CH 2 CH 2 CH 2 Gly グリシン H 配列検索:内容 • 配列検索と配列アライメント • ペアワイズ・アライメント • 配列検索の実用プログラム 配列検索 • バイオインフォマティク スにおける基本原理 – 配列が似ていれば機能 も似ている 機能未知の配列 VLPIKSKLP...... 配列検索 配列データベース – ただし、例外はある • 配列検索の利用法 – 実験を行い機能未知の配列 が見つかった – データベース中で類似の配 列を検索 – 機能既知の類似の配列が見 つかれば、その配列と似た機 能を持つと推定 DFECILTSKLG..... . ACILTSTRE...... VLPIKSDLP...... HPFACILPDEL...... 類似配列 VLPIKSDLP...... 配列アライメント • 配列の類似性の検出に 利用 • バイオインフォマティクス の最重要技術の一つ • 文字間の最適な対応関 係を求める(最適化問 題) • 配列長を同じにするよう に、ギャップ記号(挿入、 欠失に対応)を挿入 A L G F G S L Y G A L G G V S V G A L G F G A L G S L Y G G V S V G スコア行列(置換行列) • 残基間(アミノ酸文字間)の類似性を表す行列 – PAM250, BLOSUM45 など A A R N D C Q E G H I L K M F P S T W Y V 5 -2 -1 -2 -1 -1 R N D C Q E G H I L K M F T W Y V -2 -1 -2 -1 -1 -1 0 -2 -1 -2 -1 -1 -3 -1 1 0 7 -1 -2 -4 1 0 -3 0 -4 -3 3 -2 -3 -3 -1 -1 -1 7 2 -2 0 0 0 1 -3 -4 0 -2 -4 -2 1 0 -2 2 8 -4 0 2 -1 -1 -4 -4 -1 -4 -5 -1 0 -1 -4 -2 -4 13 -3 -3 -3 -3 -2 -2 -3 -2 -2 -4 -1 -1 1 0 0 -3 7 2 -2 1 -3 -2 2 0 -4 -1 0 -1 -3 -3 -4 -5 -5 -1 -2 -1 -2 -3 -3 -1 0 3 -3 -4 -1 -3 BLOSUM50 スコア行列 (置換行列)の一部分 P S スコア行列の導出 • 基本的には頻度の比の対数をスコアとする • BLOSUM行列 – 既存のスコア行列を用いて多くの配列のアライメントを求め、 ギャップ無しの領域(ブロック)を集める – 残基がL%以上一致しているものを同一クラスタに集める – 同じクラスタ内で残基aが残基bにアラインされる頻度Aabを 計算 – qa=∑b Aab / ∑cd Acd, pab=Aab / ∑cd Acd を求め、 s(a,b)=log(pab/qaqb) としたのち、 スケーリングし近傍の整数値に丸める ペアワイズ・アライメント • ペアワイズ・アライメント: 2個の配列のアライメント • 可能なアライメントの個数: 指数オーダー • しかし、スコア最大となるアライメント(最適アライメント) は動的計画法により、O(mn)時間で計算可能(m,n:入力 配列の長さ) 入力配列 AGCT, ACGCT 最適アラ イメント アライメント AGCT ACGCT スコア -3 AG - CT ACGCT 1 A - GCT ACGCT - AGC - - T AC - - GCT 3 -5 (同じ文字の時: 1、違う文字の時: -1、ギャップ1文字: -1) 動的計画法によるアライメント (1) • 入力文字列から格子状グラフを構成 • アライメントと左上から右下へのパスが一対一対応 • 最長経路=最適アライメント G G F V 5 -5 K -2 -5 Y -5 7 D 1 -6 アライメント -7 GK Y G D F V D -2 -3 -2 -7 GF V D GK Y D D 1 -7 0 -4 4 -7 -7 -7 5 -7 +7 -7 +4 = 2 -7 GK Y D -1 スコア -7 G F V D -7 -7 -1 +0 -7 -7 = -29 -7 -7 -5 -7 -7 -7 -7 = -47 動的計画法によるアライメント (2) • 動的計画法: テーブル(表)を用いて効率的に計算 • アライメントでは以下の F(i,j) を計算 – F(i,j) : (0,0) から (i,j) に至る最適なパスの重み (0,0) G (0,1) F G (1,0)K (2,0)Y (3,0)D 5 -2 -5 1 (4,0) -7 (4,1) (1,1) -5 -5 7 -6 -1 -2 -3 -2 1 0 -4 4 -7 (0,2) V (0,3) D (0,4) -7 (4,4) F(3,2)=5 動的計画法によるアライメント (3) DP (動的計画法)による 最長経路(スコア)の計算 F (0, j ) jd , F (i,0) id F (i 1, j 1) s ( xi , y j ) F (i, j ) max F (i 1, j ) d F (i, j 1) d ⇒ O(mn)時間 F(0,0) =0 G F(1,0) = -d G F(0,1) = -d F(i-1, j-1) F(i, j-1) s(K,F) F -d F(0,2) = -2d 行列からの経路の復元は、 F(m,n)からmaxで=となっている F(i,j)を逆にたどることに行う (トレースバック) K F(2,0) = -2d -d F(i-1, j) F(i, j) 動的計画法によるアライメント (4) 0 G -7 F -14 V -21 D -28 G -7 K-14 Y-21 D -28 5 -2 5 -5 -1 1 -7 -2 -9 -5 -2 -5 -2 -16 0 -7 0 -4 -9 1 -9 7 -3 -4 -7 -16 -6 5 -2 -2 -8 -7 4 -7 -7 -2 -7 3 -7 2 ローカルアライメント (1) (Smith-Watermanアルゴリズム) • 配列の一部のみ共通部分があることが多い ⇒共通部分のみのアラインメント • 配列検索において広く利用されている • 例えば、HEAWGEH と GAWED の場合、 AWGE A W -E というアライメントを計算 (実際にはローカルアライメントとアフィンギャップを組み合わせることが必 要) ローカルアライメント (2) 動的計画法 の式 0 F ( i 1, j 1) s ( x y ) , F ( i , j ) max F ( i 1, j ) d F ( i , j 1) d 配列検索の実用プログラム (1) • O(mn): mは数百だが、nは数GBにもなる ⇒ 高速アルゴリズムの開発 • FASTA: 短い配列(アミノ酸の場合、1,2文字、DNA の場合、4-6文字)の完全一致をもとに対角線を検索 し、さらにそれを両側に伸長し、最後にDPを利用。 • BLAST: 固定長(アミノ酸では3, DNAでは11)の全 ての類似単語のリストを生成し、ある閾値以上の単語 ペアを探し、それをもとに両側に伸長させる。ギャップ は基本的には入らない。伸長の際に統計的有意性を 利用。 – 様々なバリエーションが存在 • PSI-BLAST: 高精度検索用 • MEGA-BLAST: ゲノム比較用(大規模配列比較用) 配列検索の実用プログラム (2) FASTA A BLAST Query ・・・ A A F D M F D A D G G ・・・ C A T G A C 類似ワード G A MFD MFE MFN T MYD MYE MYN G ・・・ A Query T ( ktup=2 ) ・・・ A A F D M F D A D G G ・・・ ・・・ E A F S M F E K D G D ・・・ Database カーネル法によるタンパク質 構造予測:内容 • サポートベクターマシンとカーネル法 • 配列解析のためのカーネル • カーネル法による構造予測 サポートベクターマシン (1) • カーネル法の一つ • 1990年代に、Cortes と Vapnik が発明 • トレーニングデータとして与えられた正例と負例から、 それらを分離する超平面を計算 ⇒ 学習=超平面の計算 • 機械学習、統計学、人工知能、パターン認識、バイオ インフォマティクスなど様々な分野に応用 – – – – – 配列分類 タンパク質フォールド予測、二次構造予測 遺伝子発現データ解析 タンパク質相互作用予測 化合物の性質推定 サポートベクターマシン (2) • 正例と負例を与 えて、それらを最 適(マージンを最 大)に分離する超 平面を学習 • 例=点 • カーネルを適切に 定義することによ り超平面以外で の分離が可能 margin SVMによるテストデータの分類 SVM: サポートベクターマ シン SVMの利用法 1. 学習データより超平面 を学習 2. 新たなデータ(テスト データ)については、超 平面に対する上下で正 負を判定 テストデータ カーネル • • • • サポートベクターマシン:基本的には超平面で分離 Φ(x) (特徴ベクトル):「非線形曲面⇒超平面」に写像 カーネル: K(x,y)=φ(x)・φ(y) x と y の類似度が高い ⇔ K(x,y)が大 φ(x) カーネルの定義 • 関数 K: X×X→ R がカーネル iff. X から内積空間 F への写像φが存在し、 K (x, y) (x) (y) とかける マーセルの定理 (1) • X を有限空間とし、K(x,y) を X 上の対称関 数とすると、 K(x,y) がカーネル iff. 行列 K=(K(xi,xj)) (i, j=1,…,n) が半正定値 • 行列 K が半正定値 iff. K の固有値がすべて非負 iff. (x) (xtKx 0) カーネルの性質(2) • Ki が以下を満たす時、K もカーネル x, y X , lim K n (x, y ) K (x, y ) n カーネルの例(1) • (x・y+c)d はカーネル – 証明(d=2, c=0の場合) (x y ) ( x1 y1 x2 y2 ) 2 2 x1 x1 y1 y1 x2 x2 y2 y2 2 x1 x2 y1 y2 x1 x1 , x2 x2 , 2 x1 x2 y1 y1 , y2 y2 , 2 y1 y2 カーネルの例(2) • K1, K2 がカーネルの時、以下もカーネル (i) K1 (x, y ) K 2 (x, y ) (ii) a K1 (x, y ) (a 0) (iii) K1 (x, y ) K 2 (x, y ) • (i)(ii)より、カーネルの正係数の線形和もカーネル • (i)(ii)(iii)より、カーネルの正係数の多項式もカーネル カーネルの例(3) (i) f(x): X →R ⇒ f(x) f(y) はカーネル – 証明 n n v v K (x , x i 1 j 1 i j i n j n ) vi v j f (xi ) f (x j ) i 1 j 1 n n vi f (x i ) v j f (x j ) 0 i 1 j 1 (ii) exp(K(x,y)) はカーネル – 略証: 指数関数は正の係数を持つ多項式により任意の精度 で近似でき、また、カーネルの多項式もカーネルとなるため、 性質(2)によりカーネルとなる カーネルの例(4) • exp(-||x-y||2/σ2) はカーネル (Gaussian RBF kernel) • 証明 xy exp 2 2 x2 y2 2x y exp 2 exp 2 exp 2 – 最初の二項の積は例(3-i)によりカーネル、 最後の項は例(3-ii)によりカーネル、 それらの積は例(2-iii)によりカーネル カーネルの例(5) • 以下は必ずしもカーネルとはならない (i) (ii) K (x, y ) logK (x, y ) (iii) K (x, y ) tanh(ax y ) (シグモイドカーネル ) サポートベクターマシン: 定式化(1) • 学習データ: Rd 上の点とラベルのペアの集合 S (xi , yi ) | xi R , yi {1,1} – yi=1 ⇒ 正例 d yi=-1 ⇒ 負例 • 最適化問題 (凸二次計画問題) minimizew w w ,b subject to yi (w xi b) 1 – (w,b): Rd 上の超平面 h: w・x+b=0 に対応 – 1/||w||: h から一番近い xi までの距離(=margin) サポートベクターマシン: 定式化(2) 1/ w サポート ベクター γ minimizew w (w xi b) 1 w ,b subject to yi (w xi b) 1 (w xi b) h (w xi b) 1 1 ( w x b) (w xi b) 1 0 サポートベクターマシン:定式化 (3) • カーネルを用いた定式化 maximize i 1 i l α subject to l i 1 y y K ( x , x ) i j i j i j j 1 l i 1 yi i 0, • 識別関数 i 0 (SV:サポートベクターの集合) w x b * l 1 2 * y xi SV (+なら超平面より上側) i * i K ( x i , x) b b* * maxyi 1 w* xi min yi 1 w* xi 2 • 利点: 特徴ベクトルを陽に扱わずに、カーネル値のみ が計算できればOK ⇒ カーネルトリック 実問題に対するカーネル • データから特徴ベクトル(feature vector)を 作るのが一般的、かつ、 多くの場合に実用的 • 特徴ベクトル: 実数値の列 • 例えば、各化合物 x に対し、 – Φ(x) = (分子量, 容積, 表面積, logP,…) とすれば、化合物 x,y に対するカーネルは Φ(x) と Φ(y) の単なる内積 配列解析のためのカーネル • 配列を実数ベクトルに変換 • 様々なカーネルの提案 – Marginalized kernel, Fisher kernel, Local alignment kernel, … ACCGTA φ(x) CACGTA TCCGTCC CCACCG CCACCGA TCCGTTC CTACCA CTACCGG GACCGTA GACCTC AGCGTG AGCGTAA TACCGTA タンパク質配列解析のためのカーネル • 隠れマルコフモデル(HMM)から特徴ベクトルを抽出 – Fisher カーネル (Jaakkola et al., 2000) – Marginalized カーネル (Tsuda et al., 2002) • 配列から直接特徴ベクトルを抽出 – Spectrum カーネル (Leslie et al., 2002) – Mismatch カーネル (Leslie et al., 2003) • 他の配列とのスコアを特徴ベクトルとして利用 – SVM pairwise (Liao & Noble, 2002) • 配列パターンの出現頻度を特徴ベクトルとして利用 – モチーフカーネル(Ben-Hur & Brutlag, 2003) • 二つの配列から直接カーネル値を計算 – Local Alignment Kernel (Saigo et al, 2004) Spectrum カーネル • 長さ k の各文字列の出現回数を特徴ベクトルとする • カーネルはその内積(K(x,y)=φ(x)・φ(y)) • 単純だけど有用、かつ、高速に計算可能 Spectrumカーネル AA AC AG A CCT A C CC CG CT TA TC ( 0 2 0 1 0 1 1 0 ) ( 1 1 0 0 1 0 0 1 ) φ(x) A A CGT C φ(y) Local Alignment カーネル • Local Alignment アルゴリズムをカーネルとして利用したい ⇒ カーネルの条 件を満たさない • そこで、スコア最大のパスのみを考えるのではなく、すべてのパスのスコアを 考慮した Local Alignment カーネルを開発 ⇒ カーネルの条件を満たす • π:(ローカル)アラ イメント • s(x,y,π): x,yの アライメントπの スコア • Π:可能なアライメ ントの集合 定理 SW ( x, y ) max s ( x, y, ) ( x , y ) K LA ( x, y) exp( s( x, y, )) ( x , y ) lim ln(K LA ( x, y)) SW ( x, y) 1 タンパク質立体構造予測 • アミノ酸配列から、 タンパク質の立体 構造(3次元構造) をコンピュータによ り推定 • 実験よりは、精度が 悪い • だいたいの形がわ かれば良いのであ れば、4~5割の予 測率 アミノ酸配列 T C A V F G L G G V R L S D V コンピュータ タンパク質 立体構造 SCOPデータベース • タンパク質立体構造を形状を中心に、人手で、 階層的に、分類したデータベース SCOP Root ‥‥‥‥‥ Class.1 Class.2 ‥‥‥‥‥ Fold.1 Fold.2 Super Super Family.1 Family.2 Family.1 ‥‥‥‥‥ Family.2 mkkrltitlsesvlenlekmaremglsksam ispqarafleevfrrkqslnskekeevakkcg isvalenykkgq itplqvrvwfinkrmrs Family.3 Super Family 予測 • 入力配列が SCOP のどのスーパーファミリー に属するかを予測 Super Family.1 タンパク質配列 madqlteeqiaefkeafslfdkdgdgtittkel gtvmrslgqnpteaelqdminevdadg Super Family.2 ngtidfpefltmmark : : Super Family.3 SVMによるスーパーファミリー予測 • 各ファミリーごとにSVMを学習 – i番目のSVM • i番目のファミリーに属するタンパク質を正例 • それ以外のタンパク質を負例 • 最も高いスコアを出力したSVMに対応するファミリーを予測結果とする タンパク質配列 スコア LVEKHPLADFCVEDRKLVIH...... SVM1 SVM2 SVM3 SVMn 3.5 -2.0 5.8 -3.2 予測結果 3番目のスーパーファミリー まとめ • バイオインフォマティクス – 生物学+情報科学 (+数理科学+統計学+...) – 成果の多くはWEBページなどを通して利用可能 • 配列検索 – 動的計画法による配列アライメント – 配列検索による機能予測 • 配列が類似していれば、機能も類似 • カーネル法によるタンパク質構造予測 – サポートベクターマシン: 超平面を学習 – カーネル関数: 特徴ベクトルの内積 – 文字列に対するカーネル関数 • Spectrumカーネル、Local Alignment カーネル – スーパーファミリー予測への応用 参考文献 • バイオインフォマティクス – 金久實:ポストゲノム情報への招待、共立出版、2001 • 配列解析 – 岸野・浅井:生物配列の統計、岩波書店、2003 – 阿久津・浅井・矢田(訳):バイオインフォマティクス -確率モデルによる遺伝子配列解析-、医学出版、2001 • カーネル法 – 大北(訳):サポートベクターマシン入門、共立出版、2005
© Copyright 2024 ExpyDoc