The exact distribution of the k-tuple statistic for sequence homology

✍ Scribed by W.Y.Wendy Lou

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 125 KB
• Volume: 61
• Category: Article
• ISSN: 0167-7152
• DOI: 10.1016/s0167-7152(02)00337-1

✦ Synopsis

The distribution theory of runs and patterns has become increasingly useful in the ÿeld of biological sequence homology. One important application in detecting tandem duplications among DNA sequence segments is the k-tuple statistic S n; k , the sum of matches in matching-runs of length k or longer in a sequence of n i.i.d. Bernoulli trials with success/matching probability p. Current approaches to this distribution problem are based on various approximations, due mainly to the numerical complexity of computing the exact distribution using a straightforward combinatorial approach. In this paper, we obtain a simple and e cient expression for the exact distribution of S n; k using the principle of ÿnite Markov chain imbedding. Our numerical results illustrate most importantly that for pattern lengths in the range n = 10 to 100, a range commonly used in detecting DNA tandem repeats, the distribution, in general, is highly skewed and far from normal.