Aritalab:Lecture/Bioinformatics/Alignment

Needleman-Wunsch アルゴリズム

1970年、分子生物学者の Saul B. NeedlemanとChristian D. Wunsch は、大域アライメントのアルゴリズムを Journal of Molecular Biology誌 (1970) 48: 443-453 に発表しました。いまではNeedleman-Wunsch アルゴリズムと呼ばれています。

基本は最長共通部分列(LCS)アルゴリズムと同じで、動的計画法によるLCSのページで紹介した以下の漸化式に基づいてスコア行列を計算します。ギャップとミスマッチに対してそれぞれペナルティスコア (gap penalty σ, mismatch penalty δ)が与えられています。

$s_{i,j} = max \begin{cases} s_{i-1,j} - \sigma \\ s_{i,j-1} - \sigma \\ s_{i-1,j-1} - \mu & \mbox{if } x \ne y \\ s_{i-1,j-1} +1 & \mbox{if } x = y \end{cases}$

ここではギャップペナルティを 2、ミスマッチペナルティを 1 として、２つの配列 gctagg と aattgaagg の間のアライメントを考えてみましょう。スコア行列は右のようになります。 1行目と1列目は 0, -2, -4, -6, ... -18 とギャップペナルティに基づく等差数列ができています。これは左隣（または上）のセルからギャップペナルティ 2 を順次マイナスしてできる部分です。大域アライメントでは配列の最初と最後を揃えるために、初期状態としてギャップの数に比例するペナルティを与えます。 残りのセルは動的計画法に基づいてスコアが埋められ、最適アライメントは以下のようになります。 1:aattgaagg:9 | | || 1:gct--a-gg:6 右図のトレースバックと見比べてみてください。大域アライメントのスコアは マッチ 4 × 1 + ミスマッチ 2 × (-1) + ギャップ 3 × (-2) = -4 となっています。大域アライメントにおけるギャップの数は配列長の差になります。具体的なアルゴリズムとJavaコードはこのページを参照してください。

g c t a g g 0 -2 -4 -6 -8 -10 -12 a -2 -1 -3 -5 -5 -7 -9 a -4 -3 -2 -4 -4 -6 -8 t -6 -5 -4 -1 -3 -5 -7 t -8 -7 -6 -3 -2 -4 -6 g -10 -7 -8 -5 -4 -1 -3 a -12 -9 -8 -7 -4 -3 -2 a -14 -11 -10 -9 -6 -5 -4 g -16 -13 -12 -11 -8 -5 -4 g -18 -15 -14 -13 -10 -7 -4