Sparse approaches for the exact distribution of patterns in long state sequences generated by a Markov source

DOI10.1016/j.tcs.2012.10.019zbMath1291.60148arXiv1006.3246OpenAlexW2084870011MaRDI QIDQ384993

Gregory Nuel, Jean-Guillaume Dumas

Publication date: 29 November 2013

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

Full work available at URL: https://arxiv.org/abs/1006.3246

zbMATH Keywords

transcription factorsMarkov chain embeddingPROSITE signaturesrational reconstruction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Protein sequences, DNA sequences (92D20)

Related Items (1)

Moments of the count of a regular expression in a heterogeneous random sequence

Uses Software

• PCRE
• RE2
• SPatt

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Waiting time and complexity for matching patterns with automata
• Explicit distributional results in pattern formation
• A unified approach to word occurrence probabilities
• Motif statistics.
• High-order lifting and integrality certification
• Compound Poisson approximation for counts of rare patterns in Markov chains and extreme sojourns in birth-death chains.
• Distribution of waiting time until the \(r\)th occurrence of a compound pattern
• Waiting times for patterns in a sequence of multistate trials
• Regular Expressions at Their Best: A Case for Rational Design
• Poisson approximations for runs and patterns of rare events
• Expected frequencies of DNA patterns using whittle's formula
• Efficient string matching
• Assessing the Statistical Significance of Overrepresented Oligonucleotides
• Compound Poisson approximations for word patterns under Markovian hypotheses
• An Efficient Formula for Linear Recurrences
• Numerical Solutions for Patterns Statistics on Markov Chains
• Pattern Markov Chains: Optimal Markov Chain Embedding Through Deterministic Finite Automata
• Combinatorial Pattern Matching
• A Unified Construction of the Glushkov, Follow, and Antimirov Automata

This page was built for publication: Sparse approaches for the exact distribution of patterns in long state sequences generated by a Markov source