Publications - Working papers
Please find below working papers of our group. Currently, we list 58 working papers.
In the list are only not published papers present. If you look for a preprint of an already published paper you must look in the "Published papers" section.
If you have problems accessing electronic information, please let us know:
©NOTICE: All working papers are copyrighted by the authors; If you would like to use all or a portion of any paper, please contact the author.
Algebraic Dynamic Programming for Multiple Context-Free Grammars
Maik Riechert, Christian Höner zu Siederdissen, Peter F. Stadler
Download
Abstract
We present theoretical foundations, and a practical implementation, that makes the method of Algebraic Dynamic Programming available for Multiple Context-Free Grammars. This allows to formulate optimization problems, where the search space can be described by such grammars, in a concise manner and solutions may be obtained efficiently.
This improves on the previous state of the art which required complex code based on hand-written dynamic programming recursions. We apply our method to the RNA pseudoknotted secondary structure prediction problem from computational biology.
Appendix and supporting files available at: http://www.bioinf.uni-leipzig.de/Software/gADP/
Keywords
Multiple Context-Free Grammars, Dynamic Programming, Algebraic Dynamic Programming, RNA Secondary Structure Prediction, Pseudoknots