シーケンスアライメントの計算

 NGSデータ解析におけるアライメントは、マッピングなどの配列(文字の並び)を比較の際に出てくる用語です。NGSはシーケンス配列を得るための機器のため、アライメントが最も重要となる計算です。

 では、この計算はどのようなロジックで行われているのでしょうか?
 現在の比較手法は複数の配列を文字位置で一文字ずつ合わせてずれを調整します。パターンが複数できた場合は、最も一致度の高いものを採用します。この一致度の計算方法ですが、下記のような二次元の表でパターンごとのスコアを決めるスコア行列(スコアテーブル、スコア関数)を用います。計算結果で最もスコア値が大きいパターンが「最も一致度が高いパターン」とされます。

ex : 塩基のスコア行列

A T G C
A 1 0 0 0
T 0 1 0 0
G 0 0 1 0
C 0 0 0 1

 この表で見ていくと、Aに対する位置がAである場合「1」の値が付きます。Aに対する位置がA以外の場合「0」です(ミスマッチ)。AはAの位置に必ず来るように並べらればいいのですが、比較する配列によって他の塩基位置は一致してもAだけ対応が見つからない場合もあるでしょう。このような不一致はゲノムと比較した場合、変異として疑うことができます。

 スコアの設定ができたら配列を縦横軸に並べた二次元の表(ドットマトリックス表)で配列を比較します。下記の表で実際に見てみましょう。

ex : 塩基配列のドットマトリックス

 一致個所に印をつけ、左上から右下の向きに一致が連続している並びをたどります。途切れた場合は、同じく左上から右下の向きに縦横に進み、折れ線を作成します。いくつかパターンができますので、ここでスコア計算を行います。
 できた折れ線の縦横はギャップを表し、マイナスのスコアが割り当てられます。例のパターンに上表のスコアを当てはめると下記のようになります。(ギャップを-2とします。)

  1. 赤→緑
    横の配列 C T G A T G C G A C
    アライメント | | | | | | |
    縦の配列 T G A T G A C G A C

    マッチ7 + ギャップ2 = 1×7 + -2×2 = 3

  2. 赤→青
    横の配列 C T G A T G C G A C
    アライメント | | | | | | | | |
    縦の配列 T G A T G A C G A C

    マッチ8 + ギャップ1 = 1×8 + -2×1 = 6

  3. 黄→青
    横の配列 C T G A T G C G A C
    アライメント | | | | | | | |
    縦の配列 T G A T G A C G A C

    マッチ7 + ミスマッチ1 + ギャップ2 = 1×7 + 0x1 + -2×2 = 3

結果 :「2. 赤→青」のスコアが高い       
= 最も一致度の高いアライメントパターン

 アライメントはいくつか種類があり、3配列以上を比較する「マルチプルアライメント」、2配列で比較する「ペアワイズアライメント」があります。また、配列の全体を比較する「グローバルアライメント」、配列の一部分を比較する「ローカルアライメント」と分けられます。
 いずれも基本的には上記の手法をとっており、この計算を高速にすることがNGSデータ解析ツールに求められています。