This talk presents the ALGEBRAIC approach to dynamic programming (ADP),
which guarantees 100 percent more fun in the life of a dynamic programmer.
Dynamic programming is indispensible in bioinformatics, but not an easy
technique to employ. The simplicity of textbook examples (such as the Needleman-Wunsch,
Smith-Waterman, Nussinov algorithms) is deceiving. In real life, the development
of a dynamic programming algorithm is tedious. Our algorithmic ideas are obscured by
the low abstraction level of matrix recurrences. Testing the code is cumbersome,
as it is difficult to recognize when a wrong (sub-optimal) result is returned.
The new framework:
The logic of a dynamic programming algorithm can be cleanly
separated into the aspects of problem decomposition and candidate scoring. The
described by a special form of grammar, the latter by a family of functions
called an evaluation algebra. These specifications given, an implementation
can be generated automatically, and translated into correct and efficient code
using the ADP compiler recently completed by Peter Steffen.
Liberated from tedious coding and debugging issues, we may embark on more
sophisticated analyses. For a problem at hand, we may want to know not only the optimal
score, but also an optimal solution itself, information about its uniqueness,
eventually all co-optimal solutions, the solutions under multiple criteria
(the most beautiful among the best), the best solution satisfying some nontrivial extra
requirement, and so on.
Benefits and applications:
It turns out that all such concerns can also be described as evaluation algebras,
and a powerful product operation on these algebras allows to create new and combined
analyses from them, without re-programming effort.
The presentation will introduce the ADP technique in an informal way,
point to some bioinformatics tools recently built with this approach,
and -- hopefully -- stimulate discussion on its potential further