Aritalab:Lecture/Bioinformatics/Alignment
(Created page with "==Needleman-Wunsch アルゴリズム== 1970年、分子生物学者の Saul B. NeedlemanとChristian D. Wunsch は、大域アライメントのアルゴリズムを Journal of...") |
|||
Line 3: | Line 3: | ||
1970年、分子生物学者の Saul B. NeedlemanとChristian D. Wunsch は、大域アライメントのアルゴリズムを Journal of Molecular Biology誌 (1970) 48: 443-453 に発表しました。いまではNeedleman-Wunsch アルゴリズムと呼ばれています。 | 1970年、分子生物学者の Saul B. NeedlemanとChristian D. Wunsch は、大域アライメントのアルゴリズムを Journal of Molecular Biology誌 (1970) 48: 443-453 に発表しました。いまではNeedleman-Wunsch アルゴリズムと呼ばれています。 | ||
− | + | 基本は最長共通部分列(LCS)アルゴリズムと同じで、[[Aritalab:Lecture/Bioinformatics/Homology|動的計画法によるLCSのページ]]で紹介した以下の漸化式に基づいてスコア行列を計算します。ギャップとミスマッチに対してそれぞれペナルティスコア (gap penalty σ, mismatch penalty δ)が与えられています。 | |
<math> 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 | <math> 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}</math> | \end{cases}</math> | ||
− | + | {| | |
+ | |valign="top"| | ||
+ | ここではギャップペナルティを 2、ミスマッチペナルティを 1 として、2つの配列 gctagg と aattgaagg の間のアライメントを考えてみましょう。スコア行列は右のようになります。 | ||
+ | |||
+ | 1行目と1列目は 0, -2, -4, -6, ... -18 とギャップペナルティに基づく等差数列ができています。これは左隣(または上)のセルからギャップペナルティ 2 を順次マイナスしてできる部分です。大域アライメントでは配列の最初と最後を揃えるために、初期状態としてギャップの数に比例するペナルティを与えます。 | ||
+ | 残りのセルは動的計画法に基づいてスコアが埋められ、最適アライメントは以下のようになります。 | ||
+ | <big><pre> | ||
+ | 1:aattgaagg:9 | ||
+ | | | || | ||
+ | 1:gct--a-gg:6 | ||
+ | </pre></big> | ||
+ | 右図のトレースバックと見比べてみてください。大域アライメントのスコアは | ||
+ | <center> | ||
+ | マッチ 4 × 1 + ミスマッチ 2 × (-1) + ギャップ 3 × (-2) = -4 | ||
+ | </center> | ||
+ | となっています。大域アライメントにおけるギャップの数は配列長の差になります。具体的なアルゴリズムとJavaコードは[[Aritalab:Lecture/Bioinformatics/Alignment/Java|このページ]]を参照してください。 | ||
+ | |||
+ | |width="30%"| | ||
+ | {| class="wikitable" style="text-align:center" | ||
+ | |style="width:2em"| | ||
+ | |style="width:2em"| | ||
+ | |style="width:2em"| g | ||
+ | |style="width:2em"| c | ||
+ | !style="width:2em"| t | ||
+ | !style="width:2em"| a | ||
+ | !style="width:2em"| g | ||
+ | !style="width:2em"| g | ||
+ | |- | ||
+ | |style="width:2em"| | ||
+ | | 0 || -2 || -4 || -6 || -8 || -10 || -12 | ||
+ | |- | ||
+ | |style="width:2em"| a | ||
+ | | -2 | ||
+ | |style="background:lightgray"| -1 || -3 || -5 || -5 || -7 || -9 | ||
+ | |- | ||
+ | |style="width:2em"| a | ||
+ | | -4 || -3 | ||
+ | |style="background:lightgray"| -2 || -4 || -4 || -6 || -8 | ||
+ | |- | ||
+ | !style="width:2em"| t | ||
+ | | -6 || -5 || -4 | ||
+ | |style="background:lightgray"| -1 || -3 || -5 || -7 | ||
+ | |- | ||
+ | |style="width:2em"| t | ||
+ | | -8 || -7 || -6 | ||
+ | |style="background:lightgray"| -3 || -2 || -4 || -6 | ||
+ | |- | ||
+ | |style="width:2em"| g | ||
+ | | -10 || -7 || -8 | ||
+ | |style="background:lightgray"| -5 || -4 || -1 || -3 | ||
+ | |- | ||
+ | !style="width:2em"| a | ||
+ | | -12 || -9 || -8 || -7 | ||
+ | |style="background:lightgray"| -4 || -3 || -2 | ||
+ | |- | ||
+ | |style="width:2em"| a | ||
+ | | -14 || -11 || -10 || -9 | ||
+ | |style="background:lightgray"| -6 || -5 || -4 | ||
+ | |- | ||
+ | !style="width:2em"| g | ||
+ | | -16 || -13 || -12 || -11 || -8 | ||
+ | |style="background:lightgray"| -5 || -4 | ||
+ | |- | ||
+ | !style="width:2em"| g | ||
+ | | -18 || -15 || -14 || -13 || -10 || -7 | ||
+ | |style="background:lightgray"| -4 | ||
+ | |} | ||
+ | |} |
Revision as of 05:41, 15 December 2011
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 δ)が与えられています。
ここではギャップペナルティを 2、ミスマッチペナルティを 1 として、2つの配列 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コードはこのページを参照してください。 |
|