Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
435197 | Theoretical Computer Science | 2016 | 19 Pages |
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/
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Maik Riechert, Christian Höner zu Siederdissen, Peter F. Stadler,