Modeling dynamic programming problems over sequences and trees with inverse coupled rewrite systems

DOI10.3390/a7010062zbMath1461.68251OpenAlexW2006724349MaRDI QIDQ1736602

Robert Giegerich, Hélène Touzet

Publication date: 26 March 2019

Published in: Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3390/a7010062

zbMATH Keywords

dynamic programmingtree edit distanceRNA structuretree alignmentbiosequence analysis

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Combinatorial optimization (90C27) Dynamic programming (90C39) Protein sequences, DNA sequences (92D20) Grammars and rewriting systems (68Q42)

Related Items (5)

Algebraic dynamic programming for multiple context-free grammars ⋮ Algebraic dynamic programming on trees ⋮ Editorial: Special issue on algorithms for sequence analysis and storage ⋮ Integrating Pareto optimization into dynamic programming ⋮ Counting, Generating, Analyzing and Sampling Tree Alignments

Uses Software

• Haskell
• Rfam
• Rnamotif
• KiCS2
• RNAforester
• Dyna
• Locomotif

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Alignment of trees -- an alternative to tree edit
• Tree edit distance with gaps
• A discipline of dynamic programming over sequence data
• An algebraic view of the relation between largest common subtrees and smallest common supertrees
• Decomposition algorithms for the tree edit distance problem
• Forest Alignment with Affine Gaps and Anchors
• Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems
• Algorithms for Loop Matchings
• Biological Sequence Analysis
• Algorithms on Strings, Trees and Sequences
• Term Rewriting and All That
• Sneaking around concatMap
• Approximate Dynamic Programming
• Semantics of context-free languages
• Algorithms and Computation

This page was built for publication: Modeling dynamic programming problems over sequences and trees with inverse coupled rewrite systems