明治大学大学院理工学研究科 総合講義C バイオインフォマティクスにおける 数理的手法 阿久津　達也 京都大学　化学研究所　 バイオインフォマティクスセンター

バイオインフォマティクス（１） 生物学＋情報科学 １９９０年代に大きく発展 ← ゲノム計画の急速な進展 　　　（＋数理科学＋統計学＋物理学＋化学＋医学＋農学＋．．．） １９９０年代に大きく発展 　　　←　ゲノム計画の急速な進展 　　　（既に数百種類以上の生物種のゲノムが決定） 情報解析の必要性 DNA配列⇔プログラムのオブジェクトコード 意味の解析が必要 配列以外のデータ解析も重要 立体構造、遺伝子発現データ、代謝パスウェイなど

バイオインフォマティクス（２） 主要トピック 分野としての特徴 データベース構築 遺伝子発見、遺伝子制御領域推定 配列検索、配列比較、進化系統樹 タンパク質構造予測、機能予測、相互作用予測 遺伝子発現データ解析 ネットワーク構造解析 化合物の性質推定 分野としての特徴 多くのデータベース・ソフトウェアがWEBなどから利用可能 研究成果が（生物学研究への）応用に直結

バイオインフォマティクスにおけるデータベース 多くの重要なデータベースがWEBからアクセス可能 DNA配列：　GenBank, EMBL, DDBJ タンパク質配列：　UniProt (Swissprot) タンパク質立体構造： PDB モチーフ： Prosite, Pfam, … 代謝パスウェイ： KEGG

講義内容 分子生物学における基礎事項 配列検索（動的計画法による配列アライメント） カーネル法によるタンパク質構造予測

遺伝子とタンパク質 遺伝情報の流れ （セントラルドグマ） 遺伝子 DNA配列中で直接的に 機能する部分 ゲノム タンパク質 　（セントラルドグマ） DNA⇒RNA⇒タンパク質 遺伝子 DNA配列中で直接的に　機能する部分 ゲノム 遺伝情報の総体 タンパク質 アミノ酸（２０種類）の鎖

DNAとタンパク質 DNA： A,C,G,Tの４文字の並び DNAは二重ラセン構造⇒相補鎖 タンパク質： アミノ酸(20種類）の鎖 タンパク質：　アミノ酸(20種類）の鎖 固有の三次元構造をとるものが多い 構造は機能と深く関連 A T G C (図はrasmolを用いて作成)

DNAとアミノ酸 DNA： A,C,G,Tの４文字の並び タンパク質: アミノ酸の鎖 アミノ酸： ２０種類

アミノ酸とタンパク質 アミノ酸：側鎖の違いにより２０種類 タンパク質：アミノ酸の鎖

側鎖の例

配列検索：内容 配列検索と配列アライメント ペアワイズ・アライメント 配列検索の実用プログラム

配列検索 バイオインフォマティクスにおける基本原理 配列検索の利用法 配列が似ていれば機能も似ている ただし、例外はある 実験を行い機能未知の配列が見つかった データベース中で類似の配列を検索 機能既知の類似の配列が見つかれば、その配列と似た機能を持つと推定

配列アライメント 配列の類似性の検出に利用 バイオインフォマティクスの最重要技術の一つ 文字間の最適な対応関係を求める（最適化問題） 配列長を同じにするように、ギャップ記号（挿入、欠失に対応）を挿入

スコア行列（置換行列） 残基間（アミノ酸文字間）の類似性を表す行列 PAM250, BLOSUM45 など

スコア行列の導出 基本的には頻度の比の対数をスコアとする BLOSUM行列 既存のスコア行列を用いて多くの配列のアライメントを求め、ギャップ無しの領域（ブロック）を集める 残基がL％以上一致しているものを同一クラスタに集める 同じクラスタ内で残基aが残基bにアラインされる頻度Aabを計算 qa=∑b Aab / ∑cd Acd, pab=Aab / ∑cd Acd　を求め、　　　 　ｓ（a,b)=log(pab/qaqb)　 としたのち、 　スケーリングし近傍の整数値に丸める

ペアワイズ・アライメント ペアワイズ・アライメント： ２個の配列のアライメント 可能なアライメントの個数： 指数オーダー ペアワイズ・アライメント：　２個の配列のアライメント 可能なアライメントの個数：　指数オーダー しかし、スコア最大となるアライメント（最適アライメント）は動的計画法により、O(mn)時間で計算可能（m,n:入力配列の長さ）

動的計画法によるアライメント　(1) 入力文字列から格子状グラフを構成 アライメントと左上から右下へのパスが一対一対応 最長経路＝最適アライメント

動的計画法によるアライメント (2) 動的計画法： テーブル（表）を用いて効率的に計算 アライメントでは以下の F(i,j) を計算 動的計画法によるアライメント　(2) 動的計画法：　テーブル（表）を用いて効率的に計算 アライメントでは以下の F(i,j) を計算 F(i,j) : (0,0) から (i,j) に至る最適なパスの重み

動的計画法によるアライメント (3) DP (動的計画法)による 最長経路(スコア)の計算 ⇒ O(mn)時間 行列からの経路の復元は、 動的計画法によるアライメント　(3) DP　(動的計画法)による 最長経路(スコア)の計算 ⇒　O(mn)時間 行列からの経路の復元は、 F(m,n)からmaxで＝となっている F(i,j)を逆にたどることに行う （トレースバック）

動的計画法によるアライメント (4)

ローカルアライメント (1) (Smith-Watermanアルゴリズム) 配列の一部のみ共通部分があることが多い 　　⇒共通部分のみのアラインメント 配列検索において広く利用されている 例えば、HEAWGEH　と　GAWED　の場合、 　　　　　　　　A W G E 　　　　　　　　A W －E 　　というアライメントを計算 　　　（実際にはローカルアライメントとアフィンギャップを組み合わせることが必要）

ローカルアライメント (2) 動的計画法 の式

配列検索の実用プログラム (1) O(mn): mは数百だが、nは数ＧＢにもなる ⇒ 高速アルゴリズムの開発 　⇒　高速アルゴリズムの開発 FASTA:　短い配列（アミノ酸の場合、1,2文字、DNAの場合、4-6文字）の完全一致をもとに対角線を検索し、さらにそれを両側に伸長し、最後にＤＰを利用。 BLAST:　固定長（アミノ酸では3, DNAでは11）の全ての類似単語のリストを生成し、ある閾値以上の単語ペアを探し、それをもとに両側に伸長させる。ギャップは基本的には入らない。伸長の際に統計的有意性を利用。 様々なバリエーションが存在 PSI-BLAST:　高精度検索用 MEGA-BLAST: ゲノム比較用（大規模配列比較用）

配列検索の実用プログラム (2)

カーネル法によるタンパク質 構造予測：内容 サポートベクターマシンとカーネル法 配列解析のためのカーネル カーネル法による構造予測

サポートベクターマシン (1) カーネル法の一つ 1990年代に、Cortes と Vapnik が発明 トレーニングデータとして与えられた正例と負例から、それらを分離する超平面を計算 　　　⇒　学習＝超平面の計算 機械学習、統計学、人工知能、パターン認識、バイオインフォマティクスなど様々な分野に応用 配列分類 タンパク質フォールド予測、二次構造予測 遺伝子発現データ解析 タンパク質相互作用予測 化合物の性質推定

サポートベクターマシン (2) 正例と負例を与えて、それらを最適（マージンを最大）に分離する超平面を学習 例＝点 カーネルを適切に定義することにより超平面以外での分離が可能

SVMによるテストデータの分類 SVM: サポートベクターマシン SVMの利用法 学習データより超平面を学習 新たなデータ（テストデータ）については、超平面に対する上下で正負を判定

カーネル サポートベクターマシン：基本的には超平面で分離 Φ(x) (特徴ベクトル）：「非線形曲面⇒超平面」に写像 カーネル：　K(x,y)=φ(x)・φ(y) x と y の類似度が高い ⇔ K(x,y)が大

カーネルの定義 関数 K: X×X→ R がカーネル　　 iff. 　　X から内積空間 F への写像φが存在し、　　 　　とかける

マーセルの定理 (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 もカーネル

カーネルの例(1) (x・y+c)d はカーネル 証明（d=2, c=0の場合）

カーネルの例(2) K1, K2 がカーネルの時、以下もカーネル (i)(ii)より、カーネルの正係数の線形和もカーネル (i)(ii)(iii)より、カーネルの正係数の多項式もカーネル

(i) f(x): X →R ⇒ f(x) f(y) はカーネル カーネルの例(3) (i) f(x): X →R ⇒ f(x) f(y) はカーネル 証明 (ii) exp(K(x,y)) はカーネル 略証： 指数関数は正の係数を持つ多項式により任意の精度で近似でき、また、カーネルの多項式もカーネルとなるため、性質（２）によりカーネルとなる

exp(-||x-ｙ||2/σ2) はカーネル カーネルの例(4) exp(-||x-ｙ||2/σ2)　はカーネル 　　　　　　　　　（Gaussian RBF kernel） 証明 最初の二項の積は例(3-i)によりカーネル、 　　最後の項は例(3-ii)によりカーネル、 　　それらの積は例(2-iii)によりカーネル

カーネルの例(5) 以下は必ずしもカーネルとはならない

サポートベクターマシン: 定式化(1) 学習データ： Rd 上の点とラベルのペアの集合 最適化問題 （凸二次計画問題） yi=1 ⇒ 正例　　　 yi=-1 ⇒ 負例 最適化問題　（凸二次計画問題） (w,b): Rd 上の超平面 h: w・x+b=0 に対応 1/||w||: h から一番近い xi までの距離（=margin)

サポートベクターマシン: 定式化(2)

識別関数 （SV:サポートベクターの集合） サポートベクターマシン:定式化 (3) カーネルを用いた定式化 識別関数　　　　　　　　（SV:サポートベクターの集合） 利点：　特徴ベクトルを陽に扱わずに、カーネル値のみが計算できればＯＫ　⇒　カーネルトリック (+なら超平面より上側）

実問題に対するカーネル データから特徴ベクトル(feature vector)を作るのが一般的、かつ、 多くの場合に実用的 　多くの場合に実用的 特徴ベクトル：　実数値の列 例えば、各化合物 x に対し、 Φ(x) = (分子量, 容積, 表面積, logP,…) 　とすれば、化合物 x,y に対するカーネルは 　 Φ(x) と Φ(ｙ) の単なる内積

配列解析のためのカーネル 配列を実数ベクトルに変換 様々なカーネルの提案 　配列解析のためのカーネル 配列を実数ベクトルに変換 様々なカーネルの提案 Marginalized kernel, Fisher kernel, Local alignment kernel, …

タンパク質配列解析のためのカーネル 隠れマルコフモデル（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)) 単純だけど有用、かつ、高速に計算可能

Local Alignment カーネル π：(ローカル)アライメント s(x,y,π): x,yの アライメントπの スコア 　　アライメントπの 　　スコア Π：可能なアライメントの集合 定理

タンパク質立体構造予測 アミノ酸配列から、タンパク質の立体構造（３次元構造）をコンピュータにより推定 実験よりは、精度が悪い だいたいの形がわかれば良いのであれば、4～５割の予測率

SCOPデータベース タンパク質立体構造を形状を中心に、人手で、 階層的に、分類したデータベース SCOP Root Class.1 　階層的に、分類したデータベース SCOP Root Class.1 Class.2 ‥‥‥‥‥ Fold.1 Fold.2 ‥‥‥‥‥ Super Family.1 Super Family.2 ‥‥‥‥‥ Family.1 Family.2 Family.3 mkkrltitlsesvlenlekmaremglsksamisvalenykkgq ispqarafleevfrrkqslnskekeevakkcgitplqvrvwfinkrmrs

Super Family 予測 入力配列が SCOP のどのスーパーファミリーに属するかを予測 Super Family.1 タンパク質配列 madqlteeqiaefkeafslfdkdgdgtittkelgtvmrslgqnpteaelqdminevdadg ngtidfpefltmmark タンパク質配列 Super Family.1 Super Family.2 Super Family.3 ：

SVMによるスーパーファミリー予測 各ファミリーごとにSVMを学習 i番目のSVM i番目のファミリーに属するタンパク質を正例 それ以外のタンパク質を負例 最も高いスコアを出力したSVMに対応するファミリーを予測結果とする

まとめ バイオインフォマティクス 配列検索 カーネル法によるタンパク質構造予測 生物学＋情報科学 （＋数理科学＋統計学＋．．．） 生物学＋情報科学　　（＋数理科学＋統計学＋．．．） 成果の多くはWEBページなどを通して利用可能 配列検索 動的計画法による配列アライメント 配列検索による機能予測 配列が類似していれば、機能も類似 カーネル法によるタンパク質構造予測 サポートベクターマシン：　超平面を学習 カーネル関数：　特徴ベクトルの内積 文字列に対するカーネル関数 Spectrumカーネル、Local Alignment カーネル スーパーファミリー予測への応用

参考文献 バイオインフォマティクス 配列解析 カーネル法 金久實：ポストゲノム情報への招待、共立出版、2001 岸野・浅井：生物配列の統計、岩波書店、2003 阿久津・浅井・矢田（訳）：バイオインフォマティクス 　　　-確率モデルによる遺伝子配列解析-、医学出版、2001 カーネル法 大北（訳）：サポートベクターマシン入門、共立出版、2005