Publications - Published papers
Please find below publications of our group. Currently, we list 565 papers. Some of the publications are in collaboration with the group of Sonja Prohaska and are also listed in the publication list for her individual group. Access to published papers (
) is restricted to our local network and chosen collaborators.
If you have problems accessing electronic information, please let us know:
) is restricted to our local network and chosen collaborators.
If you have problems accessing electronic information, please let us know:©NOTICE: All papers are copyrighted by the authors; If you would like to use all or a portion of any paper, please contact the author.
How to multiply dynamic programming algorithms
Christian Höner zu Siederdissen, Ivo L. Hofacker, and Peter F. Stadler
Download
Status: Published
In Joao C. Setubal and Nalvo F. Almeida, editors, Advances in Bioinformatics and Computational Biology, 8th BSB , volume 8213 of Lect. Notes Comp. Sci. , pages 82–93 (2013)
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 di fferent 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-specifi c language makes the theory
directly accessible to writing and using grammar products without the
detour of an external compiler.
http://www.bioinf.uni-leipzig.de/Software/gramprod/
Keywords
linear grammar, context free grammar, product structure, multiple alignment, Haskell