Fraunhofer-Gesellschaft

Publica

Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Algebraic dynamic programming for multiple context-free grammars

 
: Riechert, M.; Höner zu Siederdissen, C.; Stadler, P.F.

:

Theoretical computer science 639 (2016), pp.91-109
ISSN: 0304-3975
English
Journal Article
Fraunhofer IZI ()

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/

: http://publica.fraunhofer.de/documents/N-418140.html