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.