www.bic.kyoto

明治大学大学院理工学研究科
総合講義C
バイオインフォマティクスにおける
数理的手法
阿久津達也
京都大学化学研究所
バイオインフォマティクスセンター
バイオインフォマティクス（１）
• 生物学＋情報科学
（＋数理科学＋統計学＋物理学＋化学＋医学＋農学＋．．．）
• １９９０年代に大きく発展
← ゲノム計画の急速な進展
（既に数百種類以上の生物種のゲノムが決定）
• 情報解析の必要性
– DNA配列⇔プログラムのオブジェクトコード
– 意味の解析が必要
– 配列以外のデータ解析も重要
• 立体構造、遺伝子発現データ、代謝パスウェイなど
バイオインフォマティクス（２）
• 主要トピック
–
–
–
–
–
–
–
データベース構築
遺伝子発見、遺伝子制御領域推定
配列検索、配列比較、進化系統樹
タンパク質構造予測、機能予測、相互作用予測
遺伝子発現データ解析
ネットワーク構造解析
化合物の性質推定
• 分野としての特徴
– 多くのデータベース・ソフトウェアがWEBなどから利用可能
– 研究成果が（生物学研究への）応用に直結
バイオインフォマティクスにおけるデータベース
• 多くの重要なデータベースがWEBからアクセ
ス可能
– DNA配列： GenBank, EMBL, DDBJ
– タンパク質配列： UniProt (Swissprot)
– タンパク質立体構造： PDB
– モチーフ： Prosite, Pfam, …
– 代謝パスウェイ： KEGG
講義内容
• 分子生物学における基礎事項
• 配列検索（動的計画法による配列アライメン
ト）
• カーネル法によるタンパク質構造予測
遺伝子とタンパク質
• 遺伝情報の流れ
（セントラルドグマ）
– DNA⇒RNA⇒タンパク質
• 遺伝子
– DNA配列中で直接的
に機能する部分
• ゲノム
DNA
エキソン
エキソン
転写制御領域
（プロモーターなど）
転写・
スプライシング
mRNA
GGU
– アミノ酸（２０種類）の鎖
GCA
翻訳
GGU → Gly
GCA → Ala
– 遺伝情報の総体
• タンパク質
エキソン
タンパク質
• DNA： A,C,G,Tの４文
字の並び
• DNAは二重ラセン構造
⇒相補鎖
A
C
T
DNAとタンパク質
• タンパク質：アミノ酸(20
種類）の鎖
• 固有の三次元構造をとる
ものが多い
• 構造は機能と深く関連
T
G
A
G
C
A
T
C
G
(図はrasmolを用いて作成)
DNAとアミノ酸
• DNA： A,C,G,Tの４
文字の並び
• タンパク質: アミノ
酸の鎖
• アミノ酸：２０種類
• DNA３文字がアミノ
酸１文字に対応
コード表
2文字目
T
T
１
文
字
目
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
アミノ酸とタンパク質
• アミノ酸：側鎖の違
いにより２０種類
• タンパク質：アミノ酸
の鎖
アミノ酸
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 ２
O
C
-
His ヒス
チジン
Cys シス
テイン
HN
SH
+
NH
CH ２
CH 2
CH ２
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 を求め、
ｓ（a,b)=log(pab/qaqb) としたのち、
スケーリングし近傍の整数値に丸める
ペアワイズ・アライメント
• ペアワイズ・アライメント：２個の配列のアライメント
• 可能なアライメントの個数：指数オーダー
• しかし、スコア最大となるアライメント（最適アライメント）
は動的計画法により、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は数ＧＢにもなる
⇒ 高速アルゴリズムの開発
• FASTA: 短い配列（アミノ酸の場合、1,2文字、DNA
の場合、4-6文字）の完全一致をもとに対角線を検索
し、さらにそれを両側に伸長し、最後にＤＰを利用。
• 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)) はカーネル
– 略証：指数関数は正の係数を持つ多項式により任意の精度
で近似でき、また、カーネルの多項式もカーネルとなるため、
性質（２）によりカーネルとなる
カーネルの例(4)
• exp(-||x-ｙ||2/σ2) はカーネル
（Gaussian RBF kernel）
• 証明
 xy
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 )

logK (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
• 利点：特徴ベクトルを陽に扱わずに、カーネル値のみ
が計算できればＯＫ ⇒ カーネルトリック
実問題に対するカーネル
• データから特徴ベクトル(feature vector)を
作るのが一般的、かつ、
多くの場合に実用的
• 特徴ベクトル：実数値の列
• 例えば、各化合物 x に対し、
– Φ(x) = (分子量, 容積, 表面積, logP,…)
とすれば、化合物 x,y に対するカーネルは
Φ(x) と Φ(ｙ) の単なる内積
配列解析のためのカーネル
• 配列を実数ベクトルに変換
• 様々なカーネルの提案
– 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
 
タンパク質立体構造予測
• アミノ酸配列から、
タンパク質の立体
構造（３次元構造）
をコンピュータによ
り推定
• 実験よりは、精度が
悪い
• だいたいの形がわ
かれば良いのであ
れば、4～５割の予
測率
アミノ酸配列
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
予測結果
３番目のスーパーファミリー
まとめ
• バイオインフォマティクス
– 生物学＋情報科学（＋数理科学＋統計学＋．．．）
– 成果の多くはWEBページなどを通して利用可能
• 配列検索
– 動的計画法による配列アライメント
– 配列検索による機能予測
• 配列が類似していれば、機能も類似
• カーネル法によるタンパク質構造予測
– サポートベクターマシン：超平面を学習
– カーネル関数：特徴ベクトルの内積
– 文字列に対するカーネル関数
• Spectrumカーネル、Local Alignment カーネル
– スーパーファミリー予測への応用
参考文献
• バイオインフォマティクス
– 金久實：ポストゲノム情報への招待、共立出版、2001
• 配列解析
– 岸野・浅井：生物配列の統計、岩波書店、2003
– 阿久津・浅井・矢田（訳）：バイオインフォマティクス
-確率モデルによる遺伝子配列解析-、医学出版、2001
• カーネル法
– 大北（訳）：サポートベクターマシン入門、共立出版、2005

Download Report