TBI-p-2013-8

Download: No pdf submitted

Titel:
How to Multiply Dynamic Programming Algorithms

Author(s):
Christian Höner zu Siederdissen, Ivo L. Hofacker, and Peter F. Stadler

submitted to:
Brazilian Symposium on Bioinformatics (BSB 2013). Lecture Notes in Bioinformatics 8213

Abstract:
We develop a theory of algebraic operations over linear grammars that makes it possible to combine simple ``atomic'' grammars operating on single sequences into complex, multi-dimensional grammars. We demonstrate the utility of this framework by constructing the search spaces of complex alignment problems on multiple input sequences explicitly as algebraic expressions of very simple 1-dimensional grammars. The compiler accompanying our theory makes it easy to experiment with the combination of multiple grammars and different operations. Composite grammars can be written out in \LaTeX{} for documentation and as a guide to implementation of dynamic programming algorithms. An embedding in Haskell as a domain-specific language makes the theory directly accessible to writing and using grammar products without the detour of an external compiler.

Link to publication:

Return to Index Return to List
Last modified: 2008-10-22 12:23:11 fall