Aritalab:Lecture/Bioinformatics/MotifFinding

Revision as of 10:38, 7 November 2011

モチーフ

DNA配列の中で転写制御部位や生体分子の結合部位など、決まったパターンを持つ部分配列をモチーフと呼びます。 決まったパターンといっても全く同じ部分配列が存在することは稀で、多くは「ほとんど」一致する部分配列となります。 モチーフを表現するのに、正則表現やプロファイル行列がよく用いられます。

プロファイル行列とコンセンサス

固定長 (l とします) の配列を n 本そろえて n × l 行列の形に表現し、各列における各塩基配列の出現頻度を記した 4 × l 行列をプロファイルと呼びます。 プロファイルの (i, j) 要素 (i ∈ {A,C,G,T}, j ∈ Z) には、もとの行列で塩基 i が出現する確率が入ります。

それぞれの位置で代表的な塩基が定まる場合、それをコンセンサス配列と呼びます。

例

モチーフ発見問題

ここでは長いDNA配列 n 本と正の整数 k を与えられたとき、配列それぞれの位置 s = (s₁, s₂, ... s_n) にから長さ　k の部分配列を取り出してできるプロファイル行列を考えます。

問題. スコア関数　S( s , DNA) = − Σ^k_j Σ_i^A,T,G,C p_i,j log p_i,j を最小化する位置の配列 s を求めよ。

これをモチーフ発見問題といいます。スコア関数は − ΣΣ p log p の形をとっており、p_ij はポジション j における塩基 i の確率を表しています。− p log p の総和をプロファイルのエントロピーといいます。 このエントロピーとはシャノンの平均情報量を意味し、分布の偏りを示す指標です。全ての塩基が等確率で出てくるときに平均情報量は最も大きく、塩基の出現確率に偏りがあればあるほど、平均情報量は小さくなります。

• 完全にランダムな場合 （情報量は大きい）

− Σ^kΣ^ACGT p log p = − 4 k * { (1/4) * (−2)} = 2 k

k ビットの情報源が持ちうるエントロピーの最大値は k です。DNAは4文字あるために各位置が 2 ビットの情報を持ち得て 2k になります。もし4文字のうち2文字だけが50%ずつ利用される場合、情報量は k になります。

• 完全に一致する場合（情報量は小さい）

− Σ^kΣ^ACGT p log p = − k * { log 1 } = 0

完全一致の場合、情報量は 0 になります。

このスコア関数をハミング距離にしても本質的な問題は変わりません。完全にランダムな場合はハミング距離の総和が最大になり、完全一致の場合はハミング距離の総和が最小になります。

モチーフの候補数

長さ L の DNA 配列が n 本与えられたとき、長さ l のモチーフを選ぶ組み合わせの数は (L - k + 1)ⁿ になります。