Probabilistic Arithmetic Automata

Investigators: Tobias Marschall & Sven Rahmann
Funding: internal
Software: MoSDi

Probabilistic Arithmetic Automata are an extension of Deterministic Finite Automata (DFAs) and Hidden Markov Models (HMMs) to allow arithmetic or arbitrary binary operations. Exact state-value probability distributions can be efficiently computed with in this framework, and many applications in string algorithmics and computational biology can be modeled in this framework and treated in a unifying manner. Our work included:

• Development of the PAA framework (CPM 2008)
• Application: Exact analysis of pattern matching algorithms, e.g., Horspool, BNDM, BOM (LATA 2010)
• Application: significance of motifs and DNA Motif discovery (CPM 2008)
• Application: seed sensitivity for seeded alignment (WABI 2008)
• Application: significance of peaks in mass spectra (RECOMB-Satellite conference on Proteomics and Systems Biology 2007; precedes the formal PAA definition)