Kemungkinan menemukan urutan pasangan basa tertentu

10

Memikirkan probabilitas selalu membuat saya menyadari betapa buruknya saya dalam menghitung ...

Pertimbangkan urutan huruf dasar , masing-masing sama-sama cenderung muncul. Berapakah probabilitas bahwa urutan ini mengandung urutan tertentu dari pasangan basa dengan minat panjang ?nSEBUAH,T,C, dan Grn

Ada urutan yang berbeda (kemungkinan sama) yang mungkin. Mulailah dengan urutan minat di awal urutan penuh; urutan seperti ini dimungkinkan. Kita dapat memulai urutan minat kami di lokasi yang berbeda. Karenanya, jawaban saya adalah .4n4n-rn+1-r(n+1-r)/4r

Probabilitas ini meningkat dalam , yang masuk akal bagi saya. Tetapi probabilitas ini melebihi 1 ketika . Tapi itu tidak mungkin. Probabilitas harus mendekati 1 dalam batas (menurut saya), tetapi tidak melebihi itu.nn>4r+r1

Saya berasumsi bahwa saya menghitung dua kali sesuatu. Apa yang saya lewatkan? Terima kasih.

(FYI, bukan pekerjaan rumah, hanya contoh mainan dalam persiapan ujian. Sebuah pertanyaan yang diajukan oleh teman ahli biologi molekuler saya.)

Charlie
sumber
Itu benar tentang hal itu tidak boleh melebihi satu karena itu akan melanggar aksioma probabilitas: books.google.com/...
Chris Simokat
1
(Samar-samar) terkait: stats.stackexchange.com/questions/12174/…
kardinal

Jawaban:

5

Mari kita renungkan versi kecil dari masalah ini dengan . Berapa kemungkinan urutan lima huruf akan berisi target ? Ini mudah: dari semua urutan dimulai dengan string ini, berakhir dengan itu, dan tidak ada urutan yang dimulai dan diakhiri dengan string ini. Karenanya kesempatannya adalah .... A C G T 4 - 4 4 - 4 2 × 4 - 4n=5ACGT44442×44

Di sisi lain, apa peluang ? Sekali lagi, dari urutan dimulai dengan string ini, proporsi yang sama berakhir dengan string ini, dan dari semua urutan melakukan keduanya . Oleh karena itu, dengan Prinsip Inklusi-Pengecualian, jawabannya adalah .4 - 4 4 - 5 2 × 4 - 4 - 4 - 5AAAA444-52×4-4-4-5

Secara umum, jawabannya tergantung pada struktur substring. Untuk lebih spesifik, ketika Anda memindai string (dari kiri ke kanan, katakan) untuk , Anda mengabaikan semua karakter sampai Anda melihat awal . Setelah itu, ada tiga kemungkinan: karakter berikutnya adalah kecocokan untuk , yang berikutnya adalah tidak cocok untuk tetapi bukan (jadi Anda kembali dalam status tunggu-untuk-an- ), atau yang berikutnya adalah non-cocok namun itu adalah , menempatkan Anda ke dalam kondisi just-saw-an- . Sebaliknya, pertimbangkan pencarian untuk . Misalkan Anda telah melihat awalanSEBUAHCGTSEBUAHCCSEBUAHSEBUAHSEBUAHSEBUAHSEBUAHCTSEBUAHCGSEBUAHCTSEBUAHC. Karakter berikutnya akan cocok jika . Ketika itu adalah non-pertandingan, (i) menempatkan Anda ke dalam menunggu-untuk-an awal negara, (ii) memiliki Anda menonton keluar untuk , dan (iii) berarti Anda telah melihat dan Anda sudah setengah jalan menuju pertandingan (dan mencari kedua ). "Struktur" yang relevan jelas terdiri dari pola substring di target yang cocok dengan awalan target. Itu sebabnya peluang tergantung pada string target.GCSEBUAHSEBUAHCT...SEBUAHCTSEBUAH

Diagram FSA yang saya anjurkan dalam jawaban at Time diambil untuk memukul pola kepala dan ekor dalam serangkaian lemparan koin dapat membantu memahami fenomena ini.

whuber
sumber
3

Sebuah perkiraan kasar akan menjadi . Anda mengambil probabilitas bahwa urutan Anda tidak terjadi di lokasi tertentu, taruh pada kekuatan jumlah lokasi (anggapan salah independensi), yang n - r + 1 bukan n - r , dan ini merupakan perkiraan dari tidak terjadi sehingga Anda perlu mengurangi ini dari 1 . 1-(1-1/4r)n-r+1n-r+1n-r1

Penghitungan yang tepat akan tergantung pada pola tepat yang Anda cari. lebih mungkin untuk tidak terjadi dari A T C G T .SEBUAHSEBUAHSEBUAHSEBUAHSEBUAHSEBUAHTCGT

Henry
sumber
Mungkin hanya saya, tapi tampaknya sedikit lebih jelas dalam hal memahami bagaimana persamaan dibangun. 1(1(1/4)r)n(r1)
@ JoRocc - Saya curiga ini pribadi. Jika Anda membaca dari halaman hingga halaman 400 buku, pernahkah Anda membaca 400 - 300 + 1 = 101 halaman atau 400 - ( 300 - 1 ) = 101 halaman? 300400400300+1=101400(3001)=101
Henry
Jangan khawatir, saya hanya akan dengan intuisi masalah saya. Jika kita secara intuitif menurunkan persamaan menjadi , maka ketika mencoba menjelaskannya kepada seseorang, saya pikir lebih baik membiarkannya seperti itu daripada menyederhanakannya menjadi a - b + c - 1 + d (meskipun ini tentu saja dapat menjadi lebih intuitif setelah dipertimbangkan). Intuisi Anda mungkin berbeda dalam hal apa pun :)(a(b(c1+d)))ab+c1+d
2

Anda menghitung dua kali urutan yang mencakup beberapa kali target Anda, misalnya di posisi A dan di posisi B! = A. Itu sebabnya probabilitas Anda yang keliru dapat melebihi 1

pengguna145136
sumber
Bagus sekali ! +1
Michael R. Chernick
1

Dimungkinkan untuk memperoleh probabilitas pasti dari urutan tertentu dengan menggunakan representasi rantai Markov dari masalah. Rincian cara membangun rantai bergantung pada urutan minat tertentu, tetapi saya akan memberikan beberapa contoh cara melakukan hal ini.


Probabilitas yang tepat melalui rantai Markov: Pertimbangkan urutan hasil yang terpisah dari A,T,C,G mana hasil dalam urutan tersebut dapat dipertukarkan, dan anggaplah kami tertarik pada beberapa substring panjang k . Untuk setiap nilai yang diberikan dari n , biarkan W menjadi hal substring kepentingan terjadi, dan membiarkan Ha menjadi hal terakhir a hasil adalah yang pertama a<k karakter dalam substring bunga (tetapi tidak lebih dari ini) . Kami menggunakan acara ini untuk memberikan partisi k+1 kemungkinan status minat:

State 0W¯H0,   State 1W¯H1,   State 2W¯H2,   State 3W¯H3,   State k1W¯Hk1,State kW.  

Karena urutan hasil diasumsikan dapat ditukar, kami memiliki hasil independen yang tergantung pada probabilitas masing-masing θA+θT+θC+θG=1 . Proses minat Anda dapat direpresentasikan sebagai rantai Markov waktu diskrit yang dimulai pada State 0 pada n=0 dan transisi sesuai dengan matriks probabilitas yang tergantung pada substring tertentu yang diminati. Matriks transisi akan selalu menjadi (k+1)×(k+1)matriks yang mewakili probabilitas transisi menggunakan status di atas. Jika substring yang menarik belum tercapai, maka setiap transisi dapat membawa Anda selangkah lebih dekat ke substring atau dapat membuat Anda kembali ke keadaan sebelumnya yang bergantung pada substring tertentu. Setelah substring tercapai, ini adalah kondisi penyerap rantai, mewakili fakta bahwa peristiwa menarik telah terjadi.

Misalnya, jika substring minat adalah SEBUAHSEBUAHSEBUAHSEBUAHSEBUAHSEBUAH maka matriks transisi adalah:

P=[1-θSEBUAHθSEBUAH000001-θSEBUAH0θSEBUAH00001-θSEBUAH00θSEBUAH0001-θSEBUAH000θSEBUAH001-θSEBUAH0000θSEBUAH01-θSEBUAH00000θSEBUAH0000001.]

SEBUAHCTSEBUAHGC

P=[1-θSEBUAHθSEBUAH00001-θSEBUAH-θCθSEBUAHθC00001-θSEBUAH-θTθSEBUAH0θT0001-θSEBUAH000θSEBUAH001-θSEBUAH-θC-θGθSEBUAHθC00θG01-θSEBUAH-θCθSEBUAH0000θC0000001.]

nP(W|n)={Pn}0,kn<k


Rn

#Create function to give n-step transition matrix for n = 1...N
#We will use the example of the substring of interest "AAAAAA"

#a is the probability of A
#t is the probability of T
#c is the probability of C
#g is the probability of G
#N is the last value of n
PROB <- function(N,a,t,c,g) { TOT <- a+t+c+g;
                              a <- a/TOT; 
                              t <- t/TOT; 
                              c <- c/TOT; 
                              g <- g/TOT; 

                              P <- matrix(c(1-a, a, 0, 0, 0, 0, 0,
                                            1-a, 0, a, 0, 0, 0, 0,
                                            1-a, 0, 0, a, 0, 0, 0,
                                            1-a, 0, 0, 0, a, 0, 0,
                                            1-a, 0, 0, 0, 0, a, 0,
                                            1-a, 0, 0, 0, 0, 0, a,
                                              0, 0, 0, 0, 0, 0, 1),
                                          nrow = 7, ncol = 7, 
                                          byrow = TRUE);
                              PPP <- array(0, dim = c(7,7,N));
                              PPP[,,1] <- P;
                              for (n in 2:N) { PPP[,,n] <- PPP[,,n-1] %*% P; } 
                              PPP }

#Calculate probability for N = 100 for equiprobable outcomes
N <- 100;
a <- 1/4;
t <- 1/4;
c <- 1/4;
g <- 1/4;
PROB(N,a,t,c,g)[1,7,N];

[1] 0.01732435

SEBUAHSEBUAHSEBUAHSEBUAHSEBUAHSEBUAHn=1000,01732435

Ben - Pasang kembali Monica
sumber