Some strings -the texts- are assumed to be randomly generated, according to a probability model that is either a Bernoulli model or a Markov model. A rare event is the over or under-representation of a word or a set of words. The aim of this paper is twofold. First, a single word is given. One studies the tail distribution of the number of its occurrences. Sharp large deviation estimates are derived. Second, one assumes that a given word is overrepresented. The distribution of a second word is studied; formulae for the expectation and the variance are derived. In both cases, the formulae are accurate and actually computable. These results have applications in computational biology, where a genome is viewed as a text.

Source : oai:HAL:hal-00959004v1

Volume: Vol. 6 no. 2

Published on: January 1, 2004

Submitted on: March 26, 2015

Keywords: computable closed formulae,large deviations,combinatorics,generating fumctions,words,genome,computable closed formulae.,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

This page has been seen 120 times.

This article's PDF has been downloaded 119 times.