  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.
