📂アルゴリズム

シーケンスアラインメントスコアとギャップペナルティ

定義

参照配列とクエリ配列が与えられているとしよう。配列アラインメントスコア^{sequence Alignment Score}とは、２つの配列を比較した時にどの程度一致しているかを数値化すること、及びその方法を言う。スコアリングは以下の項目に重みを付けて計算される。

1. マッチ: ２つの配列が一致する回数だ。
2. ミスマッチ: ２つの配列が一致しない回数だ。

例

例として、上に示された２つの塩基配列があるとする。これらの配列をアラインする方法は様々あるが、どのアラインが最も良いかについては、比較的客観的な根拠が必要だろう。この例の２つの配列は長さが異なるため、後ろが飛び出すことがあるが、これを防ぐためにギャップ^gapを加えることになる。

この２つがどれだけ一致しているかを数値化したければ、マッチとミスマッチの数に比例したスコアを与えるのが合理的だろう。マッチは6回、赤いミスマッチは2回だ。ここで、２つのスコア体系Ａ, Ｂを考えてみよう。Ａ体系はマッチに2点、ミスマッチに-1点を与え、Ｂ体系はマッチに1点、ミスマッチに-2点を与える。するとＡ体系では$2\cdot 6 - 1 \cdot 2= 10$点、Ｂ体系では$1\cdot 6 - 2 \cdot 2= 2$点になるだろう。これは同じであるか、異なるかの２つの視点からアラインを評価したと言える。以降はマッチに1点、ミスマッチに-1点を与えることにしよう。その上でのこのアラインは$6-2=4$点になる。マッチとミスマッチに与える加点と減点は任意に設定しても良いが、既に広く使われているスコア表を利用することもできる。これは置換行列と呼ばれるもので、塩基配列だけでなく、タンパク質配列や他の文字にも使用でき、どの程度似ているかが反映された細かいスコア付けが可能だ。

一方、後ろが飛び出すことを防ぐためにギャップを加えたとしても、それも違いとして存在するため、ペナルティを課したい、これをギャップペナルティという。

ギャップペナルティ

3. ギャップ: 長さを合わせるために空白が追加される回数だ。
   1. コンスタントギャップペナルティ: ギャップがあればペナルティを課す。
   2. リニアギャップペナルティ: ギャップの数に比例してペナルティを課す。
   3. アフィンギャップペナルティ: ギャップの存在とその長さにペナルティを課す。
      1. オープン (ギャップペナルティ): ギャップの連なりが始まる地点の数だ。
      2. エクステンション (ギャップペナルティ): オープン後に続くギャップの数を全て足したものだ。

例

コンスタントでギャップペナルティ-10を与えると、以下のアラインのスコアは$4-10 = -6$点だ。リニアでギャップペナルティ-1を与えると、ギャップの数に比例して$4-1\cdot 5 = -1$点になる。

アフィンギャップペナルティは、最も広く使われる方法だ。オープンは文字通り、ギャップの区間が始まることを指し、エクステンションはその開いた区間がどれだけ拡張されるかを示す。オープンのギャップペナルティを-2, エクステンションのギャップペナルティを-1とした場合、ギャップの区間が２つあるので、オープンは2, その二つを引いたエクステンションは$5-2=3$個になり、最終スコアは$10-2\cdot 2 - 1 \cdot 3 = 3$点になる。

ギャップペナルティに付けられた名前が妥当であることは、以下の図を見ると簡単に理解できる。コンスタントはギャップの存在自体にペナルティを与え、リニアは数に比例してペナルティを与える。アフィンやアファインと付けられている言葉は数学全般で「平行移動」を含み、ギャップペナルティを示す直線が平行移動という概念とよく合っている。

¹