Modeling dynamic programming problems over sequences and trees with inverse coupled rewrite systems
type: Item
instance of: scholarly article
title: Modeling dynamic programming problems over sequences and trees with inverse coupled rewrite systems
zbMATH Open document ID: 1461.68251
author: Robert Giegerich
author: H. Touzet
published in: Algorithms
publication date: 2019-03-26T00:00:00Z
review text: Summary: 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 \textit{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.
Mathematics Subject Classification ID: 68W05
Mathematics Subject Classification ID: 68Q42
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C39
Mathematics Subject Classification ID: 92D20
zbMATH DE Number: 7042196
zbMATH Keywords: biosequence analysis
zbMATH Keywords: RNA structure
zbMATH Keywords: dynamic programming
zbMATH Keywords: tree edit distance
zbMATH Keywords: tree alignment
describes a project that uses: Haskell
describes a project that uses: Rfam
describes a project that uses: Rnamotif
describes a project that uses: RNAforester
describes a project that uses: KiCS2
describes a project that uses: Dyna
describes a project that uses: Locomotif
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a7010062
OpenAlex ID: W2006724349
cites work: Q3241581
cites work: Algorithms on Strings, Trees and Sequences
cites work: Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems
cites work: Semantics of context-free languages
cites work: A discipline of dynamic programming over sequence data
cites work: Sneaking around concatMap
cites work: Term Rewriting and All That
cites work: Q2783416
cites work: Biological Sequence Analysis
cites work: Q2723939
cites work: Algorithms for Loop Matchings
cites work: Alignment of trees -- an alternative to tree edit
cites work: An algebraic view of the relation between largest common subtrees and smallest common supertrees
cites work: Tree edit distance with gaps
cites work: Q4779184
cites work: Algorithms and Computation
cites work: Forest Alignment with Affine Gaps and Anchors
cites work: Decomposition algorithms for the tree edit distance problem
cites work: An optimal decomposition algorithm for tree edit distance
cites work: Approximate Dynamic Programming
cites work: Q3311639
cites work: Q3619797
DOI: 10.3390/A7010062
description: scientific article; zbMATH DE number 7042196