Probabilistic Arithmetic Automata and their Applications

Details Probabilistic Arithmetic Automata and their Applications Probabilistic Arithmetic Automata and their Applications

2010-11-26

arxiv.org/abs/1011.5778v1

Computer Science

Formal Languages and Automata Theory

Scientific paper

We present probabilistic arithmetic automata (PAAs), a general model to describe chains of operations whose operands depend on chance, along with two different algorithms to exactly calculate the distribution of the results obtained by such probabilistic calculations. PAAs provide a unifying framework to approach many problems arising in computational biology and elsewhere. Here, we present five different applications, namely (1) pattern matching statistics on random texts, including the computation of the distribution of occurrence counts, waiting time and clump size under HMM 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 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 for pattern statistics: 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. We show how to transform a finite automaton into a DAA and then into the corresponding PAA.

Affiliated with

Also associated with

No associations

Rating

Probabilistic Arithmetic Automata and their Applications does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Probabilistic Arithmetic Automata and their Applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Probabilistic Arithmetic Automata and their Applications will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-462853