タンパク質配列の並べ方（アラインメント）とアラインメント・スコア

一般的なアミノ酸配列の並べ方について述べます．

(注意：配布したプログラム seqid.c は，以下の方法でアミノ酸配列を並べた 後にアラインメント・スコアと配列類似度（sequence id.）を計算するプログラ ムのはずです．しかし，もしも以下の記述とプログラムの計算が違っている場合 で，本選中にプログラムの変更のアナウンスがなかった場合には，このコンテス トに限り，プログラムの計算する値を正しい類似度と考えることにします．)

１．タンパク質（アミノ酸配列）について

タンパク質はアミノ酸配列からなっています．アミノ酸を表わす記号は，アルフ ァベット A 〜 Z から J, O, U, X を除いた 22 記号です．普通 20 種類といわ れていますが，グルタミンとグルタミン酸，アスパラギンとアスパラギン酸の区 別がつかない場合の記号を導入した結果，2 種類増えています．今回我々が対象 とするタンパク質は，この 22 種類の記号の列からなっています．

２．並べ方（アラインメント）

2 本のアミノ酸配列を並べる場合，
  1. 一方の配列の先頭に適当数空白を挿入し列の開始位置を右にずらす．
  2. 一方の配列の途中で -（ギャップ）を適当数挿入する．
という操作を行って，対応する記号を調整することができます．

ただし，空白やギャップを挿入するできるのは，相手の列が終わる前までです． たとえば，次の例の (a), (b) のように，相手の列の最後の記号まで挿入が続か ないようにします． 

   例：  (a) AABB         (b) AABBCCCCDD
                 CCDD         AA**CC****EE
また，空白や ギャップを両方の配列の同じ位置に挿入することも可能ですが， 両方に同時に挿入しても意味ないので考えないことにします．

３．並べ方ごとの得点

空白やギャップの挿入方法を決めると，どの記号とどの記号を対応させるかが決 まります．すると，得点も次のように決まります． 
   得点 = 各記号間の得点の合計 + ギャップのペナルティ
記号間の得点は付録の表「アミノ酸間の得点表」で定義されている通りで す．たとえば，下の例では， 
   A A B B C C D D - - E E F 
   A A - - - - D D K K K E F G G
   4+4        +6+6    +1+5+6 = 32
が各記号間の類似度の合計になります．一方，ギャップ（- 挿入）のペナルティ は - を最初に挿入するところで -10，続いて挿入するところで -1 として計算 します．たとえば， 
   A A B B C C D D - - E E F 
   A A - - - - D D K K K E F G G
     -10-1-1-1   -10-1 = -24
です．したがって，例題の得点は 32-24=8 になります．

４．アラインメント・スコアの定義（以下，単に「スコア」と呼ぶ<）

以上の準備のもと，2 つのタンパク質配列 X, Y 間のスコアは，次のように定義 されます． 
   スコア(X, Y) = 得点のうちの最大値
たとえば，課題説明の例で使った次の X,Y の列では，スコアは 36 です． 
   X: CBADDKDDBBTPPEP
   Y: CGAEEDDKDDBBTEEFGKKK
これは，次のような挿入を考えた場合の得点になっています． 
   X: CBA--DDKDDBBTPPEP
   Y: CGAEEDDKDDBBTEEFGKKK
タンパク質の配列は，得点の最大値（つまり，スコア（X,Y））を与えるように並 べる決まりになっています．

５．スコアの計算法

以上でスコアは完全に定義されました．でも，定義されたからといって，簡単に 計算できるかどうかは別問題です．幸いなことにスコアの計算は，漸化式で再帰 的に書くことができます．しかも，表に計算結果をしまうことで再計算を避ける 手法（皆さんが予選で使ったあの手法です）で，かなり効率よく計算することが できるのです．以下では，漸化式で計算するところまでを説明します．

まずは手始めにギャップのペナルティがいつでも一定で，ギャップの挿入 1 つ あたり -1 という場合を考えてみましょう．

スコアを求めたい列 X, Y が，配列 X[1..m], Y[1..n] に与えられているものと します．また，X の何文字目かを指す変数を i (1 <= i <= m)，Y の何文字目か を指す変数を j (1 <= j <= n) とします．ここで，スコアの計算を一般化し， 次のような関数の計算を考えます． 

   score0(i, j) = X[i..n], Y[j..n] のスコア
このように一般化することで漸化式を立てることができるのです．実際，次のよ うな漸化式で計算できます． 
   score0(i, j) = max( TBL[X[i],Y[j]] + score0(i+1, j+1),  -- (i)
                       -1 + score0(i, j+1),                -- (ii)
                       -1 + score0(i+1, j) )               -- (iii)
ここで，(i) は X[i] と Y[j] を対応させた場合の得点，(ii) は X 側に ギャップ を 1 つ挿入した場合（挿入がその次も続く可能性有り）の得点，(iii) は Y 側にギャップを 1 つ挿入した場合の得点です．X[i], Y[j] の比較に関しては，こ の 3 通りしかありえないので，この 3 つの得点で最大のものが score0(i, j) となります．なお，TBL[X[i], Y[j]] は，記号間の類似度（「アミノ酸間の得点表」）の値を与 える配列です．

漸化式の定義では，端の定義も重要です．この場合は i = m のときと j = n のときです．どちらも同じなので，ここでは i = m の場合（X が最後の 1 文 字の場合）を考えましょう．この場合には，Y 側でギャップを挿入して X[m] を 飛ばすことはできません．したがって，漸化式は次のようになります． 

   score0(m, j) = max( TBL[X[m],Y[j]], -1 + score0(m, j+1) )
以上のように score0(i, j) を定義できました．では，肝心のスコア(X, Y) の計算はどうなるでしょうか？これは score0(i, j) を使って次のように計算 できます． 
   スコア(X, Y) = max( score0(1, 1), score0(1, 2), ..., score0(1, n),
                                     score0(2, 1), ..., score0(m, 1) )
たとえば，score0(1, k) は，X[1..n] と Y[k..m] の得点ですが，これは， X[1] を Y の k 文字目に対応させたものです．つまり，列 X の前に k - 1 個 の空白を入れたことに対応するのです．

以上は，ギャップのペナルティがいつでも一定の場合でした．でも実際には， 最初にギャップが挿入されたときだけペナルティが -10 になるのでした．一方， ギャップの挿入が続いているときは，ペナルティは -1 です．そこで，ギャップ の挿入が続いているときか否かを区別するため， 

   score0(i, j) = X[i..n], Y[j..n] のスコア（何もないとき）
   score1(i, j) = ここまで X 側に ギャップが挿入されてきているときの
                  X[i..n], Y[j..n] のスコア
   score2(i, j) = ここまで Y 側にギャップが挿入されてきているときの
                  X[i..n], Y[j..n] のスコア
と 3 つの関数に分けて考えましょう．

この場合も考え方は前とまったく同じで，変えるところも少しです．たとえば， score0 の場合には 

   score0(i, j) = max( TBL[X[i],Y[j]] + score0(i+1, j+1),  -- (i)
                       -10 + score1(i, j+1),               -- (ii)
                       -10 + score2(i+1, j) )              -- (iii)

   score0(m, j) = max( TBL[X[m],Y[j]], -10 + score1(m, j+1) )
となります．一方，score1, score2 の場合にはギャップを続けるか，あるいは， 打ち切って本当に比較するかのどちらかですので，漸化式は次のようになります． （例として score1 についてのみ説明します．） 
   score1(i, j) = max( TBL[X[i],Y[j]] + score0(i+1, j+1),  -- (i)
                       -1 + score1(i, j+1) )               -- (ii)

   score1(m, j) = max( TBL[X[m],Y[j]], -1 + score1(m, j+1) )

ただし，スコア(X, Y) を計算するときに使うのは score0(i, j) のみです．

(参考: スコア計算プログラムscoreout.c)

================================

付録：アミノ酸間の得点表

http://www.ncbi.nlm.nih.gov/blast/html/sub_matrix.html より転載．（正
確には BLOSUM62 のスコア表）

    A  R  N  D  C  Q  E  G  H  I  L  K  M  F  P  S  T  W  Y  V  B  Z  X 
 A  4 -1 -2 -2  0 -1 -1  0 -2 -1 -1 -1 -1 -2 -1  1  0 -3 -2  0 -2 -1  0 
 R -1  5  0 -2 -3  1  0 -2  0 -3 -2  2 -1 -3 -2 -1 -1 -3 -2 -3 -1  0 -1 
 N -2  0  6  1 -3  0  0  0  1 -3 -3  0 -2 -3 -2  1  0 -4 -2 -3  3  0 -1 
 D -2 -2  1  6 -3  0  2 -1 -1 -3 -4 -1 -3 -3 -1  0 -1 -4 -3 -3  4  1 -1 
 C  0 -3 -3 -3  9 -3 -4 -3 -3 -1 -1 -3 -1 -2 -3 -1 -1 -2 -2 -1 -3 -3 -2 
 Q -1  1  0  0 -3  5  2 -2  0 -3 -2  1  0 -3 -1  0 -1 -2 -1 -2  0  3 -1 
 E -1  0  0  2 -4  2  5 -2  0 -3 -3  1 -2 -3 -1  0 -1 -3 -2 -2  1  4 -1 
 G  0 -2  0 -1 -3 -2 -2  6 -2 -4 -4 -2 -3 -3 -2  0 -2 -2 -3 -3 -1 -2 -1 
 H -2  0  1 -1 -3  0  0 -2  8 -3 -3 -1 -2 -1 -2 -1 -2 -2  2 -3  0  0 -1 
 I -1 -3 -3 -3 -1 -3 -3 -4 -3  4  2 -3  1  0 -3 -2 -1 -3 -1  3 -3 -3 -1 
 L -1 -2 -3 -4 -1 -2 -3 -4 -3  2  4 -2  2  0 -3 -2 -1 -2 -1  1 -4 -3 -1 
 K -1  2  0 -1 -3  1  1 -2 -1 -3 -2  5 -1 -3 -1  0 -1 -3 -2 -2  0  1 -1 
 M -1 -1 -2 -3 -1  0 -2 -3 -2  1  2 -1  5  0 -2 -1 -1 -1 -1  1 -3 -1 -1 
 F -2 -3 -3 -3 -2 -3 -3 -3 -1  0  0 -3  0  6 -4 -2 -2  1  3 -1 -3 -3 -1 
 P -1 -2 -2 -1 -3 -1 -1 -2 -2 -3 -3 -1 -2 -4  7 -1 -1 -4 -3 -2 -2 -1 -2 
 S  1 -1  1  0 -1  0  0  0 -1 -2 -2  0 -1 -2 -1  4  1 -3 -2 -2  0  0  0 
 T  0 -1  0 -1 -1 -1 -1 -2 -2 -1 -1 -1 -1 -2 -1  1  5 -2 -2  0 -1 -1  0 
 W -3 -3 -4 -4 -2 -2 -3 -2 -2 -3 -2 -3 -1  1 -4 -3 -2 11  2 -3 -4 -3 -2 
 Y -2 -2 -2 -3 -2 -1 -2 -3  2 -1 -1 -2 -1  3 -3 -2 -2  2  7 -1 -3 -2 -1 
 V  0 -3 -3 -3 -1 -2 -2 -3 -3  3  1 -2  1 -1 -2 -2  0 -3 -1  4 -3 -2 -1 
 B -2 -1  3  4 -3  0  1 -1  0 -3 -4  0 -3 -3 -2  0 -1 -4 -3 -3  4  1 -1 
 Z -1  0  0  1 -3  3  4 -2  0 -3 -3  1 -1 -3 -1  0 -1 -3 -2 -2  1  4 -1 
 X  0 -1 -1 -1 -2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -2  0  0 -2 -1 -1 -1 -1 -1 

注：X はその他の記号の総称
以上．