Faster exact distributions of pattern statistics through sequential elimination of states

DOI10.1007/s10463-015-0540-yzbMath1398.62215OpenAlexW1872970325WikidataQ57009415 ScholiaQ57009415MaRDI QIDQ2397054

Laurent Noé, Donald E. K. Martin

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) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Sequential statistical analysis (62L10)

Related Items

Minimal auxiliary Markov chains through sequential elimination of states, Distributions of pattern statistics in sparse Markov models

Uses Software

• PatternHunter

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The exact joint distribution of the sum of heads and apparent size statistics of a ``tandem repeats finder algorithm
• Multiple pattern matching: a Markov chain approach
• Waiting time distribution of generalized later patterns
• The exact distribution of the \(k\)-tuple statistic for sequence homology
• On spaced seeds for similarity search
• The exact and limiting distributions for the number of successes in success runs within a sequence of Markov-dependent two-state trials
• Runs, scans and urn model distributions: A unified Markov chain approach
• Application of auxiliary Markov chains to start-up demonstration tests
• An efficient algorithm for exact distribution of discrete scan statistics
• Distributions associated with general runs and patterns in hidden Markov models
• Distribution of statistics of hidden state sequences through the sum-product algorithm
• Distribution of Clump Statistics for a Collection of Words
• Subset Seed Automaton
• Probabilistic Arithmetic Automata and Their Application to Pattern Matching Statistics
• Efficient string matching
• Distribution Theory of Runs: A Markov Chain Approach
• Pattern Markov Chains: Optimal Markov Chain Embedding Through Deterministic Finite Automata
• p-values for the Discrete Scan Statistic through Slack Variables