-ATGCA-TGC
A- TGC-ATGC-
AATCAACG
配列１
A T G A T G C
C
C A T A A
配列２
G
C
(3) 多くの○を通るような A 左上と右下を結ぶ折れ線
A-TGC-ATGC-* A-TGC-ATGC-* A-TGC-ATGC-* A-TGC-ATGC-* A-TGC-ATGC-* AAT-CAA--CG
この場合、解は何通りもあるが、いずれも一致する残基数は５
動的計画法によるアライメント
• アライメント問題は、有向グラフの最適経路 問題と等価
• 有向グラフの最適経路問題は動的計画法
（ Dynamic Programming) と呼ばれるアルゴリ ズムで解ける。
• O(NM) の計算量 （文字列長の積に比例）
0
-3 -3 -3 -3
-3 -3 -3 -3
-3 -3 -3 -3
-3 -3 -3 -3
-3
-3
-3 -3
-3
-3 -3 -3
-3 -3 -3
-3
-3 -3 -3
2
-2
-3 4 -1 -4 -4
2
2 -2 -2
6
L
Q
I
L D G V
動的計画法によるグローバルアライメントの解法
z
鉛直、水平に比較したい文字列を並べる
z
対角線のエッジには一致スコア、鉛直水平のエッジにはギャップスコアを書き込む
z
右下のノードから左上のノードへ至る最適経路を求める
j
i
始点
終点
動的計画法によるグローバル・アライメントの解法 (Needleman & Wunsh,1970)
(0) 準備
( １ ) 前向きステップ
(2) 後ろ向きステップ
始点の格子点のスコア D(0,0) を 0 に設定
終点を起点にして、マークした矢印を逆向きにたどる。終点に到着したら終了。
⎪ ⎩
⎪ ⎨
⎧
−
−
−
−
+
−
−
=
) ( )
1 ,
(
) ( )
, 1 (
) ( )
, ( )
1 ,
1 (
max )
, (
h Gap
j i D
v Gap
j i
D
d j
i s j
i D j
i D
水平 鉛直 対角
終点 始点
d
h
v D(i-1,j-1)
D(i,j-1) D(i,j)
D(i-1,j) i=1,j=1から、開始し、iとjを一つずつ
大きくしながら、以下の式に従って、
D(i,j)
を決めていく。
そのとき、使用した矢印をマークする。
※
D(i,j)
は始点
(0,0)
から格子点
(i,j)
までのスコアの和の最大値
s(i,j)
は配列１のi
番目と配列２のj
番目の文字がマッチしたときのスコア
-3 0
-3 -3 -3 -3
-3 -3 -3 -3
-3 -3 -3 -3
-3 -3 -3 -3
-3
-3
-3 -3
-3
-3 -3 -3
-3 -3 -3
-3
-3 -3 -3
2
-2
-3 4 -1 -4 -4
2
2 -2 -2
6
L
Q
I
L D G V
z
鉛直、水平に比較したい文字列を並べる
z
対角線のエッジには一致スコア、鉛直水平のエッジにはギャップスコアを書き込む
z
右下のノードから左上のノードへ至る最適経路を求める
j
i
始点
終点
左端と上端の D(i,j) をまず、決めていく
-6 -3 0
-3 -3 -3 -3
-3 -3 -3 -3
-3 -3 -3 -3
-3 -3 -3 -3
-3
-3
-3 -3
-3
-3 -3 -3
-3 -3 -3
-3
-3 -3 -3
2
-2
-3 4 -1 -4 -4
2
2 -2 -2
6
L
Q
I
L D G V
z
鉛直、水平に比較したい文字列を並べる
z
対角線のエッジには一致スコア、鉛直水平のエッジにはギャップスコアを書き込む
z
右下のノードから左上のノードへ至る最適経路を求める
j
i
始点
終点
左端と上端の D(i,j) をまず、決めていく
-9 -12 -6
-3
-6
-9 -3
0
-3 -3 -3 -3
-3 -3 -3 -3
-3 -3 -3 -3
-3 -3 -3 -3
-3
-3
-3 -3
-3
-3 -3 -3
-3 -3 -3
-3
-3 -3 -3
2
-2
-3 4 -1 -4 -4
2
2 -2 -2
6
L
Q
I
L D G V
z
鉛直、水平に比較したい文字列を並べる
z
対角線のエッジには一致スコア、鉛直水平のエッジにはギャップスコアを書き込む
z
右下のノードから左上のノードへ至る最適経路を求める
j
i
始点
終点
左端と上端の D(i,j) をまず、決めていく
-9 -12 -6
-3
-6
-9 -3
0
-3 -3 -3 -3
-3 -3 -3 -3
-3 -3 -3 -3
-3 -3 -3 -3
-3
-3
-3 -3
-3
-3 -3 -3
-3 -3 -3
-3
-3 -3 -3
2
-2
-3 4 -1 -4 -4
2
2 -2 -2
6
L
Q
I
L D G V
z
鉛直、水平に比較したい文字列を並べる
z
対角線のエッジには一致スコア、鉛直水平のエッジにはギャップスコアを書き込む
z
右下のノードから左上のノードへ至る最適経路を求める
j
i
始点
終点
6+0=6 -3-3=-6
-3-3=-6
（１）前向きステップ：たて、よこ、ななめのスコアを比べる
-9 -12 -6
-3
6
-6
-9 -3
0
-3 -3 -3 -3
-3 -3 -3 -3
-3 -3 -3 -3
-3 -3 -3 -3
-3
-3
-3 -3
-3
-3 -3 -3
-3 -3 -3
-3
-3 -3 -3
2
-2
-3 4 -1 -4 -4
2
2 -2 -2
6
L
Q
I
L D G V
z
鉛直、水平に比較したい文字列を並べる
z
対角線のエッジには一致スコア、鉛直水平のエッジにはギャップスコアを書き込む
z
右下のノードから左上のノードへ至る最適経路を求める
j
i
始点
終点
6+0=6 -3-3=-6
-3-3=-6
（１）前向きステップ：たて、よこ、ななめのスコアを比べる
-9 -12 -6
-3
6
-6
-9 -3
0
-3 -3 -3 -3
-3 -3 -3 -3
-3 -3 -3 -3
-3 -3 -3 -3
-3
-3
-3 -3
-3
-3 -3 -3
-3 -3 -3
-3
-3 -3 -3
2
-2
-3 4 -1 -4 -4
2
2 -2 -2
6
L
Q
I
L D G V
z
鉛直、水平に比較したい文字列を並べる
z
対角線のエッジには一致スコア、鉛直水平のエッジにはギャップスコアを書き込む
z
右下のノードから左上のノードへ至る最適経路を求める
j
i
始点
終点
-3-2=-5 6-3=3 -6-3=-9
（１）前向きステップ：たて、よこ、ななめのスコアを比べる
-9 -12 -6
-3
6
-6 3
-9 -3
0
-3 -3 -3 -3
-3 -3 -3 -3
-3 -3 -3 -3
-3 -3 -3 -3
-3
-3
-3 -3
-3
-3 -3 -3
-3 -3 -3
-3
-3 -3 -3
2
-2
-3 4 -1 -4 -4
2
2 -2 -2
6
L
Q
I
L D G V
z
鉛直、水平に比較したい文字列を並べる
z
対角線のエッジには一致スコア、鉛直水平のエッジにはギャップスコアを書き込む
z
右下のノードから左上のノードへ至る最適経路を求める
j
i
始点
終点
-3-2=-5 6-3=3 -6-3=-9
（１）前向きステップ：たて、よこ、ななめのスコアを比べる
-9 -12 -6
-3
6
-6 3
-9 -3
0
-3 -3 -3 -3
-3 -3 -3 -3
-3 -3 -3 -3
-3 -3 -3 -3
-3
-3
-3 -3
-3
-3 -3 -3
-3 -3 -3
-3
-3 -3 -3
2
-2
-3 4 -1 -4 -4
2
2 -2 -2
6
L
Q
I
L D G V
z
鉛直、水平に比較したい文字列を並べる
z
対角線のエッジには一致スコア、鉛直水平のエッジにはギャップスコアを書き込む
z
右下のノードから左上のノードへ至る最適経路を求める
j
i
始点
終点
1 2 3 4
（１）前向きステップ：たて、よこ、ななめのスコアを比べる
9 2 -3 -9 -12
0
5
5 5 8
3 -6 -3
6
-6 3
0 -9
-3 0
-3 -3 -3 -3
-3 -3 -3 -3
-3 -3 -3 -3
-3 -3 -3 -3
-3
-3
-3 -3
-3
-3 -3 -3
-3 -3 -3
-3
-3 -3 -3
2
-2
-3 4 -1 -4 -4
2
2 -2 -2
6
L
Q
I
L D G V
z
鉛直、水平に比較したい文字列を並べる
z
対角線のエッジには一致スコア、鉛直水平のエッジにはギャップスコアを書き込む
z
右下のノードから左上のノードへ至る最適経路を求める
j
i
始点
終点
（１）前向きステップ：たて、よこ、ななめのスコアを比べる
9 2 -3 -9 -12
0
5
5 5 8
3 -6 -3
6
-6 3
0 -9
-3 0
-3 -3 -3 -3
-3 -3 -3 -3
-3 -3 -3 -3
-3 -3 -3 -3
-3
-3
-3 -3
-3
-3 -3 -3
-3 -3 -3
-3
-3 -3 -3
2
-2
-3 4 -1 -4 -4
2
2 -2 -2
6
L
Q
I
L D G V
z
鉛直、水平に比較したい文字列を並べる
z
対角線のエッジには一致スコア、鉛直水平のエッジにはギャップスコアを書き込む
z
右下のノードから左上のノードへ至る最適経路を求める
j
i
始点
終点
（２）後ろ向きステップ：マークした矢印を終点から
9 2 -3 -9 -12
0
5
5 5 8
3 -6 -3
6
-6 3
0 -9
-3 0
-3 -3 -3 -3
-3 -3 -3 -3
-3 -3 -3 -3
-3 -3 -3 -3
-3
-3
-3 -3
-3
-3 -3 -3
-3 -3 -3
-3
-3 -3 -3
2
-2
-3 4 -1 -4 -4
2
2 -2 -2
6
L
Q
I
L D G V
z
鉛直、水平に比較したい文字列を並べる
z
対角線のエッジには一致スコア、鉛直水平のエッジにはギャップスコアを書き込む
z
右下のノードから左上のノードへ至る最適経路を求める
j
i
始点
終点
（２）後ろ向きステップ：マークした矢印を終点から
9 2 -3 -9 -12
0
5
5 5 8
3 -6 -3
6
-6 3
0 -9
-3 0
-3 -3 -3 -3
-3 -3 -3 -3
-3 -3 -3 -3
-3 -3 -3 -3
-3
-3
-3 -3
-3
-3 -3 -3
-3 -3 -3
-3
-3 -3 -3
2
-2
-3 4 -1 -4 -4
2
2 -2 -2
6
L
Q
I
L D G V
z
鉛直、水平に比較したい文字列を並べる
z
対角線のエッジには一致スコア、鉛直水平のエッジにはギャップスコアを書き込む
z
右下のノードから左上のノードへ至る最適経路を求める
j
i
始点
終点
（２）後ろ向きステップ：マークした矢印を終点から
9 2 -3 -9 -12
0
5
5 5 8
3 -6 -3
6
-6 3
0 -9
-3 0
-3 -3 -3 -3
-3 -3 -3 -3
-3 -3 -3 -3
-3 -3 -3 -3
-3
-3
-3 -3
-3
-3 -3 -3
-3 -3 -3
-3
-3 -3 -3
2
-2
-3 4 -1 -4 -4
2
2 -2 -2
6
L
Q
I
L D G V
z
鉛直、水平に比較したい文字列を並べる
z
対角線のエッジには一致スコア、鉛直水平のエッジにはギャップスコアを書き込む
z
右下のノードから左上のノードへ至る最適経路を求める
j
i
始点
終点
（２）後ろ向きステップ：マークした矢印を終点から
LDGV
