Prawdopodobieństwo znalezienia określonej sekwencji par zasad

10

Myślenie o prawdopodobieństwie zawsze uświadamia mi, jak źle liczę ...

Rozważ ciąg podstawowych liter , z których każde może pojawić się w jednakowym stopniu. Jakie jest prawdopodobieństwo, że ta sekwencja zawiera określoną sekwencję interesujących par zasad o długości ? $n$ $A,\; T, \; C, \text{ and } G$ $r\leq n$

Możliwe są różne sekwencje (równie prawdopodobne). Rozpocznij od interesującej sekwencji na początku pełnej sekwencji; Możliwe są takie sekwencje . Możemy rozpocząć naszą sekwencję zainteresowania w różnych lokalizacjach. Dlatego moja odpowiedź brzmi . $4^n$ $4^{n-r}$ $n+1 -r$ $(n+1-r)/4^r$

To prawdopodobieństwo rośnie , który ma sens dla mnie. Ale prawdopodobieństwo to przekracza 1, gdy . Ale tak nie może być. Prawdopodobieństwo powinno zbliżyć się do 1 (wydaje mi się), ale nie może go przekroczyć. $n$ $n>4^r +r-1$

Zakładam, że podwójnie coś liczę. czego mi brakuje? Dzięki.

(FYI, nie praca domowa, tylko przykład zabawki w ramach przygotowań do egzaminów. Pytanie zadane przez mojego przyjaciela biologa molekularnego.)

probability combinatorics

— Charlie
źródło

Zgadza się, nie powinno przekraczać jednego, ponieważ naruszałoby to aksjomaty prawdopodobieństwa: books.google.com/…

— Chris Simokat

1

(Niejednoznacznie) powiązane: stats.stackexchange.com/questions/12174/…

— kard.

5

Rozważmy małą wersję tego problemu z . Jaka jest szansa, że sekwencja pięciu liter będzie zawierać cel ? To proste: wszystkich sekwencji zaczyna się od tego łańcucha, kolejne kończą się nim, a żadna sekwencja nie zaczyna się i kończy z tym łańcuchem. Dlatego szansa wynosi . $n=5$ $\ldots A C G T\ldots$ $4^{-4}$ $4^{-4}$ $2 \times 4^{-4}$

Z drugiej strony, jaka jest szansa na ? Ponownie sekwencji zaczyna się od tego łańcucha, ta sama proporcja kończy się tym łańcuchem, a wszystkich sekwencji robi obie te rzeczy . Dlatego zgodnie z zasadą włączenia-wykluczenia odpowiedź brzmi . $\ldots A A A A \ldots$ $4^{-4}$ $4^{-5}$ $2 \times 4^{-4} - 4^{-5}$

Zasadniczo odpowiedź zależy od struktury podłańcucha. Aby być bardziej konkretne, kiedy skanowanie ciąg (od lewej do prawej, powiedzmy) dla , zignorować wszystkie znaki aż zobaczysz, że wstępna . Po tym są trzy możliwości: następny znak jest dopasowany do , następny nie pasuje do ale nie jest (więc wrócisz do stanu oczekiwania na ), lub następny jest niepasujący, ale jest to , co wprowadza cię w stan just-saw- an - . Dla kontrastu rozważ wyszukiwanie . Załóżmy, że widziałeś prefiks $ACGT$ $A$ $C$ $C$ $A$ $A$ $A$ $A$ $ACTACG$ $ACTAC$ . Następny znak będzie pasował jeśli jest . Kiedy to nie mecz, (i) daje do początkowego wait-for-an stanie, (ii) ma się oglądając się na , oraz (iii) oznacza, że już widzieliśmy i już jesteś w połowie meczu (i szukasz drugiego ). Odpowiednia „struktura” ewidentnie składa się ze wzorów podciągów w celu, które pasują do przedrostka celu. Dlatego szanse zależą od ciągu docelowego. $G$ $C$ $A$ $A$ $C$ $T$ $\ldots ACT$ $A$

Diagramy FSA, które zalecam w odpowiedzi w czasie podjętym w celu uderzenia w wzór głów i ogonów w serii rzutów monetą, mogą pomóc w zrozumieniu tego zjawiska.

— Whuber
źródło

3

Przybliżone przybliżenie byłoby . Przyjmujesz prawdopodobieństwo, że twoja sekwencja nie występuje w określonej lokalizacji, przypisujesz jej potęgę liczby lokalizacji (fałszywie zakładając niezależność), która jest nie , i jest to przybliżenie jej braku. więc musisz odjąć to od . $1-(1-1/4^r)^{n-r+1}$ $n-r+1$ $n-r$ $1$

Dokładne obliczenia będą zależeć od dokładnego wzoru, którego szukasz. częściej nie występuje niż . $AAAAA$ $ATCGT$

— Henz
źródło

Może to tylko ja, ale wydaje się nieco jaśniejsze, jeśli chodzi o zrozumienie, jak zbudowano równanie.

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

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

@JoeRocc - Podejrzewam, że to sprawa osobista. Jeśli czytasz od strony do strony książki, czy przeczytałeś stron lub stron?

300

$300$

400

$400$

400 - 300 + 1 = 101

$400-300+1=101$

400 - (300 - 1) = 101

$400-(300-1)=101$

— Henry

Nie martw się, kierowałem się wyłącznie intuicją dotyczącą problemu. Jeśli intuicyjnie wyprowadzimy równanie na , wtedy próbując wyjaśnić to komuś, myślę, że lepiej zostawić to jako takie, a nie uprościć to do (choć z pewnością może się to okazać bardziej intuicyjne po rozważeniu). Twoja intuicja może być inna :)

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

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

a - b + c - 1 + d

$a-b+c-1+d$

2

Podwójnie zliczasz sekwencje, które zawierają kilkakrotnie docelową podsekwencję, na przykład zarówno w pozycji A, jak i w pozycji B! = A. Dlatego twoje błędne prawdopodobieństwo może przekroczyć 1

— użytkownik145136
źródło

Bardzo dobrze zrobione ! +1

— Michael R. Chernick

1

Możliwe jest uzyskanie dokładnego prawdopodobieństwa określonego podsekwencji za pomocą reprezentacji problemu przez łańcuch Markowa. Specyfika tego, jak skonstruować łańcuch, zależy od konkretnego podsekwencji zainteresowania, ale podam kilka przykładów, jak to zrobić.

$A,T,C,G$ $k$ $n$ $\mathscr{W}$ $\mathscr{H}_a$ $a$ $a < k$ $k+1$

\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}$

Ponieważ zakłada się, że sekwencja wyników jest wymienna, mamy wyniki niezależne od ich prawdopodobieństw . Twój interesujący proces może być reprezentowany jako dyskretne łańcuchy Markowa, które zaczynają się w przy i przechodzą zgodnie z macierzą prawdopodobieństwa, która zależy od konkretnego podciągu będącego przedmiotem zainteresowania. Macierz przejścia będzie zawsze a $\theta_A + \theta_T + \theta_C + \theta_G = 1$ $\text{State 0}$ $n=0$ $(k+1) \times (k+1)$ macierz reprezentująca prawdopodobieństwa przejścia przy użyciu powyższych stanów. Jeśli podciąg nie jest osiągnięty, każde przejście może przybliżyć cię o jeden krok do podciągu lub może przywrócić poprzedni stan, który zależy od konkretnego podciągu. Po osiągnięciu podciągu jest to stan pochłaniający łańcucha, reprezentujący fakt, że wystąpiło interesujące zdarzenie.

Na przykład, jeśli podciągiem będącym przedmiotem zainteresowania jest wówczas macierz przejścia to: $AAAAAA$

P = [\begin{matrix} 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. \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}$

Przeciwnie, jeśli podciągu przedmiotem zainteresowania jest wówczas macierz przejścia to: $ACTAGC$

P = [\begin{matrix} 1 - θ_{A} & θ_{A} & 0 & 0 & 0 & 0 \\ 1 - θ_{A} - θ_{C} & θ_{A} & θ_{C} & 0 & 0 & 0 & 0 \\ 1 - θ_{A} - θ_{T} & θ_{A} & 0 & θ_{T} & 0 & 0 & 0 \\ 1 - θ_{A} & 0 & 0 & 0 & θ_{A} & 0 & 0 \\ 1 - θ_{A} - θ_{C} - θ_{G} & θ_{A} & θ_{C} & 0 & 0 & θ_{G} & 0 \\ 1 - θ_{A} - θ_{C} & θ_{A} & 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}$

Jak można zobaczyć powyżej, konstruowanie macierzy przejściowej wymaga zwrócenia uwagi na określony substrat. Niepoprawny wynik powoduje powrót do poprzedniego stanu w ciągu, który zależy od konkretnego interesującego cię podciągu. Po zbudowaniu macierzy przejścia, dla danej wartości prawdopodobieństwo wystąpienia podłańcucha w łańcuchu wynosi . (To prawdopodobieństwo wynosi zero dla wszystkich .) $n$ $\mathbb{P}(\mathscr{W} | n) = \{ \mathbf{P}^n \}_{0,k}$ $n<k$

Programowanie w R: Możesz zaprogramować to jako funkcję w R, tworząc funkcję, która generuje macierz przejścia dla łańcucha Markowa i tablicę jego mocy do pewnej pożądanej liczby prób. Następnie można odczytać odpowiednie prawdopodobieństwo przejścia dla wartości która jest przedmiotem zainteresowania. Oto przykład takiego kodu: $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

Jak widać z tego obliczenia, prawdopodobieństwo otrzymania podłańcucha w wynikami wynosi . To tylko jeden przykład z zastosowaniem określonego podłańcucha i danej liczby prób, ale można go zmieniać, aby uzyskać prawdopodobieństwa w odniesieniu do innych interesujących podłańcuchów. $AAAAAA$ $n=100$ $0.01732435$

— Ben - Przywróć Monikę
źródło