5
$\begingroup$

Suppose I have two sequences of characters of length L and M respectively, with the characters chosen i.i.d. from an alphabet of A through H, each with probability p=1/8. I want to find the probability that there exists a subsequence of length N which occurs simultaneously in both the length L and M sequences. I don't actually care whether it occurs exactly once or at least once in each of the sequences. Whichever is easier will do.

For example, let's say we have

(L) AABBCCDDEEFFGGHH

(M) GBCCDFH

If N=4, I'm going to search through M and discover that BCCD also occurs in L (exactly once in both in this case). I want to know how likely that was to have happened (finding any length four sequence, not specifically BCCD).

In the case where M=N, I thought the answer would be something like

$$\left( \begin{array}{c} L-N+1\\ 1 \end{array} \right)*(p^N)^1*(1-p^N)^{L-N}$$

giving a lower bound, but of this, I'm not terribly confident. In any case, M will probably be significantly longer than N, so it would be good to get a more accurate answer.

$\endgroup$
  • $\begingroup$ I think a reasonable estimate would be to let the expression in the example above be p1 (p1 = choose(L-N+1,1)...). Then the probability would be p2 = choose(M-N+1,1)*p1^1*(1-p1)^(M-N). Intuitively, I would expect the answer to be roughly (M-N+1)*p1 if N is large. $\endgroup$ – Todd May 24 '13 at 20:01
  • $\begingroup$ Warning: when you say subsequences you mean consecutive elements or not necessarily? If you mean consecutive, you should rather speak of "substrings" en.wikipedia.org/wiki/Substring $\endgroup$ – leonbloy May 24 '13 at 21:20
0
$\begingroup$

Let $t$ be the length of the longest common substring. Then, $p_H = p(t \ge H)$, so the problem is equivalent to finding the probability distribution of $t$ This is a problem which has received quite work, but there are no simple exact results - even for the special case $L=M$. For example, see here and here.

Perhaps if you are interested in a particular range of $L,M$ we can get some approximation or algorithm...

Update : This is quite a complex problem, and I'm not really familiar with it. Only some notes and a wild estimate:

Allow me to change notation: let $n$ and $n$ be the lengths of the strings, $k$, the substring length, $a$ the alphabet size. THen, the expected number of common substrings is easily (the only easy result here) obtained as $\lambda_{n,m}^k = (n-k+1)(m-k+1) a^{-k}$

Equating that to 1, we can obtain a quick and rough estimate of the expected longest common substring: $k_1 = \log_a [(n-k_1+1)(m-k_1+1) ] \approx \log_a (n \, m)$ (instead of the last approximation we can also use the first equality as an interative solver). For example, for $n=5000$, $m=100$, $k_1 = 6.284$ This gives as a rough idea: if $k$ exceeds considerably this value, the probability will be near zero, if $k<k_1$ the probability will of quicky to 1.

A (very wild) estimate, for $k$ not very far from $k_1$, can be obtained by assuming a Poisson with mean $\lambda_{n,m}^k$, so the desired probability is

$$p \approx 1- \exp\left( -\lambda_{n,m}^k \right) \approx 1 - \exp\left( n \, m \, a^{-k}\right)$$

For example, for $n=5000$,$m=100$,$k=7$,$a=8$, I get $p\approx 0.178$ (simulation: $p\approx 0.2$)

$\endgroup$
  • $\begingroup$ I would expect L to be somewhere around 5000 to 10000 and M to be between 30 and 300. Even an order of magnitude estimate is probably good enough. $\endgroup$ – Todd May 24 '13 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.