Algebraic dynamic programming for multiple context-free grammars
| Autor: | Peter F. Stadler, Maik Riechert, Christian Höner zu Siederdissen |
|---|---|
| Přispěvatelé: | Publica |
| Rok vydání: | 2016 |
| Předmět: |
0301 basic medicine
Theoretical computer science Optimization problem General Computer Science business.industry Computer science Programming language 0206 medical engineering 02 engineering and technology computer.software_genre Theoretical Computer Science Dynamic programming 03 medical and health sciences 030104 developmental biology Software Rule-based machine translation Stochastic context-free grammar State (computer science) Algebraic number L-attributed grammar business computer 020602 bioinformatics |
| Zdroj: | Theoretical Computer Science. 639:91-109 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2016.05.032 |
| Popis: | 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/ |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect