Titel
Algebraic Dynamic Programming over general data structures
Autor*in
Sonja J Prohaska
Computational EvoDevo Group, Department of Computer Science, Universität Leipzig
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.
Stichwort
formal grammardynamic programminggene duplications
Objekt-Typ
Sprache
Englisch [eng]
Persistent identifier
https://phaidra.univie.ac.at/o:446798
Erschienen in
Titel
BMC Bioinformatics
Band
16
Ausgabe
Suppl 19
Verlag
Springer Nature
Erscheinungsdatum
2015
Zugänglichkeit

Herunterladen

Universität Wien | Universitätsring 1 | 1010 Wien | T +43-1-4277-0