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.
Product Grammars for Alignment and Folding
Christian Höner zu Siederdissen, Ivo L. Hofacker, Peter F. Stadler
Download
PREPRINT 13-048: [ PDF ]
Status: Published
IEEE/ACM Transactions on Computational Biology and Bioinformatics 99 (2014).
Abstract
We develop a theory of algebraic operations over linear and context-free 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. In particular, we provide a fully worked frameshift-aware, semiglobal DNA-protein
alignment algorithm whose grammar is composed of products of small, atomic 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.
http://www.bioinf.uni-leipzig.de/Software/gramprod
Keywords
Linear grammar, context free grammar, product structure, multiple alignment, Haskell