Dirk Evers Dynamic Programming and RNA folding A new approach to the systematic development of dynamic programming algorithms is presented and applied to RNA folding. In order to develop more specific analyses, we split up the traditional dynamic programming approach into a structure recognition and an evaluation phase. Regular tree grammars are used to describe the recognized class of structures. An EBNF-like notation for tree grammars is developed. It turns into a recognizer by interpreting the EBNF-operators as parser combinators.
Polynomial efficiency is regained by the introduction of tabulating yield parsers.
By abstraction from the result constructors of a recognizer, we obtain an abstract folding space evaluator, described in terms of higher order functions. It can be instantiated towards any kind of analysis that can be specified by a so-called folding space evaluation algebra. Given such an instantiation, a correct and efficient set of dynamic programming recurrencies can be derived by straightforward mathematical reasoning. The flexibility of the approach is demonstrated by extending a given RNA grammar to evaluate dangling ends.