Asymptotic Behavior ofk-Word Matches Between two Uniformly Distributed Sequences

Given two sequences of lengthnover a finite alphabetAof size |A| =d, theD2statistic is the number ofk-letter word matches between the two sequences. This statistic is used in bioinformatics for EST sequence database searches. Under the assumption of independent and identically distributed letters in the sequences, Lippert, Huang and Waterman (2002) raised questions about the asymptotic behavior ofD2when the alphabet is uniformly distributed. They expressed a concern that the commonly assumed normality may create errors in estimating significance. In this paper we answer those questions. Using Stein's method, we show that, for large enoughk, theD2statistic is approximately normal asngets large. Whenk= 1, we prove that, for large enoughd, theD2statistic is approximately normal asngets large. We also give a formula for the variance ofD2in the uniform case.