## Description of the Bellman's GAP Repository: Fold-Grammars

Bellman's GAP is a domain specific language and compiler for dynamic programming over sequence data. It's name is derived from "Bellman's Principle of Optimality, Grammars, Algebras, and Products". A Bellman's GAP repository is an archive of re-usable modules. Repositories are provided for code sharing. If you have modules to share, write to Stefan Janssen sjanssen@techfak.uni-bielefeld.de

A typical program in Bellman's GAP contains four elements:

- a signature, defining functions available in grammars which must be implemented in algebras,
- one or more algebras, evaluating a candidate from the search space and applying the objective function,
- one or more grammars, defining a search space of solution candidates
- one or more executable program instances, combining a grammar with a product of algebras.

### Naming conventions

Although GAP-L (Bellman's GAP language) allows arbitrary names, i.e. they must match the regular expression [A-Z_a-z][A-Z_a-z0-9]*, for signatures, algebras and grammars, we restrict ourselves for a better reading to the following naming convention:- signature names start with the prefix "sig_"
- algebra names start with the prefix "alg_"
- grammar names start with the prefix "gra_"
- for large elements, sub-fragments are outsourced in files starting with "XXXpart_"

### Repository content of Fold-Grammars

This repository is a collection of components (algebras, grammars, ...) for dynamic programming problems covering RNA secondary structure predictions. It covers the fields of:- single structure prediction (similar to RNAfold),
- prediction of structures for alignments (similar to RNAalifold) [filenames with "ali_"],
- sequence structure evaluation (similar to RNAeval) [filenames with "eval_"] ,
- abstract shape analysis (similar the RNAshapes) and HIshapes, and
- pseudoknot prediction (similar to pknotsRG and pKiss) [filenames with "pknot_"].
- outside computations, e.g. McCaskill base-pair probabilities, which also allow for Maximum Expected Accuracy (MEA) computations [filenames with "outside_"]

- "nodangle" (no energy contributions of dangling bases at all),
- "overdangle" (available or not, bases next to a stem always dangle from both sides to this stem),
- "microstate" (by increasing the search space a lot, best of all four possibilities for dangling onto a stem is selected. OK for MFE computations, but wrong for probabilistic analyses) and
- "macrostate" (unambiguous handling of dangling bases, i.e. no search space inflation and dangling only available bases onto a stem. Violating Bellman's principle of optimality for MFE computations, but correct for probabilistic analyses by using a four component vector, instead of a single partition function value. This component trick is the reason for some special algebra versions for macrostate.)