#### Bellman's GAP

The system includes the multi-paradigm language (GAP-L), its compiler (GAP-C)
and functional modules (GAP-M) . GAP-L includes declarative constructs, e.g.
tree grammars to model the search space, and imperative constructs for programming
advanced scoring functions. The syntax of GAP-L is similar to C/Java to lower usage
barriers. GAP-C translates the high-level and index-free GAP-L programs into
efficient C++-Code, which is competitive with handwritten code. It includes a
novel table design optimization algorithm, support for dynamic programming (DP)
over multiple sequences (multi-track DP), sampling, optional top-down evaluation,
various backtracing schemes etc. GAP-M includes modules for use in GAP-L programs.
Examples are efficient representations of classification data types and sampling
as well as filter helper functions.

#### Algebraic dynamic programming

Algebraic Dynamic Programming (ADP) is a formal framework for specifying dynamic
programming algorithms on sequences. It clearly separates the concerns of search
space description, candidate description, candidate evaluation and tabulation.

Tree grammars (G) specify the search space, algebras (E) evaluate candidate terms
and signatures (��) declare the function reservoir which tree grammars and algebras
are using. Tabulation is specified through non-terminal annotation in tree grammars.
The use of tree grammars for search space description eliminates subscripts from the
algorithm description, i.e. a major source of programming errors in developing DP
algorithms.

Algebras are building blocks to wrap different scoring schemes or optimization s
trategies (h). With product operations they can be combined to more powerful analyses.

#### Fold-Grammars

Dynamic programming is ubiquitous in bioinformatics. Developing and implementing non-trivial
dynamic programming algorithms is often error prone and tedious. Bellman's GAP is a new
programming system, designed to ease the development of bioinformatics tools based on the
dynamic programming technique.
Fold-Grammars is
repository for thermodynamic RNA folding with Bellman's GAP.