Bellman's GAP--a language and compiler for dynamic programming in sequence analysis.
BACKGROUND
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.


RESULTS
In Bellman's GAP, dynamic programming algorithms are described in a declarative style by tree grammars, evaluation algebras and products formed thereof. This bypasses the design of explicit dynamic programming recurrences and yields programs that are free of subscript errors, modular and easy to modify. The declarative modules are compiled into C++ code that is competitive to carefully hand-crafted implementations. This article introduces the Bellman's GAP system and its language, GAP-L. It then demonstrates the ease of development and the degree of re-use by creating variants of two common bioinformatics algorithms. Finally, it evaluates Bellman's GAP as an implementation platform of 'real-world' bioinformatics tools.


BACKGROUND
Bellman's GAP is available under GPL license from http://bibiserv.cebitec.uni-bielefeld.de/bellmansgap. This Web site includes a repository of re-usable modules for RNA folding based on thermodynamics.
Center of Biotechnology and Faculty of Technology, Bielefeld University, 33615 Bielefeld, Germany.
Georg
G
Sauthoff
Mathias
M
Möhl
Stefan
S
Janssen
Robert
R
Giegerich
D000465:Algorithms; D019295:Computational Biology / Q000379:methods; D011381:Programming Languages; D059370:RNA Folding; D017421:Sequence Analysis / Q000379:methods*