ISSN:
1432-0541
Keywords:
Key words. Frequency of pattern occurrences, Markov source, Autocorrelation polynomials, Languages, Generating functions, Asymptotic analysis, Large deviations.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. Consider a given pattern H and a random text T generated by a Markovian source. We study the frequency of pattern occurrences in a random text when overlapping copies of the pattern are counted separately. We present exact and asymptotic formulae for moments (including the variance), and probability of r pattern occurrences for three different regions of r , namely: (i) r=O(1) , (ii) central limit regime, and (iii) large deviations regime. In order to derive these results, we first construct certain language expressions that characterize pattern occurrences which are later translated into generating functions. We then use analytical methods to extract asymptotic behaviors of the pattern frequency from the generating functions. These findings are of particular interest to molecular biology problems (e.g., finding patterns with unexpectedly high or low frequencies, and gene recognition), information theory (e.g., second-order properties of the relative frequency), and pattern matching algorithms (e.g., q -gram algorithms).
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00009244
Permalink