特定の配列がいくつ現れるか（期待値の計算）

質問

DNAの話なのですが、4つの異なる文字が3×10^9個の1次元配列にランダムに納まっているとします。どの文字も同様に確からしく出現するとして、ある特定の10文字の配列と同じ10文字の配列が、この3×10^9個の配列の中に何ヶ所出現するかを求めたいのです。

１ヶ所も現れない確率、1ヶ所だけ現れる確率、2ヶ所現れる確率…、と求めて行き、最後に期待値を出そうと考えています。確率の漸化式を立てて一般項P(n)を求めてからn=0～3×10^9までΣnP(n)を計算するという方針ですが、式が立てられず悩んでいます。

数字が大きいので端のことなどはあまり気にしなくても良いのですが、ものすごく複雑になりそうに思います。それとも簡単な方法があるのでしょうか。

回答No.4

rabbit_cat · ベストアンサー

すいません。肝心の漸化式が全然、間違ってますね。
K(n) = Σ_{j=10→19} P*{K(n-j)+1} + (1-P)*K(n-j)
です。

お礼

回答ありがとうございます。
これは２０項間漸化式になるということでしょうか。自分は３項間までしか解いたことがありません。

回答No.3

rabbit_cat

出現回数ではなくて、文字列の長さで漸化式をたてたほうがいいと思う。

＞特定の10文字の配列は
＞5'GGCCACAGCG3'
＞です。
この場合は、重なって出現することはないんで簡単です。

長さnの文字列にこの１０文字が平均K(n)回出現するとすると、長さnの文字列の先頭部分に、この10文字が現れるかどうかに注目すれば、
P = (1/4)^10
として、
K(n) = P*K(n-10) + P*K(n-11) + … + P*K(n-19)
と書けます。
あとは、K(1)～K(19)を地道に求めればよい。

お礼

そうですね。5'GGCCACAGCG3'では重なることはありませんね。一般の場合ばかり考えていて気づきませんでした。
文字列の長さで漸化式を立てるという考え方もあったのですね。
ありがとうございます。

回答No.2

murakkusu

あまり自信はありませんが・・・

10個の1次配列に、ATGCの組が何個あるかについて考えてみました。

【第1ステップ】

まず、ATCGが1つだけある場合を考えると、

ATCG○○○○○○　　　・・・(1)
○ATCG○○○○○　　　・・・(2)　　　
○○ATCG○○○○　　　・・・(3)
○○○ATCG○○○　　　・・・(4)
○○○○ATCG○○　　　・・・(5)
○○○○○ATCG○　　　・・・(6)
○○○○○○ATCG　　　・・・(7)

という風に、7通り(10-4+1通り)

【第2ステップ】

他の○のところに、ランダムに他の4つが入るとしたら、それぞれの○に4通りある。○が6個あるから、4^6になる。

んで、

7×4^6

【第3ステップ】

ここから、○6個の中に、ATGCが出てきてしまう場合を引く必要がある。

ATGCの左と右にそれぞれいくつできるかを考える。さっき、7通り考えたように数える。負の数が出たら存在しないとする。

(1)の場合、　左:0-4+1=無 　右:6-4+1=3
(2)の場合、　左:1-4+1=無 　右:5-4+1=2
(3)の場合、　左:2-4+1=無 　右:4-4+1=1
(4)の場合、　左:3-4+1=0 　 右:3-4+1=0
(5)の場合、　左:4-4+1=1 　 右:2-4+1=無
(6)の場合、　左:5-4+1=2 　 右:1-4+1=無
(7)の場合、　左:6-4+1=3　 右:0-4+1=無

合計　12個

よって、10個の配列にATGCが一つある場合の数は

7×4^6-12　となる。

これを、拡張すればできそう・・・

n個の配列にm個の組が1つある場合を考える。

【第1ステップ】
n-m+1
【第2ステップ】
n-m個にATGCを入れる
4^(n-m)
【第3ステップ】
1　 右:0-m+1　　 左:(n-m)-m+1
2　 右:1-m+1　　 左:(n-m-1)-m+1
3　 右:2-m+1　　 左:(n-m-2)-m+1
・・・
x 右:x-1-m+1 　　左:(n-m-(x-1))-m+1
　　　 ・・・
n-m-1　右:(n-m-2)-m+1　左:3-m+1
n-m　 右:(n-m-1)-m+1　左:2-m+1
n-m+1　右:(n-m)-m+1　　左:1-m+1

何番目まで有効か？
左について考えると、

(n-m-(x-1))-m+1=0

になる所まで

x=n-2m+2　番目まで

それらの合計は、初項0、公差1の等差数列のx項までの和になるので、

Σ(k=1～x)k=1/2x(x+1)

右も考えると、

x(x+1)　通りになる

以上より、1組だけある場合の場合の数は

(n-m+1)×[4^(n-m)}－x(x＋1)　通り

となりそうだ。

考え方、あってるかわからない。計算ミスもしてるかもしれない。

2組以上ある場合は、同様に考えれる？
やってないからわかりません。
多分、考えれると思います。

お礼

詳しく回答していただいてありがとうございます。特定の配列のある場所が一ヶ所のときの場合が求まっても、一般にｎヶ所のときの確率が求まらないと期待値が求められないのです。
でもこの考え方は参考にさせていただきます。ありがとうございます。

回答No.1

murakkusu

答えではないです。

例えば、４つの異なる文字(A,T,G,C)が”５”の1次元配列にランダムに納まってる問題にして。

2文字の配列が、何個できるかを考えたとき。

AAAAA

という、5つの1次元配列なら、何個できてると考えるのですか?

考えようによっては、2つ　4つ　となってしまう。

もしくは

AAAGT

とかだったら？

これが、わかっても解ける自信はありませんが、一応。

お礼

おはようございます。回答ありがとうございます。
条件が漏れてしまい申し訳ありませんでした。
特定の配列が、DNAのある場所で2つ以上重なった形で存在したときは重なったものはカウントしません。
たとえば
AAAAA
という5文字の配列に
AA
という二文字の特定の配列は２つ存在すると考えます。

特定の10文字の配列は
5'GGCCACAGCG3'
です。