Publications - Published papers
Please find below publications of our group. Currently, we list 565 papers. Some of the publications are in collaboration with the group of Sonja Prohaska and are also listed in the publication list for her individual group. Access to published papers (
) is restricted to our local network and chosen collaborators.
If you have problems accessing electronic information, please let us know:
) is restricted to our local network and chosen collaborators.
If you have problems accessing electronic information, please let us know:©NOTICE: All papers are copyrighted by the authors; If you would like to use all or a portion of any paper, please contact the author.
Algebraic dynamic programming over general data structures
Christian Höner zu Siederdissen, Sonja J. Prohaska, Peter F. Stadler
Download
PREPRINT 15-043:
Status: Published
BMC Bioinformatics 16: 19:S2
Abstract
Background: Dynamic programming algorithms provide exact solutions to many problems in computational
biology, such as sequence alignment, RNA folding, hidden Markov models (HMMs), and scoring of
phylogenetic trees. Structurally analogous algorithms compute optimal solutions, evaluate score distributions,
and perform stochastic sampling. This is explained in the theory of Algebraic Dynamic Programming (ADP) by
a strict separation of state space traversal (usually represented by a context free grammar), scoring (encoded
as an algebra), and choice rule. A key ingredient in this theory is the use of yield parsers that operate on the
ordered input data structure, usually strings or ordered trees. The computation of ensemble properties, such as
a posteriori probabilities of HMMs or partition functions in RNA folding, requires the combination of two
distinct, but intimately related algorithms, known as the inside and the outside recursion. Only the inside
recursions are covered by the classical ADP theory.
Results: The ideas of ADP are generalized to a much wider scope of data structures by relaxing the concept
of parsing. This allows us to formalize the conceptual complementarity of inside and outside variables in a
natural way. We demonstrate that outside recursions are generically derivable from inside decomposition
schemes. In addition to rephrasing the well-known algorithms for HMMs, pairwise sequence alignment, and
RNA folding we show how the TSP and the shortest Hamiltonian path problem can be implemented efficiently
in the extended ADP framework. As a showcase application we investigate the ancient evolution of HOX gene
clusters in terms of shortest Hamiltonian paths.
Conclusions: The generalized ADP framework presented here greatly facilitates the development and
implementation of dynamic programming algorithms for a wide spectrum of applications.
Keywords
formal grammar; dynamic programming; gene duplications