NDLI: Probabilistic Arithmetic Automata and Their Applications

Content Provider	ACM Digital Library
Author	Herms, Inke Marschall, Tobias Kaltenbach, Hans-Michael Rahmann, Sven
Abstract	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.
Starting Page	1737
Ending Page	1750
Page Count	14
File Format	PDF
ISSN	15455963
DOI	10.1109/TCBB.2012.109
Volume Number	9
Issue Number	6
Journal	IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-11-01
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Hidden Markov models,Automata,Computational modeling,Markov processes,Probabilistic logic,Context,Bioinformatics,dynamic programming.,Probabilistic automaton,text model,hidden Markov model,pattern matching,statistics,clump,string algorithm,analysis of algorithms,alignment seed,peptide mass fingerprinting,DNA sequencing
Content Type	Text
Resource Type	Article
Subject	Genetics Biotechnology Applied Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Probabilistic Arithmetic Automata and Their Applications

Multiple sequence alignment a quick tour

Computing alignment seed sensitivity with probabilistic arithmetic automata (2008)

An Algorithm to Compute the Character Access Count Distribution for Pattern Matching Algorithms

Probabilistic graphical model for flash memory programming

Fortuna: Model Checking Priced Probabilistic Timed Automata

Probabilistic Inference for Obfuscated Network Attack Sequences

Exact analysis of pattern matching algorithms with probabilistic arithmetic automata. arXiv (1009)

Exact analysis of horspool’s and sunday’s pattern matching algorithms with probabilistic arithmetic automata.

Probabilistic Arithmetic Automata and Their Applications

Similar Documents

Probabilistic Arithmetic Automata and Their Applications

Multiple sequence alignment a quick tour

Computing alignment seed sensitivity with probabilistic arithmetic automata (2008)

An Algorithm to Compute the Character Access Count Distribution for Pattern Matching Algorithms

Probabilistic graphical model for flash memory programming

Fortuna: Model Checking Priced Probabilistic Timed Automata

Probabilistic Inference for Obfuscated Network Attack Sequences

Exact analysis of pattern matching algorithms with probabilistic arithmetic automata. arXiv (1009)

Exact analysis of horspool’s and sunday’s pattern matching algorithms with probabilistic arithmetic automata.

Probabilistic Arithmetic Automata and Their Applications