Faster exact distributions of pattern statistics through sequential elimination of states

DOI10.1007/S10463-015-0540-YMaRDI QIDQ2397054zbMATH OpenOpenAlexWikidataFDO

Authors Donald E. K. Martin, Laurent Noé

Publication date 29 May 2017

Published in Annals of the Institute of Statistical Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10463-015-0540-y

zbMATH Keywords

computational efficiencyactive proper suffixauxiliary Markov chainextended seed patternsminimal deterministic finite automatonoverlapping pattern occurrencesseeded alignmentsspaced seed coverage

Mathematics Subject Classification ID

Exact distribution theory in statistics (62E15) Sequential statistical analysis (62L10) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Recommendations

• Sparse approaches for the exact distribution of patterns in long state sequences generated by a Markov source
• Pattern Markov Chains: Optimal Markov Chain Embedding Through Deterministic Finite Automata
• Numerical Solutions for Patterns Statistics on Markov Chains
• On the First k Moments of the Random Count of a Pattern in a Multistate Sequence Generated by a Markov Source
• Distributions of pattern statistics in sparse Markov models

Cites work

• scientific article; zbMATH DE number 6683488 (Why is no real title available?)
• scientific article; zbMATH DE number 3174818 (Why is no real title available?)
• scientific article; zbMATH DE number 1955813 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 947423 (Why is no real title available?)
• An efficient algorithm for exact distribution of discrete scan statistics
• Application of auxiliary Markov chains to start-up demonstration tests
• DNA, words and models. Statistics of exceptional words. Translated from the 2003 French original
• Distribution Theory of Runs: A Markov Chain Approach
• Distribution of clump statistics for a collection of words
• Distribution of statistics of hidden state sequences through the sum-product algorithm
• Distribution theory of runs and patterns and its applications. A finite Markov chain imbedding approach
• Distributions associated with general runs and patterns in hidden Markov models
• Efficient string matching
• Multiple pattern matching: a Markov chain approach
• On spaced seeds for similarity search
• Pattern Markov Chains: Optimal Markov Chain Embedding Through Deterministic Finite Automata
• Probabilistic Arithmetic Automata and Their Application to Pattern Matching Statistics
• Runs and scans with applications
• Runs, scans and urn model distributions: A unified Markov chain approach
• Subset Seed Automaton
• The exact and limiting distributions for the number of successes in success runs within a sequence of Markov-dependent two-state trials
• The exact distribution of the \(k\)-tuple statistic for sequence homology
• The exact joint distribution of the sum of heads and apparent size statistics of a ``tandem repeats finder algorithm
• Waiting time distribution of generalized later patterns
• \(p\)-values for the discrete scan statistic through slack variables

Cited in

(3)

• Minimal auxiliary Markov chains through sequential elimination of states
• Distributions of pattern statistics in sparse Markov models
• Computation of exact probabilities associated with overlapping pattern occurrences

Describes a project that uses

Uses Software

• PatternHunter

This page was built for publication: Faster exact distributions of pattern statistics through sequential elimination of states

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