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

DOI10.1016/J.TCS.2012.10.019zbMATH Open1291.60148arXiv1006.3246OpenAlexW2084870011MaRDI QIDQ384993FDOQ384993

Authors: Gregory Nuel, Jean-Guillaume Dumas 

Publication date: 29 November 2013

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

Abstract: We present two novel approaches for the computation of the exact distribution of a pattern in a long sequence. Both approaches take into account the sparse structure of the problem and are two-part algorithms. The first approach relies on a partial recursion after a fast computation of the second largest eigenvalue of the transition matrix of a Markov chain embedding. The second approach uses fast Taylor expansions of an exact bivariate rational reconstruction of the distribution. We illustrate the interest of both approaches on a simple toy-example and two biological applications: the transcription factors of the Human Chromosome 5 and the PROSITE signatures of functional motifs in proteins. On these example our methods demonstrate their complementarity and their hability to extend the domain of feasibility for exact computations in pattern problems to a new level.

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

Recommendations

• On the First k Moments of the Random Count of a Pattern in a Multistate Sequence Generated by a Markov Source
• Numerical Solutions for Patterns Statistics on Markov Chains
• Multiple pattern matching: a Markov chain approach
• Distributions of pattern statistics in sparse Markov models
• Explicit distributional results in pattern formation

zbMATH Keywords

transcription factorsMarkov chain embeddingPROSITE signaturesrational reconstruction

Mathematics Subject Classification ID

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) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Efficient string matching
• Title not available (Why is that?)
• Title not available (Why is that?)
• A unified approach to word occurrence probabilities
• Motif statistics.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• High-order lifting and integrality certification
• Title not available (Why is that?)
• Explicit distributional results in pattern formation
• Compound Poisson approximation for counts of rare patterns in Markov chains and extreme sojourns in birth-death chains.
• Waiting time and complexity for matching patterns with automata
• 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
• Assessing the Statistical Significance of Overrepresented Oligonucleotides
• Compound Poisson approximations for word patterns under Markovian hypotheses
• An Efficient Formula for Linear Recurrences
• On exact and approximate interpolation of sparse rational functions
• Waiting time distributions for pattern occurrence in a constrained sequence
• 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

Cited In (6)

• Faster exact distributions of pattern statistics through sequential elimination of states
• Transducing Markov sequences
• Distributions of pattern statistics in sparse Markov models
• Sparse Markov chains for sequence data
• Moments of the count of a regular expression in a heterogeneous random sequence
• Distribution of statistics of hidden state sequences through the sum-product algorithm

Uses Software

• PCRE
• RE2
• SPatt

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q384993)