Aritalab:Lecture/Bioinformatics/MotifFinding - Revision history

Adm at 11:40, 18 December 2011

2011-12-18T11:40:18Z

Adm: /* 応用テクニック */

2011-12-18T00:07:16Z

‎応用テクニック

Adm: /* アルゴリズム */

2011-12-16T07:01:28Z

‎アルゴリズム

Adm: son

2011-12-16T06:42:07Z

son

Adm at 05:28, 7 November 2011

2011-11-07T05:28:57Z

Adm: /* モチーフの候補探し */

2011-11-07T05:27:32Z

‎モチーフの候補探し

Adm at 02:41, 7 November 2011

2011-11-07T02:41:34Z

Adm: /* モチーフ発見問題 */

2011-11-07T01:38:37Z

‎モチーフ発見問題

Adm: /* モチーフ発見問題 */

2011-11-06T17:27:58Z

‎モチーフ発見問題

Adm: /* プロファイル行列 */

2011-11-06T17:11:11Z

‎プロファイル行列

@@ Line 135: / Line 135: @@
 もし s がばらばらな配列要素を指していたらプロファイルは平均的なものになるため、更新されるモチーフ位置はほとんどランダムに決定されます。しかし何らかの正しいモチーフに近いプロファイルが形成された途端、プロファイルは正確にモチーフを選び出すようになって収束します。最適解を返す保証はありませんが、実用上は大変便利なことが知られています。
-===応用テクニック===
+===スコア関数===
-;局所解に陥らない工夫
-;長さ k を自動的に決定する工夫
+基本は <math>\sum - p \log p </math> という平均情報量を計算します。しかし各アミノ酸は均等な割合で出てくるわけではないので単純な頻度である <math>\textstyle p = \frac{c_{i,j}}{(n-1)}</math> の代わりに背景となるアミノ酸頻度との比 <math>\textstyle \frac{c_{i,j}}{\bar{c}_{j}}</math> をアミノ酸 j の情報量とし、さらに擬似カウントをつけ足しています。
-通常はモチーフの長さ k をあらかじめ知ることができません。しかし、k を自由に設定できるようにすると、その値が長いほどプロファイルのスコアが高くなって不必要に長いモチーフを探してしまいます。これを防ぐには、プロファイルのスコアから k に比例する値を引いて k の長さを調節させます。
 ;参考
 <references/>

@@ Line 137: / Line 137: @@
 ===応用テクニック===
 ;局所解に陥らない工夫
 ;参考
 <references/>

@@ Line 133: / Line 133: @@
 # 更新によって値が変化しなくなるまで（収束するまで）繰り返す
-このアプローチは（当然ですが）最適解を返す保証はありませんが、実用上は大変便利なことが知られています。
+もし s がばらばらな配列要素を指していたらプロファイルは平均的なものになるため、更新されるモチーフ位置はほとんどランダムに決定されます。しかし何らかの正しいモチーフに近いプロファイルが形成された途端、プロファイルは正確にモチーフを選び出すようになって収束します。最適解を返す保証はありませんが、実用上は大変便利なことが知られています。
 ;参考
 <references/>
 ##

@@ Line 112: / Line 112: @@
 L<sup>n</sup> や 4<sup>k</sup> という組み合わせの数は膨大で、全てのパターンをしらみつぶしに計算していると無駄も多そうです。あらかじめ設定した閾値などを用いて無駄な手続きを省略する手法を枝刈り (branch-and-bound) と呼びます。こうした枝刈りでは、残念ながら最悪計算量を下げることはできません。
-====プロファイル行列作りの枝刈り====
+; 例. プロファイル行列作りにおける枝刈り
 長さ k のモチーフと呼べるプロファイルの各ポジションにおけるエントロピーを、k 以下としてみましょう。 各位置のエントロピーが 1 以下であるためには少なくとも半分以上の文字が同一でなくてはなりません。従って、n 本の配列に対して (L - k + 1)<sup>n</sup> 通りの組み合わせを試すときに、途中で残りの文字がどのようになってもエントロピー 1 を達成できないことがわかれば、その時点で次の候補へ移ることができます。
 例えば i 本目の比較で目標のエントロピー基準を達成できないことがわかれば、i + 1 本目以降の (L - k + 1)<sup>n - i</sup> 通りをスキップできます。

@@ Line 112: / Line 112: @@
 L<sup>n</sup> や 4<sup>k</sup> という組み合わせの数は膨大で、全てのパターンをしらみつぶしに計算していると無駄も多そうです。あらかじめ設定した閾値などを用いて無駄な手続きを省略する手法を枝刈り (branch-and-bound) と呼びます。こうした枝刈りでは、残念ながら最悪計算量を下げることはできません。
-===プロファイル行列作りの枝刈り===
+====プロファイル行列作りの枝刈り====
 長さ k のモチーフと呼べるプロファイルの各ポジションにおけるエントロピーを、k 以下としてみましょう。 各位置のエントロピーが 1 以下であるためには少なくとも半分以上の文字が同一でなくてはなりません。従って、n 本の配列に対して (L - k + 1)<sup>n</sup> 通りの組み合わせを試すときに、途中で残りの文字がどのようになってもエントロピー 1 を達成できないことがわかれば、その時点で次の候補へ移ることができます。
 例えば i 本目の比較で目標のエントロピー基準を達成できないことがわかれば、i + 1 本目以降の (L - k + 1)<sup>n - i</sup> 通りをスキップできます。

@@ Line 96: / Line 96: @@
 このスコア関数をハミング距離にしても本質的な問題は変わりません。完全にランダムな場合はハミング距離の総和が最大になり、完全一致の場合はハミング距離の総和が最小になります。
-===モチーフの候補探し===
+===モチーフ候補探しの効率===
 長さ L の DNA 配列が n 本与えられたとき、長さ k のモチーフを選ぶ組み合わせの数は (L - k + 1)<sup>n</sup> になります。それぞれのポジションについてプロファイル行列を kn 時間で作成していると、全体で
@@ Line 107: / Line 107: @@
 こちらも無駄の多いアプローチに見えますが、n が大きかったり k が小さいときには有効なことがわかります。

@@ Line 5: / Line 5: @@
 ===プロファイル行列とコンセンサス===
-固定長 (''l'' とします) の配列を ''n'' 本そろえて ''n'' &times; ''l'' 行列の形に表現し、各列における各塩基配列の出現頻度を記した 4 &times; ''l'' 行列をプロファイルと呼びます。
+固定長 (k とします) の配列を n 本そろえて n &times; k 行列の形に表現し、各列における各塩基配列の出現頻度を記した 4 &times; k 行列をプロファイルと呼びます。
-プロファイルの (''i'', ''j'') 要素 (''i'' &isin; {A,C,G,T}, ''j'' &isin; Z) には、もとの行列で塩基 ''i'' が出現する確率が入ります。
+プロファイルの ( i, j ) 要素 ( i &isin; {A,C,G,T}, j &isin; Z) には、もとの行列で塩基 i が出現する確率が入ります。
 それぞれの位置で代表的な塩基が定まる場合、それをコンセンサス配列と呼びます。
@@ Line 96: / Line 96: @@
 このスコア関数をハミング距離にしても本質的な問題は変わりません。完全にランダムな場合はハミング距離の総和が最大になり、完全一致の場合はハミング距離の総和が最小になります。
-===モチーフの候補数===
+===モチーフの候補探し===
-長さ L の DNA 配列が n 本与えられたとき、長さ ''l'' のモチーフを選ぶ組み合わせの数は (L - k + 1)<sup>n</sup> になります。

@@ Line 79: / Line 79: @@
 ==モチーフ発見問題==
-ここでは長いDNA配列 ''n'' 本と正の整数 ''l'' を与えられたとき、配列それぞれの位置 '''s''' = (s<sub>1</sub>, s<sub>2</sub>, ... s<sub>n</sub>) にから長さ　''l'' の部分配列を取り出してできるプロファイル行列を考えます。
+ここでは長いDNA配列 n 本と正の整数 k を与えられたとき、配列それぞれの位置 '''s''' = (s<sub>1</sub>, s<sub>2</sub>, ... s<sub>n</sub>) にから長さ　k の部分配列を取り出してできるプロファイル行列を考えます。
-: '''問題.''' スコア関数　S('''s''', DNA) = &minus; <Big>&Sigma;<sup>''l''</sup><sub>j</sub> &Sigma;<sub>i</sub><sup>A,T,G,C</sup></big> ''p<sub>i,j</sub>'' log ''p<sub>i,j</sub>'' を最小化する位置の配列 '''s''' を求めよ。
+: '''問題.''' スコア関数　S( '''s''' , DNA) = &minus; <Big>&Sigma;<sup>k</sup><sub>j</sub> &Sigma;<sub>i</sub><sup>A,T,G,C</sup></big> p<sub>i,j</sub> log p<sub>i,j</sub> を最小化する位置の配列 '''s''' を求めよ。
 これをモチーフ発見問題といいます。スコア関数は &minus; <big>&Sigma;&Sigma;</big> p log p の形をとっており、p<sub>ij</sub> はポジション j における塩基 i の確率を表しています。&minus; p log p の総和をプロファイルのエントロピーといいます。
-このエントロピーとは[[Aritalab:Lecture/Basic/Entropy|シャノンの平均情報量]]を意味し、分布の偏りを示す指標です。全ての塩基が等確率で出てくるときに平均情報量は最も大きく、塩基の出現確率に偏りがあればあるほど、平均情報量は小さくなります。このスコア関数をハミング距離にしても本質的な問題は変わりません。
+このエントロピーとは[[Aritalab:Lecture/Basic/Entropy|シャノンの平均情報量]]を意味し、分布の偏りを示す指標です。全ての塩基が等確率で出てくるときに平均情報量は最も大きく、塩基の出現確率に偏りがあればあるほど、平均情報量は小さくなります。
 ===モチーフの候補数===
-長さ L の DNA 配列が n 本与えられたとき、長さ ''l'' のモチーフを選ぶ組み合わせの数は (L - l + 1)<sup>n</sup> になります。
+長さ L の DNA 配列が n 本与えられたとき、長さ ''l'' のモチーフを選ぶ組み合わせの数は (L - k + 1)<sup>n</sup> になります。

@@ Line 4: / Line 4: @@
 モチーフを表現するのに、[[Aritalab:Lecture/Automata/Regular|正則表現]]やプロファイル行列がよく用いられます。
-===プロファイル行列===
+===プロファイル行列とコンセンサス===
 固定長 (''l'' とします) の配列を ''n'' 本そろえて ''n'' &times; ''l'' 行列の形に表現し、各列における各塩基配列の出現頻度を記した 4 &times; ''l'' 行列をプロファイルと呼びます。
 プロファイルの (''i'', ''j'') 要素 (''i'' &isin; {A,C,G,T}, ''j'' &isin; Z) には、もとの行列で塩基 ''i'' が出現する確率が入ります。
 ;例
@@ Line 52: / Line 54: @@
 | &nbsp;<big>&rArr;</big>&nbsp;
 |　style="vertical-align:top"|
-{| class="wikitable"
+{| class="wikitable" style="text-align:center"
 |+ プロファイル行列
 |-
@@ Line 62: / Line 64: @@
 |-
 ! C
-| 0.125 || 0 || 0.125 || 0.5 || 0.250 || 0 || 0.250 || 0.625
+| 0.125 || 0 || 0.125 || 0.5 || 0.250 || 0 || 0.250 || 0.750
 |-
 ! G
@@ Line 69: / Line 71: @@
 ! T
 | 0.125 || 0.750 || 0 || 0 || 0 || 0.250 || 0.750 || 0.250
 |}
 |}