Faster exact distributions of pattern statistics through sequential elimination of states

DOI10.1007/S10463-015-0540-YzbMATH Open1398.62215OpenAlexW1872970325WikidataQ57009415 ScholiaQ57009415MaRDI QIDQ2397054FDOQ2397054

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

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

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)

Cites Work

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

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)