A New Method of Approximating the Probability of Matching Common Words in Multiple Random Sequences

摘要

In this paper we consider R independent sequences of length T formed by independent, not necessarily uniformly distributed letters drawn from a finite alphabet. We first develop a new and efficient method of calculating the expectation E(N_R) = E(N_R(m,T)) of the number of distinct words of length m, N_R(m, T), which are common to R such sequences. We then consider the case of four uniformly distributed letters. We determine a b_R = b_R(m, T) ≥ 0 such that the interval [E(N_R) - b_R; E(N_R)] contains the probability p_R = ?(N_R ≥ 1) that there exists a word of length m common to the R sequences. We show that b_R ≈ 0.07E(N_R) if R = 3 and b_R ≤ 0.05 E(N_R) if R ≥ 4. Thus, for unusual common words, i. e. such that p_R is small, E(N_R) provides a very accurate approximation of this probability. We then compare numerically the intervals E(N_R)-b_R},E(N_R)] with former approximations of p_R provided by Karlin and Ost (Ann Probab 16:535-563, 1988) and Naus and Sheng (Bull Math Biol 59(3):483-495, 1997).