Motif statistics.

DOI10.1016/S0304-3975(01)00264-XzbMath1061.68118OpenAlexW2912570624MaRDI QIDQ1853502

Pierre Nicodème, Philippe Flajolet, Bruno Salvy

Publication date: 21 January 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(01)00264-x

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Combinatorial probability (60C05) Protein sequences, DNA sequences (92D20) Asymptotic enumeration (05A16)

Related Items

Some probabilistic results on the nonrandomness of simple sequence repeats in DNA sequences ⋮ Stochastic analysis of minimal automata growth for generalized strings ⋮ Sparse approaches for the exact distribution of patterns in long state sequences generated by a Markov source ⋮ Large deviation properties for patterns ⋮ Asymptotic normality for -dependent and constrained -statistics, with applications to pattern matching in random strings and permutations ⋮ Average Value and Variance of Pattern Statistics in Rational Models ⋮ Probabilistic Arithmetic Automata and Their Application to Pattern Matching Statistics ⋮ Construction of minimal deterministic finite automata from biological motifs ⋮ Local limit laws for symbol statistics in bicomponent rational models ⋮ An analytic approach to the asymptotic variance of trie statistics and related structures ⋮ Shuffling biological sequences with motif constraints ⋮ Multiple pattern matching: a Markov chain approach ⋮ An algorithm to compute the character access count distribution for pattern matching algorithms ⋮ Weighted dependency graphs ⋮ Growth of repetition-free words -- a review ⋮ Frequency of symbol occurrences in bicomponent stochastic models ⋮ Pattern statistics and Vandermonde matrices. ⋮ Controlled non-uniform random generation of decomposable structures ⋮ Moments of the count of a regular expression in a heterogeneous random sequence ⋮ Approximation of sojourn-times via maximal couplings: motif frequency distributions ⋮ On the First k Moments of the Random Count of a Pattern in a Multistate Sequence Generated by a Markov Source ⋮ Pattern Markov Chains: Optimal Markov Chain Embedding Through Deterministic Finite Automata ⋮ Probabilistic models for pattern statistics ⋮ Asymptotic properties of words in semi-Markov sequences ⋮ Variances and covariances in the central limit theorem for the output of a transducer

Uses Software

• gfun

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• From regular expressions to deterministic automata
• Central and local limit theorems applied to asymptotic enumeration. III. Matrix recursions
• The distribution of subword counts is usually normal
• Deviations from uniformity in random strings
• String overlaps, pattern matching, and nontransitive games
• On pattern frequency occurrences in a Markovian sequence
• Regular expressions into finite automata
• Dynamical sources in information theory: Fundamental intervals and word prefixes
• Effective asymptotics of linear recurrences with rational coefficients
• Central and local limit theorems applied to asymptotic enumeration
• GFUN
• The computation of nearly minimal Steiner trees in graphs