Cargando…

Algebraic Dynamic Programming over general data structures

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 distribut...

Descripción completa

Detalles Bibliográficos
Autores principales: zu Siederdissen, Christian Höner, Prohaska, Sonja J, Stadler, Peter F
Formato: Online Artículo Texto
Lenguaje:English
Publicado: BioMed Central 2015
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4686793/
https://www.ncbi.nlm.nih.gov/pubmed/26695390
http://dx.doi.org/10.1186/1471-2105-16-S19-S2
_version_ 1782406499340910592
author zu Siederdissen, Christian Höner
Prohaska, Sonja J
Stadler, Peter F
author_facet zu Siederdissen, Christian Höner
Prohaska, Sonja J
Stadler, Peter F
author_sort zu Siederdissen, Christian Höner
collection PubMed
description 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.
format Online
Article
Text
id pubmed-4686793
institution National Center for Biotechnology Information
language English
publishDate 2015
publisher BioMed Central
record_format MEDLINE/PubMed
spelling pubmed-46867932015-12-31 Algebraic Dynamic Programming over general data structures zu Siederdissen, Christian Höner Prohaska, Sonja J Stadler, Peter F BMC Bioinformatics Research 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. BioMed Central 2015-12-16 /pmc/articles/PMC4686793/ /pubmed/26695390 http://dx.doi.org/10.1186/1471-2105-16-S19-S2 Text en Copyright © 2015 zu Siederdissen et al. http://creativecommons.org/licenses/by/4.0 This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. The Creative Commons Public Domain Dedication waiver (http://creativecommons.org/publicdomain/zero/1.0/) applies to the data made available in this article, unless otherwise stated.
spellingShingle Research
zu Siederdissen, Christian Höner
Prohaska, Sonja J
Stadler, Peter F
Algebraic Dynamic Programming over general data structures
title Algebraic Dynamic Programming over general data structures
title_full Algebraic Dynamic Programming over general data structures
title_fullStr Algebraic Dynamic Programming over general data structures
title_full_unstemmed Algebraic Dynamic Programming over general data structures
title_short Algebraic Dynamic Programming over general data structures
title_sort algebraic dynamic programming over general data structures
topic Research
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4686793/
https://www.ncbi.nlm.nih.gov/pubmed/26695390
http://dx.doi.org/10.1186/1471-2105-16-S19-S2
work_keys_str_mv AT zusiederdissenchristianhoner algebraicdynamicprogrammingovergeneraldatastructures
AT prohaskasonjaj algebraicdynamicprogrammingovergeneraldatastructures
AT stadlerpeterf algebraicdynamicprogrammingovergeneraldatastructures