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 ? $n$ $A,\; T, \; C, \text{ and } G$ $r\leq n$

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 . $4^n$ $4^{n-r}$ $n+1 -r$ $(n+1-r)/4^r$

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. $n$ $n>4^r +r-1$

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.)

probability combinatorics 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

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 . $n=5$ $\ldots A C G T\ldots$ $4^{-4}$ $4^{-4}$ $2 \times 4^{-4}$

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 . $\ldots A A A A \ldots$ $4^{-4}$ $4^{-5}$ $2 \times 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 awalan $ACGT$ $A$ $C$ $C$ $A$ $A$ $A$ $A$ $ACTACG$ $ACTAC$ . 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. $G$ $C$ $A$ $A$ $C$ $T$ $\ldots ACT$ $A$

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 bukan , dan ini merupakan perkiraan dari tidak terjadi sehingga Anda perlu mengurangi ini dari . $1-(1-1/4^r)^{n-r+1}$ $n-r+1$ $n-r$ $1$

Penghitungan yang tepat akan tergantung pada pola tepat yang Anda cari. lebih mungkin untuk tidak terjadi dari . $AAAAA$ $ATCGT$

Henry
sumber

Mungkin hanya saya, tapi

tampaknya sedikit lebih jelas dalam hal memahami bagaimana persamaan dibangun.

1 - (1 - (1 / 4)^{r})^{n - (r - 1)}

$1-(1-(1/4)^r)^{n-(r-1)}$

@ JoRocc - Saya curiga ini pribadi. Jika Anda membaca dari halaman

hingga halaman

buku, pernahkah Anda membaca

halaman atau

halaman?

300

$300$

400

$400$

400 - 300 + 1 = 101

$400-300+1=101$

400 - (300 - 1) = 101

$400-(300-1)=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

(meskipun ini tentu saja dapat menjadi lebih intuitif setelah dipertimbangkan). Intuisi Anda mungkin berbeda dalam hal apa pun :)

(a - (b - (c - 1 + d)))

$(a-(b-(c-1+d)))$

a - b + c - 1 + d

$a-b+c-1+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 $\mathscr{W}$ menjadi hal substring kepentingan terjadi, dan membiarkan $\mathscr{H}_a$ 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:

\begin{matrix} State 0 & \bar{W} \cap H_{0}, \\ State 1 & \bar{W} \cap H_{1}, \\ State 2 & \bar{W} \cap H_{2}, \\ State 3 & \bar{W} \cap H_{3}, \\ ⋮ & ⋮ \\ State k - 1 & \bar{W} \cap H_{k - 1}, \\ State k & W . \end{matrix}

$\begin{matrix} \text{State 0} & & & \bar{\mathscr{W}} \cap \mathscr{H_0}, \text{ } \text{ } \text{ } \\[6pt] \text{State 1} & & & \bar{\mathscr{W}} \cap \mathscr{H_1}, \text{ } \text{ } \text{ } \\[6pt] \text{State 2} & & & \bar{\mathscr{W}} \cap \mathscr{H_2}, \text{ } \text{ } \text{ } \\[6pt] \text{State 3} & & & \bar{\mathscr{W}} \cap \mathscr{H_3}, \text{ } \text{ } \text{ } \\[6pt] \vdots & & & \vdots \\[6pt] \text{State }k-1 & & & \bar{\mathscr{W}} \cap \mathscr{H_{k-1}}, \\[6pt] \text{State }k & & & \mathscr{W}. \quad \quad \quad \text{ } \text{ } \\[6pt] \\[6pt] \end{matrix}$

Karena urutan hasil diasumsikan dapat ditukar, kami memiliki hasil independen yang tergantung pada probabilitas masing-masing $\theta_A + \theta_T + \theta_C + \theta_G = 1$ . Proses minat Anda dapat direpresentasikan sebagai rantai Markov waktu diskrit yang dimulai pada $\text{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) \times (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 $AAAAAA$ maka matriks transisi adalah:

P = [\begin{matrix} 1 - θ_{SEBUAH} & θ_{SEBUAH} & 0 & 0 & 0 & 0 & 0 \\ 1 - θ_{SEBUAH} & 0 & θ_{SEBUAH} & 0 & 0 & 0 & 0 \\ 1 - θ_{SEBUAH} & 0 & 0 & θ_{SEBUAH} & 0 & 0 & 0 \\ 1 - θ_{SEBUAH} & 0 & 0 & 0 & θ_{SEBUAH} & 0 & 0 \\ 1 - θ_{SEBUAH} & 0 & 0 & 0 & 0 & θ_{SEBUAH} & 0 \\ 1 - θ_{SEBUAH} & 0 & 0 & 0 & 0 & 0 & θ_{SEBUAH} \\ 0 & 0 & 0 & 0 & 0 & 0 & 1. \end{matrix}]

$\mathbf{P} = \begin{bmatrix} 1-\theta_A & \theta_A & 0 & 0 & 0 & 0 & 0 \\[6pt] 1-\theta_A & 0 & \theta_A & 0 & 0 & 0 & 0 \\[6pt] 1-\theta_A & 0 & 0 & \theta_A & 0 & 0 & 0 \\[6pt] 1-\theta_A & 0 & 0 & 0 & \theta_A & 0 & 0 \\[6pt] 1-\theta_A & 0 & 0 & 0 & 0 & \theta_A & 0 \\[6pt] 1-\theta_A & 0 & 0 & 0 & 0 & 0 & \theta_A \\[6pt] 0 & 0 & 0 & 0 & 0 & 0 & 1. \\[6pt] \end{bmatrix}$

$ACTAGC$

P = [\begin{matrix} 1 - θ_{SEBUAH} & θ_{SEBUAH} & 0 & 0 & 0 & 0 \\ 1 - θ_{SEBUAH} - θ_{C} & θ_{SEBUAH} & θ_{C} & 0 & 0 & 0 & 0 \\ 1 - θ_{SEBUAH} - θ_{T} & θ_{SEBUAH} & 0 & θ_{T} & 0 & 0 & 0 \\ 1 - θ_{SEBUAH} & 0 & 0 & 0 & θ_{SEBUAH} & 0 & 0 \\ 1 - θ_{SEBUAH} - θ_{C} - θ_{G} & θ_{SEBUAH} & θ_{C} & 0 & 0 & θ_{G} & 0 \\ 1 - θ_{SEBUAH} - θ_{C} & θ_{SEBUAH} & 0 & 0 & 0 & 0 & θ_{C} \\ 0 & 0 & 0 & 0 & 0 & 0 & 1. \end{matrix}]

$\mathbf{P} = \begin{bmatrix} 1-\theta_A & \theta_A & 0 & 0 & 0 & 0 \\[6pt] 1-\theta_A-\theta_C & \theta_A & \theta_C & 0 & 0 & 0 & 0 \\[6pt] 1-\theta_A-\theta_T & \theta_A & 0 & \theta_T & 0 & 0 & 0 \\[6pt] 1-\theta_A & 0 & 0 & 0 & \theta_A & 0 & 0 \\[6pt] 1-\theta_A-\theta_C-\theta_G & \theta_A & \theta_C & 0 & 0 & \theta_G & 0 \\[6pt] 1-\theta_A-\theta_C & \theta_A & 0 & 0 & 0 & 0 & \theta_C \\[6pt] 0 & 0 & 0 & 0 & 0 & 0 & 1. \\[6pt] \end{bmatrix}$

$n$ $\mathbb{P}(\mathscr{W} | n) = \{ \mathbf{P}^n \}_{0,k}$ $n<k$

R $n$

#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

$AAAAAA$ $n=100$ $0.01732435$

Ben - Pasang kembali Monica
sumber

Kemungkinan menemukan urutan pasangan basa tertentu

Jawaban: