Asymptotic Behavior ofk-Word Matches Between two Uniformly Distributed Sequences
Authors:
- M. R. KantorovitzMKM. R. Kantorovitz
- H. S. BoothHBH. S. Booth
- C. J. BurdenCBC. J. Burden
- S. R. WilsonSWS. R. Wilson
Open Access
- 1 September 2007
- journal article
- research article
- Published by Cambridge University Press (CUP) in Journal of Applied Probability
- Vol. 44 (3) , 788-805
Abstract
Given two sequences of length n over a finite alphabet A of size |A| = d, the D 2 statistic is the number of k-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 of D 2 when 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 enough k, the D 2 statistic is approximately normal as n gets large. When k = 1, we prove that, for large enough d, the D 2 statistic is approximately normal as n gets large. We also give a formula for the variance of D 2 in the uniform case.Keywords
This publication has 15 references indexed in Scilit:
- Distributional regimes for the number ofk-word matches between two random sequencesProceedings of the National Academy of Sciences, 2002
- Assessment of the parallelization approach of d2_cluster for high‐performance sequence clusteringJournal of Computational Chemistry, 2002
- Genome shuffling leads to rapid phenotypic improvement in bacteriaNature, 2002
- Compound Poisson approximation: a user's guideThe Annals of Applied Probability, 2001
- STACK: Sequence Tag Alignment and Consensus KnowledgebaseNucleic Acids Research, 2001
- Introduction to Computational Biology: Maps, Sequences and Genomes.1998
- Some Examples of Normal Approximations by Stein’s Method1996
- Identification of common molecular subsequencesJournal of Molecular Biology, 1981
- Probability and measure, by Patrick Billingsley. Pp 515. £15·20. 1979. SBN 0 471 03173 9 (Wiley)The Mathematical Gazette, 1980
- Poisson Approximation for Dependent TrialsThe Annals of Probability, 1975