Publications - Published papers

Please find below publications of our group. Currently, we list 501 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 (access) 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


PREPRINT 13-047: [ PDF ]
  paperID

Status:


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