Probabilistic Arithmetic Automata and Their Applications

Marschall T, Herms I, Kaltenbach H-M, Rahmann S (2012)
Ieee/Acm Transactions On Computational Biology And Bioinformatics 9(6): 1737-1750.

Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Zeitschriftenaufsatz | Veröffentlicht | Englisch
Autor
; ; ;
Abstract / Bemerkung
We present a comprehensive review on probabilistic arithmetic automata (PAAs), a general model to describe chains of operations whose operands depend on chance, along with two algorithms to numerically compute the distribution of the results of such probabilistic calculations. PAAs provide a unifying framework to approach many problems arising in computational biology and elsewhere. We present five different applications, namely 1) pattern matching statistics on random texts, including the computation of the distribution of occurrence counts, waiting times, and clump sizes under hidden Markov background models; 2) exact analysis of window-based pattern matching algorithms; 3) sensitivity of filtration seeds used to detect candidate sequence alignments; 4) length and mass statistics of peptide fragments resulting from enzymatic cleavage reactions; and 5) read length statistics of 454 and IonTorrent sequencing reads. The diversity of these applications indicates the flexibility and unifying character of the presented framework. While the construction of a PAA depends on the particular application, we single out a frequently applicable construction method: We introduce deterministic arithmetic automata (DAAs) to model deterministic calculations on sequences, and demonstrate how to construct a PAA from a given DAA and a finite-memory random text model. This procedure is used for all five discussed applications and greatly simplifies the construction of PAAs. Implementations are available as part of the MoSDi package. Its application programming interface facilitates the rapid development of new applications based on the PAA framework.
Erscheinungsjahr
Zeitschriftentitel
Ieee/Acm Transactions On Computational Biology And Bioinformatics
Band
9
Zeitschriftennummer
6
Seite
1737-1750
ISSN
PUB-ID

Zitieren

Marschall T, Herms I, Kaltenbach H-M, Rahmann S. Probabilistic Arithmetic Automata and Their Applications. Ieee/Acm Transactions On Computational Biology And Bioinformatics. 2012;9(6):1737-1750.
Marschall, T., Herms, I., Kaltenbach, H. - M., & Rahmann, S. (2012). Probabilistic Arithmetic Automata and Their Applications. Ieee/Acm Transactions On Computational Biology And Bioinformatics, 9(6), 1737-1750. doi:10.1109/TCBB.2012.109
Marschall, T., Herms, I., Kaltenbach, H. - M., and Rahmann, S. (2012). Probabilistic Arithmetic Automata and Their Applications. Ieee/Acm Transactions On Computational Biology And Bioinformatics 9, 1737-1750.
Marschall, T., et al., 2012. Probabilistic Arithmetic Automata and Their Applications. Ieee/Acm Transactions On Computational Biology And Bioinformatics, 9(6), p 1737-1750.
T. Marschall, et al., “Probabilistic Arithmetic Automata and Their Applications”, Ieee/Acm Transactions On Computational Biology And Bioinformatics, vol. 9, 2012, pp. 1737-1750.
Marschall, T., Herms, I., Kaltenbach, H.-M., Rahmann, S.: Probabilistic Arithmetic Automata and Their Applications. Ieee/Acm Transactions On Computational Biology And Bioinformatics. 9, 1737-1750 (2012).
Marschall, T., Herms, Inke, Kaltenbach, Hans-Michael, and Rahmann, Sven. “Probabilistic Arithmetic Automata and Their Applications”. Ieee/Acm Transactions On Computational Biology And Bioinformatics 9.6 (2012): 1737-1750.

2 Zitationen in Europe PMC

Daten bereitgestellt von Europe PubMed Central.

Analysis of pattern overlaps and exact computation of P-values of pattern occurrences numbers: case of Hidden Markov Models.
Régnier M, Furletova E, Yakovlev V, Roytberg M., Algorithms Mol Biol 9(1), 2014
PMID: 25648087

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®

Quellen

PMID: 22868683
PubMed | Europe PMC

Suchen in

Google Scholar