Probabilidade de encontrar uma sequência específica de pares de bases

10

Pensar em probabilidade sempre me faz perceber o quão ruim sou em contar ...

Considere uma sequência de letras base , cada um com a mesma probabilidade de aparecer. Qual é a probabilidade de que essa sequência contenha uma sequência específica de pares de bases de interesse de comprimento ? $n$ $A,\; T, \; C, \text{ and } G$ $r\leq n$

Existem sequências diferentes (igualmente prováveis) possíveis. Comece com a sequência de interesse no início da sequência completa; seqüências como essa são possíveis. Podemos iniciar nossa sequência de interesse em locais diferentes. Portanto, minha resposta é . $4^n$ $4^{n-r}$ $n+1 -r$ $(n+1-r)/4^r$

Essa probabilidade está aumentando em , o que faz sentido para mim. Mas essa probabilidade excede 1 quando . Mas isso não pode ser. A probabilidade deve se aproximar de 1 no limite (me parece), mas não exceder. $n$ $n>4^r +r-1$

Suponho que estou contando algo duas vezes. o que estou perdendo? Obrigado.

(FYI, não lição de casa, apenas um exemplo de brinquedo em preparação para os exames. Uma pergunta feita pelo meu amigo biólogo molecular.)

probability combinatorics Charlie
fonte

Isso é correto sobre isso não deve exceder uma vez que isso violaria os axiomas de probabilidade: books.google.com/...

Chris Simokat

11

(Vagamente) relacionado: stats.stackexchange.com/questions/12174/…

cardinal

5

Vamos contemplar uma versão pequena desse problema com . Qual é a chance de uma sequência de cinco letras conter os destino ? Isso é fácil: de todas as seqüências começam com essa sequência, outros terminam com ela e nenhuma sequência começa e termina com essa sequência. Portanto, a chance é . $n=5$ $\ldots A C G T\ldots$ $4^{-4}$ $4^{-4}$ $2 \times 4^{-4}$

Por outro lado, qual é a chance de ? Mais uma vez, das seqüências começam com essa sequência, a mesma proporção termina com essa sequência e de todas as sequências fazem as duas coisas . Portanto, pelo Princípio da Inclusão-Exclusão, a resposta é . $\ldots A A A A \ldots$ $4^{-4}$ $4^{-5}$ $2 \times 4^{-4} - 4^{-5}$

Em geral, a resposta depende da estrutura da substring. Para ser mais específico, ao digitalizar uma string (da esquerda para a direita, digamos) em busca do , você ignora todos os caracteres até ver o inicial . Depois disso, existem três possibilidades: o próximo caractere corresponde a , o próximo não corresponde a mas não é (portanto, você está de volta no estado de espera por ) ou o próximo não combina, mas é um , colocando você no estado just-saw-an- . Por outro lado, considere uma pesquisa por . Suponha que você tenha visto o prefixo $ACGT$ $A$ $C$ $C$ $A$ $A$ $A$ $A$ $ACTACG$ $ACTAC$ . O próximo personagem vai corresponder se for . Quando não é compatível, (i) um coloca você no estado inicial de espera por um , (ii) um faz você ficar de olho em um e (iii) um significa que você já viu e você já está no meio de uma partida (e está procurando o segundo ). A "estrutura" relevante consiste evidentemente em padrões de substrings no alvo que correspondem ao prefixo do alvo. É por isso que as chances dependem da sequência de destino. $G$ $C$ $A$ $A$ $C$ $T$ $\ldots ACT$ $A$

Os diagramas da FSA que defendo em uma resposta na Time tomadas para atingir um padrão de cara e coroa em uma série de lançamentos de moedas podem ajudar a entender esse fenômeno.

whuber
fonte

3

Uma aproximação bruta seria . Você assume a probabilidade de que sua sequência não ocorra em um local específico, coloca-o no poder do número de locais (assumindo independência falsamente), que é não , e essa é uma aproximação de sua ocorrência. então você precisa subtrair isso de . $1-(1-1/4^r)^{n-r+1}$ $n-r+1$ $n-r$ $1$

Um cálculo preciso dependerá do padrão preciso que você está procurando. É mais provável que não ocorra que . $AAAAA$ $ATCGT$

Henry
fonte

Talvez seja só eu, mas parece um pouco mais claro em termos de compreensão de como a equação foi construída.

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

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

@JoeRocc - Eu suspeito que isso seja pessoal. Se você leu da página à página de um livro, leu páginas ou páginas?

300

$300$

400

$400$

400 - 300 + 1 = 101

$400-300+1=101$

400 - (300 - 1) = 101

$400-(300-1)=101$

Henry

Não se preocupe, eu estava passando pela minha intuição do problema. Se derivarmos intuitivamente uma equação para ser , então, ao tentar explicá-la a alguém, acho melhor deixá-la assim, em vez de simplificá-la para (embora isso certamente se mostre mais intuitivo quando considerado). Sua intuição pode ter sido diferente, em qualquer caso :)

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

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

a - b + c - 1 + d

$a-b+c-1+d$

2

Você está contando duas vezes as seqüências que incluem várias vezes a subsequência de destino, por exemplo, tanto na posição A quanto na posição B! = A. É por isso que sua probabilidade de erro pode exceder 1

user145136
fonte

Muito bem feito ! 1

Michael R. Chernick

1

É possível obter a probabilidade exata de uma subsequência específica usando uma representação em cadeia de Markov do problema. As especificidades de como construir a cadeia dependem da subsequência de interesse específica, mas darei alguns exemplos de como fazer isso.

Probabilidade exata via cadeia de Markov: considere uma sequência discreta de resultados de $A,T,C,G$ que os resultados na sequência sejam permutáveis e suponha que estamos interessados em alguma substring de comprimento $k$ . Para qualquer dado valor de $n$ , deixar $\mathscr{W}$ ser o caso em que a subsequência de interesse ocorre, e deixá- $\mathscr{H}_a$ ser o caso em que os últimos $a$ resultados são o primeiro $a < k$ caracteres na subsequência de interesse (mas não mais do que isto) . Usamos esses eventos para fornecer a seguinte partição de $k+1$ possíveis estados de interesse:

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

$\theta_A + \theta_T + \theta_C + \theta_G = 1$ $\text{State 0}$ $n=0$ $(k+1) \times (k+1)$ matriz que representa as probabilidades de transição usando os estados acima. Se a substring de interesse não tiver sido alcançada, cada transição poderá aproximá-lo um pouco da substring ou retornar a um estado anterior que depende da substring específica. Uma vez atingida a substring, esse é um estado absorvente da cadeia, representando o fato de que o evento de interesse ocorreu.

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

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

$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 - Restabelecer Monica
fonte

Probabilidade de encontrar uma sequência específica de pares de bases

Respostas: