Approximate word matches between two random sequences

Abstract

Given two sequences over a finite alphabet $\mathcal{L}$, the $D_2$ statistic is the number of $m$-letter word matches between the two sequences. This statistic is used in bioinformatics for expressed sequence tag database searches. Here we study a generalization of the $D_2$ statistic in the context of DNA sequences, under the assumption of strand symmetric Bernoulli text. For $k<m$, we look at the count of $m$-letter word matches with up to $k$ mismatches. For this statistic, we compute the expectation, give upper and lower bounds for the variance and prove its distribution is asymptotically normal.

Published in at http://dx.doi.org/10.1214/07-AAP452 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Cited by in corpus (2)

• Empirical distribution of k-word matches in biological sequences
• Characterising the D2 statistic: word matches in biological sequences