Traceback
2018/4/24 1以下の図に示すように、最大重みパスをD[i,j]を用いて
頂点(m,n)から逆にたどりながら、アラインメントを後ろ
から前へと計算していけばよい。
D(i-1,j-1)=9 D(i,j-1)=10 D(i-1,j)=8 D(i,j)=10 d=-1 d=-1 D(i-1,j-1)=8 D(i,j-1)=10 D(i-1,j)=11 D(i,j)=10 d=-1 d=-1 1 1 トレースバック トレースバック 11-1=10 9+1=10Traceback
2018/4/24 2 ); , ( return ; ]) 1 ... 1 [ ( ; ]) 1 ... 1 [ ( ; 1 ; 1 ; 1 ]; [ ] [ ]; [ ] [ do ; 1 ; ' ' ] [ ]; [ ] [ do ] , [ ] , [ or 0 if else ; 1 ]; [ ] [ ; ' ' ] [ do ] 1 , [ ] , [ or 0 if do 0 j or 0 while ; ; ; 0 ) ( Traceback Procedure 2 1 1 2 2 1 1 1 2 2 1 1 2 1 1 2 2 1 t t k s t k s t k k j j i i j s k s i s k s else i i k s i s k s d j j i D j i D j j j j s k s k s d j i D j i D i i n j m i k ここで、 は を反転させた配列を表す。例えば、
s=ACGTの場合、 とする。
1 s
s
TGCA
s
1
Traceback
2018/4/24 3 ); , ( return ; ]) 1 ... 1 [ ( ; ]) 1 ... 1 [ ( ; 1 ; 1 ; 1 ; ]' [ ' ] [ ]; [ ] [ do ; 1 ; ' ' ] [ ]; [ ] [ do ] , [ ] , [ or 0 if else ; 1 ]; [ ] [ ; ' ' ] [ do ] , [ ] , [ or 0 if do 0 j or 0 while ; ; ; 0 ) ( Traceback Procedure 2 1 1 2 2 1 1 1 2 2 1 1 2 1 1 2 2 1 t t k s t k s t k k j j i i j s k s i s k s else i i k s i s k s d j j i D j i D j j j j s k s k s d j i D j i D i i n j m i k 計算時間：
ループを１回実行するごとに、i
か
ｊ
の少なくともどちらか一方は１だけ減少することが
わかる。
Traceback
2018/4/24 4 ); , ( return ; ]) 1 ... 1 [ ( ; ]) 1 ... 1 [ ( ; 1 ; 1 ; 1 ; ]' [ ' ] [ ]; [ ] [ do ; 1 ; ' ' ] [ ]; [ ] [ do ] , [ ] , [ or 0 if else ; 1 ]; [ ] [ ; ' ' ] [ do ] , [ ] , [ or 0 if do 0 j or 0 while ; ; ; 0 ) ( Traceback Procedure 2 1 1 2 2 1 1 1 2 2 1 1 2 1 1 2 2 1 t t k s t k s t k k j j i i j s k s i s k s else i i k s i s k s d j j i D j i D j j j j s k s k s d j i D j i D i i n j m i k よって、ループをたかだかn+m 回実行することによって、
i=j=0となることがわかる。ループ1回あたりの計算時間は
明らかに定数時間であり、ループ全体でかかる時間は
Ｏ（ｍ＋ｎ）となる。
Traceback
2018/4/24 5 ); , ( return ; ]) 1 ... 1 [ ( ; ]) 1 ... 1 [ ( ; 1 ; 1 ; 1 ; ]' [ ' ] [ ]; [ ] [ do ; 1 ; ' ' ] [ ]; [ ] [ do ] , [ ] , [ or 0 if else ; 1 ]; [ ] [ ; ' ' ] [ do ] , [ ] , [ or 0 if do 0 j or 0 while ; ; ; 0 ) ( Traceback Procedure 2 1 1 2 2 1 1 1 2 2 1 1 2 1 1 2 2 1 t t k s t k s t k k j j i i j s k s i s k s else i i k s i s k s d j j i D j i D j j j j s k s k s d j i D j i D i i n j m i k 配列の反転は明らかに線形時間で実行できるので、全体の計算時間は O(m+n)となる。このように、動的計画法を用いて計算したデーブルの値から、 それを逆方向にたどって最適解を復元する手続きは一般に、トレースバック （traceback)とよばれる。
動的計画法の計算時間
定理１
線形ギャップスコアの下での2個の配列に対する最適
大域アラインメントは O(mn) 時間及び Ｏ（mn) 領域
で計算できる。
問題を定義する： 二本配列 SEQX and SEQY,
* 単純スコアリングシステム (MATCH, MISMATCH, and gap INDEL
#define SEQX "TTCATA" #define SEQY "TGCTCGTA"
#define MATCH 1 #define MISMATCH -1 #define GAP -2 #include <stdlib.h> #include <stdio.h> #include <string.h>
変数を定義する。
int main(void) {char *x,*y; /* 二本配列, x_1..M and y_1..N */
int M,N; /* 配列の長さ x,y */ int i,j; /* 座標 in x and y */ int **S; /* 動的計画法の行列 */
char *ax,*ay; /* 結果: アラインメントした二本配列 */
int K; /* pairwise alignment の長さ */
int k; /* pairwise alignmentの変数, 0..K-1 */
int sc; /* tmp best pathを探すの変数 */
M = strlen(SEQX); N = strlen(SEQY);
x = malloc(sizeof(char) * (M+2)); /* +2: leading blank, and trailing ¥0 */ y = malloc(sizeof(char) * (N+2));
strcpy(x+1, SEQX); /* x_1..x_M now defined; x_0 undefined */
strcpy(y+1, SEQY); /* y_1..y_N now defined; y_0 undefined */
/*, /* 動的計画法の行列 0..M rows by 0..N columns.*/ S = malloc(sizeof(int *) * (M+1)); for (i = 0; i <= M; i++) S[i] = malloc(sizeof(int) * (N+1));
再帰法：初期化
S[0][0] = 0;
for (i = 1; i <= M; i++) S[i][0] = i * GAP;
for (j = 1; j <= N; j++) S[0][j] = j * GAP;
再帰法
: DP Algorithm
for (i = 1; i <= M; i++) for (j = 1; j <= N; j++) { /* case #1: i,j are aligned */if (x[i] == y[j]) S[i][j] = S[i-1][j-1] + MATCH; else S[i][j] = S[i-1][j-1] + MISMATCH;
sc = S[i-1][j] + GAP; /* case #2: i aligned to - */ if (sc > S[i][j]) S[i][j] = sc;
sc = S[i][j-1] + GAP; /* case #3: j aligned to - */ if (sc > S[i][j]) S[i][j] = sc;
}
/* The result (optimal alignment score) is in S[M][N]. */
Traceback ( see also above)
/* Allocate for our aligned strings (which will be 0..K-1)*/ ax = malloc(sizeof(char) * (M+N+1));
ay = malloc(sizeof(char) * (M+N+1)); /* Start at M,N; work backwards */ i = M;
j = N; k = 0;
while (i > 0 && j > 0) {
/* Case 1: best was x_i aligned to x_j? */
if (i > 0 && j > 0) { /* watch out for boundaries */ sc = S[i-1][j-1];
if (x[i] == y[j]) sc += MATCH; else sc += MISMATCH; if (sc == S[i][j]) { /* residue i aligns to j: */ ax[k] = x[i]; ay[k] = y[j]; k++; /* record the alignment */ i--; j--; /* move to next cell in trace */ continue;
} }
/* Case 2: best was x_i aligned to -? */
if (i > 0) { /* watch out for boundaries */ if (S[i-1][j] + GAP == S[i][j]) { ax[k] = x[i]; ay[k] = '-'; k++; /* record the alignment */
i--; /* move to
next cell in trace */ continue; } }
/* Case 3: best was - aligned to y_j? */
if (j > 0) { /* watch out for boundaries */ if (S[i][j-1] + GAP == S[i][j]) { ax[k] = '-'; ay[k] = y[j]; k++; /* record the alignment */
j--; /* move to
next cell in trace */ continue; } } }
/* Done with the traceback.
* Now ax[0..k-1] and ay[0..k-1] are aligned strings, but backwards; * and k is our alignment length.
* Reverse the strings and we're done. */
K = k; /* K = remember the alignment length */
for (k = 0; k < K/2; k++)
{ /* a sly, efficient in-place reversal by swapping pairs of chars: */ tmp = ax[K-k-1]; ax[K-k-1] = ax[k]; ax[k] = tmp;
tmp = ay[K-k-1]; ay[K-k-1] = ay[k]; ay[k] = tmp; }
printf("Sequence X: %s¥n", x+1); printf("Sequence Y: %s¥n", y+1);
printf("Scoring system: %d for match; %d for mismatch; %d for gap¥n", MATCH, MISMATCH, GAP);
printf("¥n");
Output
printf("Dynamic programming matrix:¥n");for (j = -1; j <= N; j++) printf(" %c ", j > 0 ? y[j] : ' '); printf("¥n"); for (i = 0; i <= M; i++) { printf(" %c ", i > 0 ? x[i] : ' '); for (j = 0; j <= N; j++) printf("%4d ", S[i][j]); printf("¥n"); } printf("¥n"); printf("Alignment:¥n"); printf("X: %s¥n", ax); printf("Y: %s¥n", ay);
printf("Optimum alignment score: %d¥n¥n", S[M][N]);
exit(0); }
G G A T T C A G T T A
G
G
A
T
C
G
A
宿題(3)：G G A
T
T
C A
G T
T
A
0
-2 -4 -6
-8 -10 -12 -14 -16 -18 -20 -22G
-2
+1 -1
G
-4
-1
A
-6
-3
T
-8
C
-10
G
-12
A
-14
-3 -5 -7 -9 -11 -13 -15 -17 -19 +2 0 -2 -4 -6 -8 -10 -12 -14 -16 0 +3 +1 -1 -3 -5 -7 -9 -11 -13 -5 -2 +1 +4 +2 0 -2 -4 -6 -8 -10 -7 -4 -1 +2 +3 +3 +1 -1 -3 -5 -7 -9 -6 -3 0 +1 +2 +2 +2 0 -2 -4 -11 -8 -5 -2 -1 0 +3 +3 +1 -1 -1G G A
T
T
C A
G T
T
A
0
-2 -4 -6
-8 -10 -12 -14 -16 -18 -20 -22G
-2
+1 -1
G
-4
-1
A
-6
-3
T
-8
C
-10
G
-12
A
-14
-3 -5 -7 -9 -11 -13 -15 -17 -19 +2 0 -2 -4 -6 -8 -10 -12 -14 -16 0 +3 +1 -1 -3 -5 -7 -9 -11 -13 -5 -2 +1 +4 +2 0 -2 -4 -6 -8 -10 -7 -4 -1 +2 +3 +3 +1 -1 -3 -5 -7 -9 -6 -3 0 +1 +2 +2 +2 0 -2 -4 -11 -8 -5 -2 -1 0 +3 +3 +1 -1 -1 GGATTCAGTTA GGA- TC- G - - A +1+1+1-2+1+1-2+1-2-2+1= +7-8=-1 GGATTCAGTTA GGAT-C- G - - A +1+1+1+1-2+1-2+1-2-2+1= +7-8 = -1Example:
0
-2
-4
-6
-8
-10 -12 -14 -16 -18
-2
1
-1
-3
-5
-7
-9
-11 -13 -15
-4
-6
-8
-10
-12
-14
-16
A T A T G C C T A
A A G C C T G A0
-2
-4
-6
-8
-10 -12 -14 -16 -18
-2
1
-1
-3
-5
-7
-9
-11 -13 -15
-4
-1
0
0
-2
-4
-6
-8
-10 -12
-6
-3
-2
-1
-1
-1
-3
-5
-7
-9
-8
-5
-4
-3
-2
-2
0
-2
-4
-6
-10
-7
-6
-5
-4
-3
-1
1
-1
-3
-12
-9
-6
-7
-4
-5
-3
-1
2
0
-14
-11 -8
-7
-6
-3
-5
-3
0
1
-16
-13 -10 -9
-6
-5
-4
-5
-2
1
A T A T G C C T A
A A G C C T G Aトレースバック
配列アラインメント
Sequence alignment
-Smith-Waterman (SW) algorithm-
Local sequence alignment
ローカルアライメント
配列アライメントから分かること
二つのＤＮＡの有機体は相似点と相違点を特定するの
に重要である。
以下のことを理解しやすくする：
どのように、二つの有機体が進化するのか？
（例：人間とチンパンジーの相違点）
なぜ？どのように？インフルエンザのウィルスが変化す
るのか？
なぜ病気になりやすい人がいるのか？
（例：ＤＮＡ塩基の変化）
遺伝子をターゲットにした特定の薬を特定する。
DNA 大域アラインメント
DNA ローカルアライメント
グローバルアライメントとローカルアライメント
前回学んだアルゴリズム
グローバルアライメント
では、あまり似ていない配列の比較は？
ローカルアライメント
（よく似ているところだけそろえてみる）
ローカル対グローバル（大域）
大域アラインメントは二本の配列に対して最適アラインメントを見つける。 ローカルアラインメントは部分配列中に類似領域（ドメイン）を見つけるADLG
AVFAL
CDRY
F
Q
||||
||||
|
ADLG
RTQN-
CDRY
Y
Q
ADLG
CDRY
F
Q
||||
||||
|
ADLG
CDRY
Y
Q
類似領域だけ を見つける例：
Global Alignment
Local Alignment—better alignment to find evolutionary-conserved segments
ローカルアラインメント：進化的保存部分列を発見
するためのよりよいアラインメントである。
--T—-CC-C-AGT—-TATGT-CAGGGGACACG—A-GCATGCAGA-GAC | || | || | | | ||| || | | | | |||| | AATTGCCGCC-GTCGT-T-TTCAG----CA-GTTATG—T-CAGAT--C tccCAGTTATGTCAGgggacacgagcatgcagagac |||||||||||| aattgccgccgtcgttttcagCAGTTATGTCAGatcローカルアライメン
トのアルゴリズム
Smith-Waterman アルゴリズム
初期化 D(0,0)=0, D(0,j)= 0, D(i,0)=0 d はギャップのペナルティ(ス コア） 再帰式で
最大スコアを行列中から探
し、そこから０があるところ
までトレースバック
( , ) 1 1 ) , ( ) 1 , ( ) , 1 ( ) t[j] [i], ( ) 1 , 1 ( 0 max ) , ( y x w y x x x w d j i D d j i D s w j i D j i D のとき d= - 2 New! New! New!Example:
グローバルアライメント
0 -2 -4 -2 -4 ?? A T A A A A A T A T A A -2 -4 -2 -4 -2 -4 -2 -4 0 0 1 1 ?? MAX 0 + 1 = 1 -2 - 2 = - 4 -2 - 2 = - 4 -2 – 1 = -3 -4 - 2 = -6 +1 – 2 = -1 MAXマッチノの重み +1
ミスマッチの重み -1
ギャップの重み -2
対角
対角
-1Example:
ローカルアライメント
0 0 0 0 0 ?? A T A A A A A T A T A A 0 0 0 0 0 0 0 0 0 0 1 1 ?? MAX 0 + 1 = 1 0 - 2 = - 2 0 - 2 = - 2 0 0 – 1 = -1 0 - 2 = -2 1 – 2 = -1 0 MAXマッチの重み +1
ミスマッチの重み -1
ギャップの重み -2
対角
対角
0例：
ローカルアライメント
T
C
G
A
C
T
A
C
例：
ローカルアライメント
T
C
G
A
C
0
0
0
0
0
0
T
0
A
0
C
0
例：
ローカルアライメント
T
C
G
A
C
0
0
0
0
0
0
T
0
+1
0
0
0
0
A
0
0
0
+1
0
C
0
0
+1
0
0
+2
0例：
ローカルアライメント
T
C
G
A
C
0
0
0
0
0
0
T
0
+1
0
0
0
0
A
0
0
0
0
+1
0
C
0
0
+1
0
0
+2
AC AC Local alignment例：
ローカルアライメント
A
T
A
T
G
C
C
T
A
A
A
G
C
C
T
G
A
例：
ローカルアライメント
A
T
A
T
G
C
C
T
T
0
0
0
0
0
0
0
0
0
0
A
0
+1 0
+1 0
0
0
0
0
0
A
0
+1 0
+1 0
0
0
0
0
0
G
0
0
0
0
0
+1 0
0
0
0
C
0
0
0
0
0
0
+2 +1 0
0
C
0
0
0
0
0
0
+1 +3 +1 0
T
0
0
+1 0
+1 0
0
+1 +4 +2
G
0
0
0
0
0
+2 0
0
+2 +3
T
0
0
+1 0
+1 0
+1 0
+1 +3
初期化例：
ローカルアライメント
A
T
A
T
G
C
C
T
T
0
0
0
0
0
0
0
0
0
0
A
0
+1 0
+1 0
0
0
0
0
0
A
0
+1 0
+1 0
0
0
0
0
0
G
0
0
0
0
0
+1 0
0
0
0
C
0
0
0
0
0
0
+2 +1 0
0
C
0
0
0
0
0
0
+1 +3 +1 0
T
0
0
+1 0
+1 0
0
+1 +4 +2
G
0
0
0
0
0
+2 0
0
+2 +3
T
0
0
+1 0
+1 0
+1 0
+1 +3
初期化行列中の最大スコア
例：
ローカルアライメント
A
T
A
T
G
C
C
T
T
0
0
0
0
0
0
0
0
0
0
A
0
+1 0
+1 0
0
0
0
0
0
A
0
+1 0
+1 0
0
0
0
0
0
G
0
0
0
0
0
+1 0
0
0
0
C
0
0
0
0
0
0
+2 +1 0
0
C
0
0
0
0
0
0
+1 +3 +1 0
T
0
0
+1 0
+1 0
0
+1 +4 +2
G
0
0
0
0
0
+2 0
0
+2 +3
T
0
0
+1 0
+1 0
+1 0
+1 +3
初期化 GCCT GCCT Local alignment ０ があるところに到達するまでトレースバック大域アラインメント
ローカルアライメント
DNA
大域アラインメント
ローカルアライメント
たんぱく質
{ Ｇ Ａ Ｔ Ｃ } { 20 文字： アミノ酸 } { 4 文字：DNA 塩基 }今まで
今後たんぱく質の
アライメント
今まで、二本のＤＮＡ配列を比較して来ました。
今から、たんぱく質配列の場合を研究しましょう。
そんなに違わない。
たんぱく質を比較するとき、単純スコアリングシステム
（例えば：マッチの時は＋１、ミスマッチの時ー１）は十分
ではない。
タンパク質の大域アラインメント：動的
計画法
d
j
i
D
d
j
i
D
s
M
j
i
D
j
i
D
)
1
,
(
)
,
1
(
)
t[j]
[i],
(
)
1
,
1
(
max
)
,
(
M: アミノ酸の類似性行列 (例えば：BLOSUM62, or PAM250 ) New!DNA 大域アラインメント
DNA ローカルアライメント
M Matrix
A C G T A 1 -1 -1 -1 C -1 1 -1 -1 G -1 -1 1 -1 T -1 -1 -1 1 A C G T A 1-1 -1 -1 C -1 1-1 -1 G -1 -1 1-1 T -1 -1 -1 1 DNA similarity matrix.
A
たんぱく質 大域アラインメント
たんぱく質 アライメント
Example: PAM 250
類似なアミノ酸がより大きいスコアになる。
Example : Blosum62
derived from block where the sequences share at least 62% identity
配列はすくなくとも６２％の類似度がある
タンパク質のローカルアラインメント：
Smith-Waterman (local alignment)
d
j
i
D
d
j
i
D
s
M
j
i
D
j
i
D
)
1
,
(
)
,
1
(
)
t[j]
[i],
(
)
1
,
1
(
0
max
)
,
(
M: アミノ酸の類似性行列(BLOSUM62, or PAM250 for example) New!
PAM250, Gap
=6
S P E A R E S 2 1 0 1 0 0 H -1 0 1 -1 2 1 A 1 1 0 2 -2 0 K 0 -1 0 -1 3 0 E 0 -1 4 0 -1 4These values are copied from the PAM250 matrix (see earlier slide)
SPEARE
S-HAKE
S
P
E
A
R
E
0
-6
-12 -18 -24 -30 -36
S
-6
H
-12
A
-18
K
-24
E
-30
タンパク質の大域アラインメント：動的計画法
タンパク質の大域アラインメント：動的計画法
PAM250, Gap
=6
S P E A R E S 2 1 0 1 0 0 H -1 0 1 -1 2 1 A 1 1 0 2 -2 0 K 0 -1 0 -1 3 0 E 0 -1 4 0 -1 4These values are copied from the PAM250 matrix (see earlier slide)
SPEARE
S-HAKE
S
P
E
A
R
E
0
-6
-12 -18 -24 -30 -36
S
-6
+2 -4
-10 -16 -22 -28
H
-12
-4
+2 -3
-9
-14
A
-18
-10 -3
+2
-7
-13
K
-24
-16 -9
-3
+1 +2 -4
E
-30
-22
-3
0
+6
-20 -1 -15 -5PAM250, Gap
=6
S P E A R E S 2 1 0 1 0 0 H -1 0 1 -1 2 1 A 1 1 0 2 -2 0 K 0 -1 0 -1 3 0 E 0 -1 4 0 -1 4These values are copied from the PAM250 matrix (see earlier slide)
SPEARE
S-HAKE
S
P
E
A
R
E
0
-6
-12 -18 -24 -30 -36
S
-6
+2 -4
-10 -16 -22 -28
H
-12
-4
+2 -3
-9
-14
A
-18
-10 -3
+2
-7
-13
K
-24
-16 -9
-3
+1 +2 -4
E
-30
-22
-3
0
+6
-20 -1 -15 -5タンパク質の大域アラインメント：動的計画法
たんぱく質はアミノ酸で構成される。
進化中のアミノ酸の置換は生化学的性質による。
進化はたんぱく質を比較するのに重要である。
PAM
PAM:
P
ercent of
A
ccepted
M
utation matrix
PAM中の化学的類似性: ＰＡＭは似かよった化学的性質を持った
アミノ酸には、より大きなスコアを与える。
Acids & Amides D,E,N,Q (Asp, Glu, Asn, Gln)
Basic H,K,R (His, Lys, Arg)
Aromatic （芳香族） F,Y,W (Phe, Tyr, Trp)
Hydrophilic (親水性） A,C,G,P,S,T, (Ala, Cys, Gly, Pro, Ser,Thr)
Hydrophobic (疎水性） L,M,V,I (Ile, Leu, Met, Val)
Example: PAM 250
Similar amino acids have greater
score 類似アミノ酸がより大きいスコアになる。
PAM Matrices
Family of matrices PAM 80, PAM 120, PAM 250
行列のグループ
The numbers with PAM matrices represent
evolutionary distance.
数字は進化距離を示す。
Greater numbers are greater distances
より大きな数はより進化距離。
PAM 250
（１）
スコアが1以上のペアアミノ酸は、両方とも似
た機能を持つ。
（２）
スコアが１以下のペアアミノ酸は、両方とも
違う機能を持つ 。
C H +H 3N COO -HCH C O -O C H +H 3N C COO -HCH O -O HCH Aspartate (Asp, D) Glutamate (Glu, E)
Example: Asp & Glu
Score = 3
BLOSUM
BLOSUM:
Blo
cks
Su
bstitution
M
atrix
Based on BLOCKS database
ＢＬＯＣＫＳ databaseによる。
~2000 blocks from 500 families of related proteins
500の関係たんぱく質のグループの中に２０００ blocks がある。
Families of proteins with identical function
たんぱく質のグループは同じ機能を持っている
。
Blocks are short conserved patterns of 3-60 AA long
without gaps
ブロックは３から６０のAAのギャップ無しの長さのパターン
です。
AABCDA… BBCDA DABCDA. A.BBCBB BBBCDABA.BCCAA AAACDAC.DCBCDB CCBADAB.DBBDCC AAACAA… BBCCCBLOSUM Matrices
（１） ＢＬＯＳＵＭ
ｎ
は少なくとも類似度が
ｎ
％の
配列による。
（２） ＢＬＯＳＵＭ
６２
はＢＬＯＳＵＭ
４５
よりさらに配
列は似ている 。
Example : Blosum62
derived from block where the sequences share at least 62% identity すくなくとも６２％の類似度がある
Entry (i,i) is greater than
any entry (i,j), j
i.
Symmetric matrix
対称行列of
20x20 entries
BLOSUM62
(i,i) エントリは最大です。
Dynamic programming
PAM250, Gap
=6
S P E A R E S 2 1 0 1 0 0 H -1 0 1 -1 2 1 A 1 1 0 2 -2 0 K 0 -1 0 -1 3 0 E 0 -1 4 0 -1 4
These values are copied from the PAM250 matrix (see earlier slide)
S
P
E
A
R
E
0
-6
-12 -18 -24 -30 -36
S
-6
H
-12
A
-18
K
-24
E
-30
タンパク質のグローバルアライメント
Global alignment
Dynamic programming
PAM250, Gap
=6
S P E A R E S 2 1 0 1 0 0 H -1 0 1 -1 2 1 A 1 1 0 2 -2 0 K 0 -1 0 -1 3 0 E 0 -1 4 0 -1 4
These values are copied from the PAM250 matrix (see earlier slide)
SPEARE
S-HAKE
S
P
E
A
R
E
0
-6
-12 -18 -24 -30 -36
S
-6
+2 -4
-10 -16 -22 -28
H
-12
-4
+2 -3
-9
-14
A
-18
-10 -3
+2
-7
-13
K
-24
-16 -9
-3
+1 +2 -4
E
-30
-22
-3
0
+6
-20 -1 -15 -5Global alignment between proteins
Dynamic Programming
PAM250, Gap
=6
S P E A R E S 2 1 0 1 0 0 H -1 0 1 -1 2 1 A 1 1 0 2 -2 0 K 0 -1 0 -1 3 0 E 0 -1 4 0 -1 4This matrix is constructed using the PAM250 matrix
SPEARE
S-HAKE
S
P
E
A
R
E
0
-6
-12 -18 -24 -30 -36
S
-6
+2 -4
-10 -16 -22 -28
H
-12
-4
+2 -3
-9
-14
A
-18
-10 -3
+2
-7
-13
K
-24
-16 -9
-3
+1 +2 -4
E
-30
-22
-3
0
+6
-20 -1 -15 -5問題
:
T
P
A
A
E
K
K
P
A
A
R
end
Protein Scoring Systems
PTHPLASKTQILPEDLASEDLTI PTHPLAGERAIGLARLAEEDFGM Sequence 1 Sequence 2 Scoring matrix T:G = -2 T:T = 5 Score = 48 C S T P A G N D . . C 9 S -1 4 T -1 1 5 P -3 -1 -1 7 A 0 1 0 -1 4 G -3 0 -2 -2 0 6 N -3 1 0 -2 -2 0 5 D -3 0 -1 -1 -2 -1 1 6 . . C S T P A G N D . . C 9 S -1 4 T -1 1 5 P -3 -1 -1 7 A 0 1 0 -1 4 G -3 0 -2 -2 0 6 N -3 1 0 -2 -2 0 5 D -3 0 -1 -1 -2 -1 1 6 . . Blosum62
Dynamic programming for global
alignment: Proteins.
d
j
i
D
d
j
i
D
s
M
j
i
D
j
i
D
)
1
,
(
)
,
1
(
)
t[j]
[i],
(
)
1
,
1
(
max
)
,
(
d=-2 M: Similarity matrix for amino-acids (BLOSUM62, or PAM250 for example)
Dynamic programming for
protein sequences:
Smith-Waterman (local alignment)
d
j
i
D
d
j
i
D
s
M
j
i
D
j
i
D
)
1
,
(
)
,
1
(
)
t[j]
[i],
(
)
1
,
1
(
0
max
)
,
(
d=-2 M: Similarity matrix for amino-acids (BLOSUM62, or PAM250 for example)
Global alignment
Dynamic programming
PAM250, Gap
=6
S P E A R E S 2 1 0 1 0 0 H -1 0 1 -1 2 1 A 1 1 0 2 -2 0 K 0 -1 0 -1 3 0 E 0 -1 4 0 -1 4
These values are copied from the PAM250 matrix (see earlier slide)
S
P
E
A
R
E
0
-6
-12 -18 -24 -30 -36
S
-6
H
-12
A
-18
K
-24
E
-30
Global alignment
Dynamic programming
PAM250, Gap
=6
S P E A R E S 2 1 0 1 0 0 H -1 0 1 -1 2 1 A 1 1 0 2 -2 0 K 0 -1 0 -1 3 0 E 0 -1 4 0 -1 4
These values are copied from the PAM250 matrix (see earlier slide)
SPEARE
S-HAKE
S
P
E
A
R
E
0
-6
-12 -18 -24 -30 -36
S
-6
+2 -4
-10 -16 -22 -28
H
-12
-4
+2 -3
-9
-14
A
-18
-10 -3
+2
-7
-13
K
-24
-16 -9
-3
+1 +2 -4
E
-30
-22
-3
0
+6
-20 -1 -15 -5Global alignment between proteins
Dynamic Programming
PAM250, Gap
=6
S P E A R E S 2 1 0 1 0 0 H -1 0 1 -1 2 1 A 1 1 0 2 -2 0 K 0 -1 0 -1 3 0 E 0 -1 4 0 -1 4This matrix is constructed using the PAM250 matrix
