Bellman’s GAP—a language and compiler for dynamic programming in sequence analysis by Georg Sauthoff, Mathias Möhl, Stefan Janssen and Robert Giegerich. (Bioinformatics (2013) 29 (5): 551-560. doi: 10.1093/bioinformatics/btt022)
Abstract:
Motivation: 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.
Availability: 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.
Contact: robert@techfak.uni-bielefeld.de
Supplementary information: Supplementary data are available at Bioinformatics online
Focused on bioinformatics but dynamic programming is not limited to that field.
There is a very amusing story about how the field came to have the name “dynamic programming” in the Wikipedia article: Dynamic Programming.