**Vortragender:** Peter Stadler von der Universität Leipzig

**Location:** EI 2 Pichelmayer HS

**ABSTRACT:**

Dynamic Programming (DP) Algorithms are very common in bioinformatics. Key

computational problems in the field, such as sequence comparison,

RNA structure prediction, and many aspects of phylogenetics admit

exact DP solutions. Although conceptually simple, algorithms applicable to

practical scenaria are complicated by incorporating much biological detail,

and thus are tedious to implement and test. Algebraic dynamic programming

simplifies algorithm development through a strict

separating the generation of the search space, an evaluation algebra, and

a choice function. Since state space traversal is represented by grammars

in ADP, the framework is large restricted to strings and ordered trees,

and practical implementations are usually focussed on context-free grammars.

I will report on several recent advances. (1) Products of grammars allow

the efficient construction of multi-tape grammars from very simple low-

dimensional building blocks. In particular, complex alignment algorithms

can designed very easily in this manner. (2) The ideas of ADP readily

generalize to arbitrary Multi-Context-Free Grammars. This extension covers

in particular the extremely complicated algorithms solving RNA folding

problems for so-called pseudoknotted structures. (3) Re-interpreting the

notion of parsing (of strings) as partitioning of essentially arbitrary

data objects makes it possible to use the ideas of ADP on general

combinatorial data structures. In this general framework it becomes

clear that backward (in a HMM setting) outside (in a CFG setting)

recursions are uniquely determined by the easier forward/inside version

of the DP algorithms, i.e., by the generalized grammar defining the rules

of search space generation. The outside algorithm thus can be mechanically

computed from the inside “grammar” and does not need to be developed

separately. As an application we show how this can be used to compute

probability distributions over Hamiltonian paths. The key advantage of this

approach is that it becomes very simple and efficient in practise to

develop prototypical algorithms and in particular to modify the detailed

specification of the underlying models with very little effort.

The presentation will report joint work with

Christian Hoener zu Siederdissen, Sonja J. Prohaska, Maik Riechert, and

Johannes Waldmann.