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 ?A ,nr nA,T,C, and Grn

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 - r n + 1 - r ( n + 1 - r ) / 4 r4n4nrn+1r(n+1r)/4r

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 > 4 r + r - 1nn>4r+r1

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

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

Respostas:

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 é .A C G T 4 - 4 4 - 4 2 × 4 - 4n=5ACGT44442×44

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 é .4 - 4 4 - 5 2 × 4 - 4 - 4 - 5AAAA44452×4445

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 prefixoA C C A A A A A C T A C G A C T A C G C A A C T A C T AACGTACCAAAAACTACGACTAC. 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.GCAACTACTA

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 . n - r + 1 n - r 11(11/4r)nr+1nr+1nr1

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

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(r1)
@JoeRocc - Eu suspeito que isso seja pessoal. Se você leu da página à página de um livro, leu páginas ou páginas? 400 400 - 300 + 1 = 101 400 - ( 300 - 1 ) = 101300400400300+1=101400(3001)=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(c1+d)))ab+c1+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 W ser o caso em que a subsequência de interesse ocorre, e deixá- Ha 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:

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

θA+θT+θC+θG=1State 0n=0(k+1)×(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=[1θAθA000001θA0θA00001θA00θA0001θA000θA001θA0000θA01θA00000θA0000001.]

ACTAGC

P=[1θAθA00001θAθCθAθC00001θAθTθA0θT0001θA000θA001θAθCθGθAθC00θG01θAθCθA0000θ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

AAAAAAn=1000.01732435

Ben - Restabelecer Monica
fonte