Probabilistic Arithmetic Automata and Their Application to Pattern Matching Statistics

DOI10.1007/978-3-540-69068-9_11MaRDI QIDQ3506945zbMATH OpenOpenAlexFDO

Authors Tobias Marschall, Sven Rahmann

Publication date 17 June 2008

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-69068-9_11

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational methods for problems pertaining to biology (92-08)

Recommendations

• Exact analysis of Horspool's and Sunday's pattern matching algorithms with probabilistic arithmetic automata
• Motif statistics.
• scientific article; zbMATH DE number 1405792
• Pattern Markov Chains: Optimal Markov Chain Embedding Through Deterministic Finite Automata
• An algorithm to compute the character access count distribution for pattern matching algorithms

Cites work

• A unified approach to word occurrence probabilities
• Construction of Aho Corasick automaton in linear time for integer alphabets
• Efficient string matching
• scientific article; zbMATH DE number 5604066 (Why is no real title available?)
• scientific article; zbMATH DE number 1754502 (Why is no real title available?)
• scientific article; zbMATH DE number 2183071 (Why is no real title available?)
• scientific article; zbMATH DE number 3420624 (Why is no real title available?)
• Motif statistics.
• Multiple pattern matching: a Markov chain approach
• On the Power of Profiles for Transcription Factor Binding Site Detection
• Re-describing an algorithm by Hopcroft

Cited in

(19)

• Statistical input-output equivalence of automata
• Optimal pattern matching algorithms
• An algorithm to compute the character access count distribution for pattern matching algorithms
• Motif statistics.
• Moments of the count of a regular expression in a heterogeneous random sequence
• Faster exact distributions of pattern statistics through sequential elimination of states
• Set intersection and sequence matching with mismatch counting
• Distribution of clump statistics for a collection of words
• Exact analysis of Horspool's and Sunday's pattern matching algorithms with probabilistic arithmetic automata
• scientific article; zbMATH DE number 1245648 (Why is no real title available?)
• Pattern recognition of amino acids via a Poisson statistical approach
• scientific article; zbMATH DE number 1405792 (Why is no real title available?)
• Minimal auxiliary Markov chains through sequential elimination of states
• Designing optimal- and fast-on-average pattern matching algorithms
• Calculating PSSM probabilities with lazy dynamic programming
• Construction of minimal deterministic finite automata from biological motifs
• Computation of exact probabilities associated with overlapping pattern occurrences
• Efficient computation of probability distributions of pattern statistics through auxiliary Markov chains -- some considerations
• Distributions of pattern statistics in sparse Markov models

This page was built for publication: Probabilistic Arithmetic Automata and Their Application to Pattern Matching Statistics

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