{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T05:03:40Z","timestamp":1737349420428,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540422426"},{"type":"electronic","value":"9783540457275"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-45727-5_9","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T16:25:28Z","timestamp":1184603128000},"page":"99-110","source":"Crossref","is-referenced-by-count":0,"title":["Computational Complexity of Word Counting"],"prefix":"10.1007","author":[{"given":"Mireille","family":"R\u00e9gnier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,6,28]]},"reference":[{"key":"9_CR1","unstructured":"Apostolico, A., Bock, M., Lonardi, S., and Xu, X. (1999). Efficient detection of unusual words. Journal of Computational Biology. to appear; preliminary version as Technical Report 97-050, Purdue University Computer Science Department (1996)."},{"key":"9_CR2","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1006\/eujc.1993.1030","volume":"14","author":"E. A. Bender","year":"1993","unstructured":"Bender, E. A. and Kochman, F. (1993). The Distribution of Subwords Counts is Usually Normal. European Journal of Combinatorics, 14:265\u2013275.","journal-title":"European Journal of Combinatorics"},{"key":"9_CR3","first-page":"433","volume":"8","author":"M. Borodovsky","year":"1992","unstructured":"Borodovsky, M. and Kleffe, J. (1992). First and second moments of counts of words in random texts generated by markov chains. CABIOS, 8:433\u2013441.","journal-title":"CABIOS"},{"key":"9_CR4","doi-asserted-by":"publisher","first-page":"228","DOI":"10.2307\/3213763","volume":"22","author":"S. Breen","year":"1985","unstructured":"Breen, S., Waterman, M., and Zhang, N. (1985). Renewal theory for several patterns. J. Appl. Prob., 22:228\u2013234.","journal-title":"J. Appl. Prob."},{"key":"9_CR5","first-page":"167","volume":"79","author":"C. Chrysaphinou","year":"1990","unstructured":"Chrysaphinou, C. and Papastavridis, S. (1990). The occurrence of sequence of patterns in repeated dependent experiments. Theory of Probability and Applications, 79:167\u2013173.","journal-title":"Theory of Probability and Applications"},{"key":"9_CR6","doi-asserted-by":"publisher","first-page":"877","DOI":"10.2307\/3215201","volume":"32","author":"M. Geske","year":"1995","unstructured":"Geske, M., Godbole, A., Schafner, A., Skolnick, A., and Wallstrom, G. (1995). Compound Poisson Approximations for Word Patterns Under Markovian Hypotheses. J. Appl. Prob., 32:877\u2013892.","journal-title":"J. Appl. Prob."},{"issue":"A","key":"9_CR7","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/0097-3165(81)90005-4","volume":"30","author":"L. Guibas","year":"1981","unstructured":"Guibas, L. and Odlyzko, A. (1981). String Overlaps, Pattern Matching and Non-transitive Games. Journal of Combinatorial Theory, Series A, 30:183\u2013208.","journal-title":"Journal of Combinatorial Theory"},{"key":"9_CR8","volume-title":"Finite Markov Chains","author":"J. Kemeny","year":"1983","unstructured":"Kemeny, J. and Snell, J. (1983). Finite Markov Chains. Undergraduate Texts in Mathematics. Springer-Verlag, Berlin."},{"issue":"1","key":"9_CR9","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/S0097-8485(99)00047-9","volume":"24","author":"M. Klaerr-Blanchard","year":"2000","unstructured":"Klaerr-Blanchard, M., Chiapello, H., and Coward, E. (2000). Detecting localized repeats in genomic sequences: A new strategy and its application to B. subtilis and A. thaliana sequences. Comput. Chem., 24(1):57\u201370.","journal-title":"Comput. Chem."},{"key":"9_CR10","series-title":"Lect Notes Comput Sci","volume-title":"CPM\u201997","author":"S. Kurtz","year":"1997","unstructured":"Kurtz, S. and Myers, G. (1997). Estimating the Probability of Approximate Matches. In CPM\u201997, Lecture Notes in Computer Science. Springer-Verlag."},{"key":"9_CR11","doi-asserted-by":"publisher","first-page":"1171","DOI":"10.1214\/aop\/1176994578","volume":"8","author":"S. Li","year":"1980","unstructured":"Li, S. (1980). A Martingale Approach to the Study of Occurrences of Sequence Patterns in Repeated Experiments. Ann. Prob., 8:1171\u20131176.","journal-title":"Ann. Prob."},{"issue":"4","key":"9_CR12","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/S0097-8485(97)00022-3","volume":"21","author":"W. Li","year":"1997","unstructured":"Li, W. (1997). The study of correlation structures of DNA sequences: a critical review. Computers Chem., 21(4):257\u2013271.","journal-title":"Computers Chem."},{"key":"9_CR13","unstructured":"Lundstrom, R. (1990). Stochastic Models and Statistical Methods for DNA Sequence Data. Phdthesis, University of Utah."},{"key":"9_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1007\/3-540-48481-7_18","volume-title":"ESA\u201999","author":"P. Nicod\u00e8me","year":"1999","unstructured":"Nicod\u00e8me, P., Salvy, B., and Flajolet, P. (1999). Motif statistics. In ESA\u201999, volume 1643 of Lecture Notes in Computer Science, pages 194\u2013211. Springer-Verlag. Proc. European Symposium on Algorithms-ESA\u201999, Prague."},{"key":"9_CR15","doi-asserted-by":"crossref","first-page":"1013","DOI":"10.1080\/07391102.1989.10506528","volume":"6","author":"P. Pevzner","year":"1991","unstructured":"Pevzner, P., Borodovski, M., and Mironov, A. (1991). Linguistic of Nucleotide sequences:The Significance of Deviations from the Mean: Statistical Characteristics and Prediction of the Frequency of Occurrences of Words. J. Biomol. Struct. Dynam., 6:1013\u20131026.","journal-title":"J. Biomol. Struct. Dynam."},{"key":"9_CR16","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1111\/j.2517-6161.1995.tb02025.x","volume":"57","author":"B. Prum","year":"1995","unstructured":"Prum, B., Rodolphe, F., and de Turckheim, E. (1995). Finding Words with Unexpected Frequencies in DNA sequences. J. R. Statist. Soc. B., 57:205\u2013220.","journal-title":"J. R. Statist. Soc. B."},{"issue":"1","key":"9_CR17","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/S0166-218X(00)00195-5","volume":"104","author":"M. R\u00e9gnier","year":"2000","unstructured":"R\u00e9gnier, M. (2000). A Unified Approach to Word Occurrences Probabilities. Discrete Applied Mathematics, 104(1):259\u2013280. Special issue on Computational Biology;preliminary version at RECOMB\u201998.","journal-title":"Discrete Applied Mathematics"},{"key":"9_CR18","unstructured":"R\u00e9gnier, M., Lifanov, A., and Makeev, V. (2000). Three variations on word counting. In GCB\u201900, pages 75\u201382. Logos-Verlag. Proc. German Conference on Bioinformatics, Heidelberg."},{"issue":"4","key":"9_CR19","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1007\/PL00009244","volume":"22","author":"M. R\u00e9gnier","year":"1997","unstructured":"R\u00e9gnier, M. and Szpankowski, W. (1997). On Pattern Frequency Occurrences in a Markovian Sequence. Algorithmica, 22(4):631\u2013649. preliminary draft at ISIT\u201997.","journal-title":"Algorithmica"},{"key":"9_CR20","unstructured":"Schbath, S. (1995). Etude Asymptotique du Nombre d\u2019Occurrences d\u2019un mot dans une Chaine de Markov et Application \u00e0 la Recherche de Mots de Frequence Exceptionnelle dans les Sequences d\u2019ADN. Th\u00e8se de 3e cycle, Universit\u00e9e de Paris V."},{"issue":"1","key":"9_CR21","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1089\/cmb.1997.4.35","volume":"4","author":"M. Tanushev","year":"1997","unstructured":"Tanushev, M. and Arratia, R. (1997). Central Limit Theorem for Renewal Theory for Several Patterns. Journal of Computational Biology, 4(1):35\u201344.","journal-title":"Journal of Computational Biology"},{"key":"9_CR22","unstructured":"Tompa, M. (1999). An exact method for finding short motifs in sequences, with application to the ribosome binding site problem. In ISMB\u201999, pages 262\u2013271. AAAI Press. Seventh International Conference on Intelligent Systems for Molecular Biology, Heidelberg,Germany."},{"key":"9_CR23","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4899-6846-3","volume-title":"Introduction to Computational Biology","author":"M. Waterman","year":"1995","unstructured":"Waterman, M. (1995). Introduction to Computational Biology. Chapman and Hall, London."}],"container-title":["Lecture Notes in Computer Science","Computational Biology"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45727-5_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,19]],"date-time":"2025-01-19T11:57:55Z","timestamp":1737287875000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45727-5_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422426","9783540457275"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-45727-5_9","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}