Probability of finding a particular sequence of base pairs

Question

Thinking about probability always makes me realize how bad I am at counting...

Consider a sequence of $n$ base letters $A,\; T, \; C, \text{ and } G$, each equally likely to appear. What is the probability that this sequence contains a particular sequence of base pairs of interest of length $r\leq n$?

There are $4^n$ different (equally likely) sequences possible. Start with the sequence of interest at the beginning of the full sequence; $4^{n-r}$ sequences like this are possible. We can start our sequence of interest in $n+1 -r$ different locations. Hence, my answer is $(n+1-r)/4^r$.

This probability is increasing in $n$, which makes sense to me. But this probability exceeds 1 when $n>4^r +r-1$. But that can't be. The probability should approach 1 in the limit (seems to me), but not exceed it.

I assume that I'm double counting something. What am I missing? Thanks.

(FYI, not homework, just a toy example in preparation for exams. A question posed by my molecular biologist friend.)

Answer 1

Let's contemplate a small version of this problem with $n=5$. What is the chance a sequence of five letters will contain the target $\ldots A C G T\ldots$? This is easy: $4^{-4}$ of all sequences begin with this string, another $4^{-4}$ end with it, and no sequence both begins and ends with this string. Therefore the chance is $2 \times 4^{-4}$.

On the other hand, what is the chance of $\ldots A A A A \ldots$? Once again, $4^{-4}$ of the sequences begin with this string, the same proportion end with this string, and $4^{-5}$ of all sequences do both. Therefore, by the Principle of Inclusion-Exclusion, the answer is $2 \times 4^{-4} - 4^{-5}$.

In general, the answer depends on the structure of the substring. To be more specific, when you're scanning a string (from left to right, say) for $ACGT$, you ignore all characters until you see that initial $A$. After that, there are three possibilities: the next character is a match for $C$, the next one is a non-match for $C$ but is not an $A$ (so you are back in the wait-for-an-$A$ state), or the next one is a non-match yet it's an $A$, placing you into the just-saw-an-$A$ state. In contrast, consider a search for $ACTACG$. Suppose you have seen the prefix $ACTAC$. The next character will match if it is $G$. When it's a non-match, (i) a $C$ puts you into the initial wait-for-an $A$ state, (ii) an $A$ has you watching out for a $C$, and (iii) a $T$ means you have already seen $\ldots ACT$ and you're already halfway to a match (and looking for the second $A$). The relevant "structure" evidently consists of patterns of substrings in the target that match the prefix of the target. That's why the chances depend on the target string.

The FSA diagrams I advocate in a reply at Time taken to hit a pattern of heads and tails in a series of coin-tosses can help with understanding this phenomenon.

Answer 2

A crude approximation would be $1-(1-1/4^r)^{n-r+1}$. You take the probability that your sequence do not occur at a particular location, put it to the power of the number of locations (falsely assuming independence), which is $n-r+1$ not $n-r$, and this is an approximation of its not occurring so you then need to subtract this from $1$.

A precise calculation will depend on the precise pattern you are looking for. $AAAAA$ is more likely to not occur than $ATCGT$.