Publications - Published papers

Please find below publications of our group. Currently, we list 508 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 (access) 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.

Dynamic Programming for Set Data Types

Christian Höner zu Siederdissen, Sonja J. Prohaska, and Peter F. Stadler


PREPRINT 14-015:   [ Software ]


In Conference Proceedings of Brasilian Symposium on Bioinformatics BSB ’14, Belo Horizonte, MG, Brazil. Lect. Notes Comp Sci. 2014


Abstract. We present an efficient generalization of algebraic dynamic programming (ADP) to unordered data types and a formalism for the automated derivation of outside grammars from their inside progenitors. These theoretical contributions are illustrated by ADP-style algorithms for shortest Hamiltonian path problems. These arise naturally when ask- ing whether the evolutionary history of an ancient gene cluster can be explained by a series of local tandem duplications. Our framework makes it easy to compute Maximum accuracy solutions, which in turn require the computation of the probabilities of individual edges in the ensemble of Hamiltonian paths. The expansion of the Hox gene clusters is investi- gated as a show-case application.