Aritalab:Lecture/Bioinformatics/Alignment

From Metabolomics.JP
< Aritalab:Lecture | Bioinformatics(Difference between revisions)
Jump to: navigation, search
(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アルゴリズムと同じですが、ギャップとミスマッチに対してそれぞれペナルティスコアが与えられています。
+
基本は最長共通部分列(LCS)アルゴリズムと同じで、[[Aritalab:Lecture/Bioinformatics/Homology|動的計画法によるLCSのページ]]で紹介した以下の漸化式に基づいてスコア行列を計算します。ギャップとミスマッチに対してそれぞれペナルティスコア (gap penalty &sigma;, mismatch penalty &delta;)が与えられています。
  
 
<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>
  
−
具体的なアルゴリズムとJavaコードはこちらを参照してください。
+
{|
 +
|valign="top"|
 +
ここではギャップペナルティを 2、ミスマッチペナルティを 1 として、２つの配列 gctagg と aattgaagg の間のアライメントを考えてみましょう。スコア行列は右のようになります。
 +
 
 +
1行目と1列目は 0, -2, -4, -6, ... -18 とギャップペナルティに基づく等差数列ができています。これは左隣（または上）のセルからギャップペナルティ 2 を順次マイナスしてできる部分です。大域アライメントでは配列の最初と最後を揃えるために、初期状態としてギャップの数に比例するペナルティを与えます。
 +
残りのセルは動的計画法に基づいてスコアが埋められ、最適アライメントは以下のようになります。
 +
<big><pre>
 +
  1:aattgaagg:9
 +
      |  | ||   
 +
  1:gct--a-gg:6
 +
</pre></big>
 +
右図のトレースバックと見比べてみてください。大域アライメントのスコアは
 +
<center>
 +
マッチ 4 &times; 1 + ミスマッチ 2 &times; (-1) + ギャップ 3 &times; (-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 δ)が与えられています。

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
Retrieved from "http://metabolomics.jp/mediawiki/index.php?title=Aritalab:Lecture/Bioinformatics/Alignment&oldid=254726"
Personal tools
Namespaces

Variants
Actions
Navigation
metabolites
Toolbox