分子生物情報学
動的計画法に基づく配列比較法
(ペアワイズアライメント法)
阿久津 達也
京都大学 化学研究所
バイオインフォマティクスセンター
配列アライメント




バイオインフォマティクスの
最重要技術の一つ
2個もしくは3個以上の配列
の類似性の判定に利用
文字間の最適な対応関係を
求める(最適化問題)
配列長を同じにするように、
ギャップ記号(挿入、欠失に
対応)を挿入
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
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
R
N
D
C
Q
E
G
H
I
L
K
M
F
P
-3
-3
-4
-5
-5
-1
-2
-1
-2
-3
-3
-1
0
3
-3
-4
-1
-3
BLOSUM50 スコア行列
(置換行列)の一部分
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
3
- AGC - - T
AC - - GCT
-5
(同じ文字の時: 1、違う文字の時: -1、ギャップ1文字: -1)
ギャップペナルティ


線形コスト -gd
 g: ギャップ長
A L G
L Y G
A V G V S D L
G
 d: ギャップペナルティ
 この図の例では、コスト= -3d
アフィンギャップコスト –d – e(g-1)
 d: ギャップ開始ペナルティ
 e: ギャップ伸張ペナルティ
 この図の例では、コスト= -d - 2e
 よく利用されるペナルティ (d,e)=(12,2),(11,1)
ギャップ (g =3)
動的計画法による大域アライメント(1)
(Needleman-Wunschアルゴリズム)



入力文字列から格子状グラフを構成
アライメントと左上から右下へのパスが一対一対応
最長経路=最適アライメント
G
G
F
V
D
5
-5
K
-2
-5
Y
-5
7
D
1
-6
-1
-2
-3
-2
1
0
-4
4
-7
-7
-7
-7
アライメント
スコア
-7
-7
-7
-7
GKY
D
G F V D
5 -7 +7
-7 +4 = 2
GK Y D
GF V D
-7 -7 -1 +0
-7 -7 = -29
GKY D
-7 -7 -5 -7
-7 -7 -7 = -47
G
F V D
動的計画法による大域アライメント(2)
F(0,0)
G
F(1,0)
=-d
K
F(2,0)
=-2d
=0
G
F(0,1)
=-d
F(i-1, j-1)
F(i, j-1)
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

s(K,F)
F
-d
F(0,2)
=-2d
F(i-1, j)
-d
F(i, j)
⇒ O(mn)時間
行列からの経路の復元は、
F(m,n)からmaxで=となっている
F(i,j)を逆にたどることに行う
(トレースバック)
動的計画法による大域アライメント(3)
0
G
-7
F
-14
V
-21
D
-28
G -7 K-14 Y-21 D -28
5
-5
-1
1
5
-2
-5
-2
-2
-9
0
-16
-7
-7
-5
-2
7
0
-3
-4
-9
-6
5
-2
-2
-4
-9
-7
1
4
-8
-7
-7
-16
-7
-2
-7
3
-7
2
局所アライメント(1)
(Smith-Watermanアルゴリズム)




配列の一部のみ共通部分があることが多い
⇒共通部分のみのアライメント
x1x2 … xm, y1y2 … yn を入力とする時、スコアが最大とな
る部分列ペア xixi+1 … xk, yjyj+1 … yh を計算
例えば、HEAWGEH と GAWED の場合、
AWGE
A W -E
というアライメントを計算
大域アライメントを繰り返すとO(m3n3)時間
⇒Smith-WatermanアルゴリズムならO(mn)時間
局所アライメント(2)
動的計画法
の式
0
F ( i  1, j  1)  s ( x y )

,
F ( i , j )  max
F ( i  1, j )  d
F ( i , j  1)  d
(最大のF(i,j)から
トレースバック)
局所アライメント(3)

局所アライメントの正当性の証明(下図)

局所アライメントの定義:x1x2 … xm, y1y2 … yn を入力とする時、
スコアが最大となる部分列ペア xixi+1 … xk, yjyj+1 … yh を計算
0
F ( i  1, j  1)  s ( x y )

,
F ( i , j )  max
F ( i  1, j )  d
F ( i , j  1)  d
maxF ( i , j )}
0
0
0
(一部の辺は
省略)
アフィンギャップコストによる
アライメント
F ( i  1, j )  d
Ix ( i , j )  max
Ix ( i  1, j )  e
F ( i , j  1)  d
Iy ( i , j )  max
Iy ( i , j  1)  e
F ( i  1, j  1)  s ( x , y )

F ( i , j )  max
Ix ( i , j )

Iy ( i , j )



三種類の行列を用いる動的
計画法によりO(mn)時間
Smith-Watermanアルゴリ
ズムとの組み合わせが広く
利用されている
Ix (i, j)
Iy (i, j)
F (i, j)
任意ギャップコストによる
アライメント

動的計画法(右式)によ
り、O(n 3 )時間
(ただし、m=O(n)とす
る)

F ( i  1, j  1)  s ( x , y )

F ( i , j )  max  max F ( k , j )   ( i  k )
 0,..., 1
 max F ( i , k )   ( j  k )
 0,... 1
ギャップコストと計算時間の関係
線形

ギャップコストが
凸の時:
O(n 2α(n))時間
ただし、α(n)は
アッカーマン関数
の逆関数(実用的
には定数と同じ)
O(n 2 )時間
2
凸 O(n α(n))時間
アフィン
任意
O(n 2 )時間
3
O(n )時間
ペアワイズ・アライメントの計算量に
関するその他の結果

線形領域アライメント





スコア計算だけなら簡単
トレースバックが難しい
しかし、分割統治法により
O(n)領域が可能(右図)
O(n2)時間の改善は可能か?
⇒O(n2/logn)が可能
s(xi,yj)が疎(O(n)程度)な場合
(Sparse DP)
⇒O(n logn)程度で可能
計算時間
C×mn
C×(mn/2)
C×(mn/4)
配列検索の実用プログラム(1)
O(mn):mは数百だが、nは数GBにもなる
⇒実用的アルゴリズムの開発
 FASTA:短い配列(アミノ酸の場合、1,2文字、DNAの
場合、4-6文字)の完全一致をもとに対角線を検索し、
さらにそれを両側に伸長し、最後にDPを利用。
 BLAST:固定長(アミノ酸では3, DNAでは11)の全て
の類似単語のリストを生成し、ある閾値以上の単語
ペアを探し、それをもとに両側に伸長させる。ギャッ
プは入らない。伸長の際に統計的有意性を利用。

配列検索の実用プログラム(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
配列検索の実用プログラム(3)


SSEARCH: 局所アラインメント(SmithWatermanアルゴリズム)をそのまま実行
PSI-BLAST: ギャップを扱えるように拡張
したBLASTを繰り返し実行。「BLASTで見
つかった配列からプロファイルを作り、そ
れをもとに検索」という作業を繰り返す。
講義のまとめ(配列アライメント
I)

動的計画法によるペアワイズアライメント





大域アライメント
局所アライメント(Smith-Watermanアルゴリズム)
アフィンギャップコストを用いたアライメント
線形領域アライメント
参考文献

阿久津、浅井、矢田訳:バイオインフォマティクス –確率モ
デルによる遺伝子配列解析、医学出版、2001
ダウンロード

第1回 - 京都大学