Modeling Dynamic Programming Problems over ...
Document type :
Compte-rendu et recension critique d'ouvrage
DOI :
Title :
Modeling Dynamic Programming Problems over Sequences and Trees with Inverse Coupled Rewrite Systems
Author(s) :
Giegerich, Robert [Auteur]
Universität Bielefeld = Bielefeld University
Touzet, Helene [Auteur]
Bioinformatics and Sequence Analysis [BONSAI]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Universität Bielefeld = Bielefeld University
Touzet, Helene [Auteur]

Bioinformatics and Sequence Analysis [BONSAI]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Journal title :
Algorithms
Pages :
62 - 144
Publisher :
MDPI
Publication date :
2014
ISSN :
1999-4893
HAL domain(s) :
Informatique [cs]/Bio-informatique [q-bio.QM]
Informatique [cs]/Algorithme et structure de données [cs.DS]
Informatique [cs]/Algorithme et structure de données [cs.DS]
English abstract : [en]
Dynamic programming is a classical algorithmic paradigm, which often allows the evaluation of a search space of exponential size in polynomial time. Recursive problem decomposition, tabulation of intermediate results for ...
Show more >Dynamic programming is a classical algorithmic paradigm, which often allows the evaluation of a search space of exponential size in polynomial time. Recursive problem decomposition, tabulation of intermediate results for re-use, and Bellman's Principle of Optimality are its well-understood ingredients. However, algorithms often lack abstraction and are difficult to implement, tedious to debug, and delicate to modify. The present article proposes a generic framework for specifying dynamic programming problems. This framework can handle all kinds of sequential inputs, as well as tree-structured data. Biosequence analysis, document processing, molecular structure analysis, comparison of objects assembled in a hierarchic fashion, and generally, all domains come under consideration where strings and ordered, rooted trees serve as natural data representations. The new approach introduces inverse coupled rewrite systems. They describe the solutions of combinatorial optimization problems as the inverse image of a term rewrite relation that reduces problem solutions to problem inputs. This specification leads to concise yet translucent specifications of dynamic programming algorithms. Their actual implementation may be challenging, but eventually, as we hope, it can be produced automatically. The present article demonstrates the scope of this new approach by describing a diverse set of dynamic programming problems which arise in the domain of computational biology, with examples in biosequence and molecular structure analysis.Show less >
Show more >Dynamic programming is a classical algorithmic paradigm, which often allows the evaluation of a search space of exponential size in polynomial time. Recursive problem decomposition, tabulation of intermediate results for re-use, and Bellman's Principle of Optimality are its well-understood ingredients. However, algorithms often lack abstraction and are difficult to implement, tedious to debug, and delicate to modify. The present article proposes a generic framework for specifying dynamic programming problems. This framework can handle all kinds of sequential inputs, as well as tree-structured data. Biosequence analysis, document processing, molecular structure analysis, comparison of objects assembled in a hierarchic fashion, and generally, all domains come under consideration where strings and ordered, rooted trees serve as natural data representations. The new approach introduces inverse coupled rewrite systems. They describe the solutions of combinatorial optimization problems as the inverse image of a term rewrite relation that reduces problem solutions to problem inputs. This specification leads to concise yet translucent specifications of dynamic programming algorithms. Their actual implementation may be challenging, but eventually, as we hope, it can be produced automatically. The present article demonstrates the scope of this new approach by describing a diverse set of dynamic programming problems which arise in the domain of computational biology, with examples in biosequence and molecular structure analysis.Show less >
Language :
Anglais
Popular science :
Non
Collections :
Source :
Files
- https://hal.archives-ouvertes.fr/hal-01084318/document
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-01084318/document
- Open access
- Access the document
- document
- Open access
- Access the document
- algorithms-07-00062-v2.pdf
- Open access
- Access the document
- Open access
- Access the document