PictBio HP「解析メモ」から移行中です。
元記事：2016/12/08 公開 シーケンスアライメントの計算
NGSデータ解析におけるアライメント
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データ解析ツールに求められています。