Aritalab:Lecture/Bioinformatics/Alignment - Revision history

Adm at 00:52, 24 July 2012

2012-07-24T00:52:27Z

Adm at 00:51, 24 July 2012

2012-07-24T00:51:42Z

Adm: /* アフィンギャップと Gotoh アルゴリズム */

2012-01-04T06:47:10Z

‎アフィンギャップと Gotoh アルゴリズム

Adm: /* Smith-Waterman アルゴリズム */

2012-01-04T06:44:50Z

‎Smith-Waterman アルゴリズム

Adm: /* Needleman-Wunsch (-Sellers) アルゴリズム */

2012-01-04T06:43:50Z

‎Needleman-Wunsch (-Sellers) アルゴリズム

Adm: /* アフィンギャップと Gotoh アルゴリズム */

2011-12-20T06:11:52Z

‎アフィンギャップと Gotoh アルゴリズム

Adm: /* アフィンギャップと Gotoh アルゴリズム */

2011-12-18T12:48:01Z

‎アフィンギャップと Gotoh アルゴリズム

Adm: /* アフィンギャップと Gotoh アルゴリズム */

2011-12-18T12:21:39Z

‎アフィンギャップと Gotoh アルゴリズム

Adm at 05:32, 15 December 2011

2011-12-15T05:32:27Z

Adm at 05:05, 15 December 2011

2011-12-15T05:05:04Z

@@ Line 1: / Line 1: @@
-__FORCETOC__
+{| style="float:right"
+| __TOC__
 * このページで説明するアルゴリズムの [[Aritalab:Lecture/Programming/Java/Alignment| Java コード]]

@@ Line 1: / Line 1: @@
 __FORCETOC__
 ==Needleman-Wunsch (-Sellers) アルゴリズム==
 年、分子生物学者の Saul B. NeedlemanとChristian D. Wunsch は、大域アライメントのアルゴリズムを Journal of Molecular Biology誌 (1970) 48: 443-453 に発表しました。いまでは誤って Needleman-Wunsch アルゴリズムと呼ばれるようになりましたが、論文は効率が悪い手法、O(n<sup>3</sup>) 時間、を紹介しています。ここで紹介されるアルゴリズムの原型を作ったのは Peter Sellers (1974) です<ref>P Sellers "On the theory and computation of evolutionary distances" SIAM J. Appl. Math. 26:787–793, 1974 にアルゴリズムが紹介されています。</ref>。したがって正確には Needleman-Wunsch-Sellers アルゴリズムと呼ぶべきでしょう <ref>1970年当時の様子は David Sankoff "The early introduction of dynamic programming into computational biology" Bioinformatics 16(1):41-47 ([http://bioinformatics.oxfordjournals.org/content/16/1/41.full.pdf pdf])を見るとよいでしょう。</ref>。

@@ Line 155: / Line 155: @@
 ギャップは配列が切断されることを意味しますが、その間に挿入される配列の長さは配列の切断というイベントに比較して重要ではありません。そのため、実用のアルゴリズムでは
-:ギャップ開始 (open) ペナルティ &sigma;<sub>o</sub>
+:ギャップ開始 (open) ペナルティ '''&sigma;<sub>o</sub>'''
-:ギャップ伸長 (extension) ペナルティ &sigma;<sub>x</sub> (この値は開始ペナルティよりもずっと小さくする)
+:ギャップ伸長 (extension) ペナルティ '''&sigma;<sub>x</sub>'''
-を導入し、長さ n のギャップに対し &sigma;<sub>o</sub> + (n-1) &sigma;<sub>x</sub> のコストとします。ギャップ長に比例する値でコストが増加するペナルティ方式を（平行移動のアフィン変換にちなんで）アフィンギャップと呼びます。計算量を O(n<sup>2</sup>) に抑えたままアフィンギャップコストを計算するアルゴリズムを最初に示したのは日本の後藤修（ごとうおさむ）先生です<ref>O Gotoh "An improved algorithm for matching bilogical sequences" J Mol Biol 162:705-8, 1982 ([http://www.genome.ist.i.kyoto-u.ac.jp/~aln_user/archive/JMB82.pdf pdf])</ref>。
+を導入し、長さ n のギャップに対し &sigma;<sub>o</sub> + (n-1) &sigma;<sub>x</sub> のコストとします。ギャップ伸長ペナルティの値は開始ペナルティよりもずっと小さくします。ギャップ長に比例する値でコストが増加するペナルティ方式を（平行移動のアフィン変換にちなんで）アフィンギャップと呼びます。計算量を O(n<sup>2</sup>) に抑えたままアフィンギャップコストを計算するアルゴリズムを最初に示したのは日本の後藤修（ごとうおさむ）先生です<ref>O Gotoh "An improved algorithm for matching bilogical sequences" J Mol Biol 162:705-8, 1982 ([http://www.genome.ist.i.kyoto-u.ac.jp/~aln_user/archive/JMB82.pdf pdf])</ref>。

@@ Line 82: / Line 82: @@
 バイオインフォマティクスの草分けである Temple F. Smith と Michael S. Waterman が 1981 年に Journal of Molecular Biology誌 (147: 195–197) に発表した局所アライメントを求めるアルゴリズムです。MS Waterman は動的計画法を RNA 二次構造の解析などに応用して活躍した数学者ですが、TF Smithは配列アライメントに関する実績もなく、このアルゴリズムをWalther Goad から聞いて論文にしたといわれる曰くつきのアルゴリズムです<ref>Walter Goad は後日 W Goad "Sequence Analysis: Contributions by Ulam to Molecular Genetics" Los Alamos Science (special issue) 288-291, 1987 ([http://library.lanl.gov/cgi-bin/getfile?15-21.pdf pdf]) に、自分のほうが先に見つけたと言いたげな記述をしています。</ref>。FASTAパッケージ（後述）の中では SSEARCH の名前で実装されていました。局所アライメントは以下のように定義されます。
-<center>
+<pre>
 局所アライメント = 与えられた２つの配列それぞれの全ての部分配列のペア中で、大域アライメントのスコアを最大にするもの
-</center>
+</pre>
-すべての部分配列を列挙して大域アライメントを施す必要が思えますが、そうではありません。動的計画法において常にスコア 0 を候補に置くだけで、同じ計算時間で局所アライメントを求められるところが大変エレガントなアルゴリズムです。オリジナル論文はアフィンギャップ関数（後述）という、生物学的に意味のあるギャップペナルティを採用しています。
+この定義だとすべての部分配列を列挙して大域アライメントを施す必要が思えますが、そうではありません。動的計画法において常にスコア 0 を候補に置くだけで、同じ計算時間で局所アライメントを求められるところが大変エレガントなアルゴリズムです。オリジナル論文はアフィンギャップ関数（後述）という、生物学的に意味のあるギャップペナルティを採用しています。
 <math> D_{i,j} = max \begin{cases}0 \\ D_{i-1,j} - \sigma \\ D_{i,j-1} - \sigma \\ D_{i-1,j-1} - \mu & \mbox{if } s_i \ne t_j \\ D_{i-1,j-1} +1 & \mbox{if } s_i = t_j

@@ Line 4: / Line 4: @@
 年、分子生物学者の Saul B. NeedlemanとChristian D. Wunsch は、大域アライメントのアルゴリズムを Journal of Molecular Biology誌 (1970) 48: 443-453 に発表しました。いまでは誤って Needleman-Wunsch アルゴリズムと呼ばれるようになりましたが、論文は効率が悪い手法、O(n<sup>3</sup>) 時間、を紹介しています。ここで紹介されるアルゴリズムの原型を作ったのは Peter Sellers (1974) です<ref>P Sellers "On the theory and computation of evolutionary distances" SIAM J. Appl. Math. 26:787–793, 1974 にアルゴリズムが紹介されています。</ref>。したがって正確には Needleman-Wunsch-Sellers アルゴリズムと呼ぶべきでしょう <ref>1970年当時の様子は David Sankoff "The early introduction of dynamic programming into computational biology" Bioinformatics 16(1):41-47 ([http://bioinformatics.oxfordjournals.org/content/16/1/41.full.pdf pdf])を見るとよいでしょう。</ref>。
-基本は最長共通部分列(LCS)アルゴリズムと同じで、[[Aritalab:Lecture/Bioinformatics/Homology|動的計画法によるLCSのページ]]で紹介した以下の漸化式に基づいてスコア行列を計算します。ギャップとミスマッチに対してそれぞれペナルティスコア (gap penalty &sigma;, mismatch penalty &delta;)が与えられています。
+基本は最長共通部分列(LCS)アルゴリズムと同じで、[[Aritalab:Lecture/Bioinformatics/Homology|動的計画法によるLCSのページ]]で紹介した以下の漸化式に基づいてスコア行列を計算します。ギャップとミスマッチに対してそれぞれペナルティスコア (gap penalty &sigma;, mismatch penalty &mu;)が与えられています。
 <math> D_{i,j} = max \begin{cases} D_{i-1,j} - \sigma \\ D_{i,j-1} - \sigma \\ D_{i-1,j-1} - \mu & \mbox{if } s_i \ne t_j \\ D_{i-1,j-1} +1 & \mbox{if } s_i = t_j

@@ Line 167: / Line 167: @@
 </center>
-と書けます。ギャップスペース数に対するペナルティはこれまでのギャップと同じなので、問題はギャップ開始数の数え方です。
+と書けます。
-各セルに ( i, j ) の値として
-# i を
-−
 {|

@@ Line 158: / Line 158: @@
 :ギャップ伸長 (extension) ペナルティ &sigma;<sub>x</sub> (この値は開始ペナルティよりもずっと小さくする)
-を導入し、長さ n のギャップに対し &sigma;<sub>o</sub> + n &sigma;<sub>x</sub> のコストとします。ギャップ長に比例する値でコストが増加するペナルティ方式を（平行移動のアフィン変換にちなんで）アフィンギャップと呼びます。計算量を O(n<sup>2</sup>) に抑えたままアフィンギャップコストを計算するアルゴリズムを最初に示したのは日本の後藤修（ごとうおさむ）先生です<ref>O Gotoh "An improved algorithm for matching bilogical sequences" J Mol Biol 162:705-8, 1982 ([http://www.genome.ist.i.kyoto-u.ac.jp/~aln_user/archive/JMB82.pdf pdf])</ref>。
+を導入し、長さ n のギャップに対し &sigma;<sub>o</sub> + (n-1) &sigma;<sub>x</sub> のコストとします。ギャップ長に比例する値でコストが増加するペナルティ方式を（平行移動のアフィン変換にちなんで）アフィンギャップと呼びます。計算量を O(n<sup>2</sup>) に抑えたままアフィンギャップコストを計算するアルゴリズムを最初に示したのは日本の後藤修（ごとうおさむ）先生です<ref>O Gotoh "An improved algorithm for matching bilogical sequences" J Mol Biol 162:705-8, 1982 ([http://www.genome.ist.i.kyoto-u.ac.jp/~aln_user/archive/JMB82.pdf pdf])</ref>。
@@ Line 168: / Line 168: @@
 と書けます。ギャップスペース数に対するペナルティはこれまでのギャップと同じなので、問題はギャップ開始数の数え方です。
 {|
@@ Line 177: / Line 180: @@
 D_{i,j} &= max \begin{cases}0 \\ P_{i-1,j} \\ Q_{i,j-1} \\ D_{i-1,j-1} - \mu & \mbox{if } s_i \ne t_j \\ D_{i-1,j-1} +1 & \mbox{if } s_i = t_j
 \end{cases} \\
-P_{i,j} &= max \begin{cases} D_{i-1, j} - \sigma_o \\ P_{i-1,j} \end{cases} - \sigma_x  \\
+P_{i,j} &= max \begin{cases} D_{i-1, j} - \sigma_o \\ P_{i-1,j} - \sigma_x \end{cases}  \\
-Q_{i,j} &= max \begin{cases} D_{i, j-1} - \sigma_o \\ Q_{i,j-1} \end{cases} - \sigma_x  \\
+Q_{i,j} &= max \begin{cases} D_{i, j-1} - \sigma_o \\ Q_{i,j-1} - \sigma_x \end{cases}  \\
 \end{align}
 </math>
@@ Line 196: / Line 199: @@
 |-
 | -2.0 || || || ||
-|rowspan="4"|
+|rowspan="3"|
 |rowspan="4" style="background:lightgray"|
 |-
@@ Line 204: / Line 207: @@
 |-
 |  :
 |-
 | i
@@ Line 212: / Line 217: @@
 </center>
-位置 (i , j) にいるとき、スコアの求め方を考えましょう。普通に考えるとセル (i , j) の左側全部と上側全部のセル（影がかかっている領域）全ての位置から、ギャップが入る可能性を検討しなくてはなりません。それを素直に実行すると各セルの値を計算するのに O(n) 時間かかるため、全体で O(n<sup>3</sup>) 時間の計算量になります。その手間を省くために行列 P, Q を導入します。
+位置 (i , j) にいるとき、スコアの求め方を考えましょう。普通に考えるとセル (i , j) の左側全部と上側全部のセル（薄い影がかかっている領域）全ての位置から、ギャップが入る可能性を検討しなくてはなりません。それを素直に実行すると各セルの値を計算するのに O(n) 時間かかるため、全体で O(n<sup>3</sup>) 時間の計算量になります。その手間を省くために行列 P, Q を導入します。
-行列 P, Q はそれぞれ位置 (i , j) が横方向および縦方向のギャップに含まれる際のスコアを記録しておく部分です。P と Q の漸化式をみると、それまで続いていたギャップを延長するか (P なら位置 i をスキップし、Q なら位置 j をスキップ）、新たに位置 i , j からギャップを開くか判断しています。これらの行列に前の方からギャップを伸長した場合のスコアを記録してあり、マッチとミスマッチによるスコアとの比較を常におこなうのです。
+行列 P, Q はそれぞれ位置 (i , j) が横方向および縦方向のギャップに含まれる際のスコアを記録しておく部分です。P と Q の漸化式をみると、それまで続いていたギャップを延長するか (P なら位置 i をスキップし、Q なら位置 j をスキップ）、新たに位置 i , j からギャップを開くか判断しています。これらの行列に前の方からギャップを伸長した場合のスコアを記録してあり、通常のスコアとの比較をおこないます。
 |}

← Older revision		Revision as of 12:21, 18 December 2011
Line 158:		Line 158:
	:ギャップ伸長 (extension) ペナルティ σ<sub>x</sub> (この値は開始ペナルティよりもずっと小さくする)		:ギャップ伸長 (extension) ペナルティ σ<sub>x</sub> (この値は開始ペナルティよりもずっと小さくする)

−	を導入し、長さ n のギャップに対し σ<sub>o</sub> + n σ<sub>x</sub> のコストとします。ギャップ長に比例する値でコストが増加するペナルティ方式を（平行移動のアフィン変換にちなんで）アフィンギャップと呼びます。計算量を O(n<sup>2</sup>) ~~に抑えたままアフィンギャップコストを計算するアルゴリズムを最初に示したのは日本の後藤修先生です~~<ref>O Gotoh "An improved algorithm for matching bilogical sequences" J Mol Biol 162:705-8, 1982 ([http://www.genome.ist.i.kyoto-u.ac.jp/~aln_user/archive/JMB82.pdf pdf])</ref>。	+	を導入し、長さ n のギャップに対し σ<sub>o</sub> + n σ<sub>x</sub> のコストとします。ギャップ長に比例する値でコストが増加するペナルティ方式を（平行移動のアフィン変換にちなんで）アフィンギャップと呼びます。計算量を O(n<sup>2</sup>) に抑えたままアフィンギャップコストを計算するアルゴリズムを最初に示したのは日本の後藤修（ごとうおさむ）先生です<ref>O Gotoh "An improved algorithm for matching bilogical sequences" J Mol Biol 162:705-8, 1982 ([http://www.genome.ist.i.kyoto-u.ac.jp/~aln_user/archive/JMB82.pdf pdf])</ref>。

@@ Line 24: / Line 24: @@
 マッチ 4 &times; 1 + ミスマッチ 2 &times; (-1) + ギャップ 3 &times; (-2) = -4
 </center>
-となっています。大域アライメントにおけるギャップの数は配列長の差になります。具体的なアルゴリズムとJavaコードは[[Aritalab:Lecture/Bioinformatics/Alignment/Java|このページ]]を参照してください。
+となっています。大域アライメントにおけるギャップの数は配列長の差になります。具体的なアルゴリズムとJavaコードは[[Aritalab:Lecture/Programming/Java/Alignment|このページ]]を参照してください。
 |width="30%"|
@@ Line 102: / Line 102: @@
 :agg:6
 </pre></big>
-具体的なアルゴリズムとJavaコードは[[Aritalab:Lecture/Bioinformatics/Alignment/Java|このページ]]を参照してください。
+具体的なアルゴリズムとJavaコードは[[Aritalab:Lecture/Programming/Java/Alignment|このページ]]を参照してください。
 |width="30%"|

← Older revision		Revision as of 05:05, 15 December 2011
Line 1:		Line 1:
		+	__FORCETOC__
		+
	==Needleman-Wunsch (-Sellers) アルゴリズム==		==Needleman-Wunsch (-Sellers) アルゴリズム==
	1970年、分子生物学者の Saul B. NeedlemanとChristian D. Wunsch は、大域アライメントのアルゴリズムを Journal of Molecular Biology誌 (1970) 48: 443-453 に発表しました。いまでは誤って Needleman-Wunsch アルゴリズムと呼ばれるようになりましたが、論文は効率が悪い手法、O(n<sup>3</sup>) 時間、を紹介しています。ここで紹介されるアルゴリズムの原型を作ったのは Peter Sellers (1974) です<ref>P Sellers "On the theory and computation of evolutionary distances" SIAM J. Appl. Math. 26:787–793, 1974 にアルゴリズムが紹介されています。</ref>。したがって正確には Needleman-Wunsch-Sellers アルゴリズムと呼ぶべきでしょう <ref>1970年当時の様子は David Sankoff "The early introduction of dynamic programming into computational biology" Bioinformatics 16(1):41-47 ([http://bioinformatics.oxfordjournals.org/content/16/1/41.full.pdf pdf])を見るとよいでしょう。</ref>。		1970年、分子生物学者の Saul B. NeedlemanとChristian D. Wunsch は、大域アライメントのアルゴリズムを Journal of Molecular Biology誌 (1970) 48: 443-453 に発表しました。いまでは誤って Needleman-Wunsch アルゴリズムと呼ばれるようになりましたが、論文は効率が悪い手法、O(n<sup>3</sup>) 時間、を紹介しています。ここで紹介されるアルゴリズムの原型を作ったのは Peter Sellers (1974) です<ref>P Sellers "On the theory and computation of evolutionary distances" SIAM J. Appl. Math. 26:787–793, 1974 にアルゴリズムが紹介されています。</ref>。したがって正確には Needleman-Wunsch-Sellers アルゴリズムと呼ぶべきでしょう <ref>1970年当時の様子は David Sankoff "The early introduction of dynamic programming into computational biology" Bioinformatics 16(1):41-47 ([http://bioinformatics.oxfordjournals.org/content/16/1/41.full.pdf pdf])を見るとよいでしょう。</ref>。