{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:26:55Z","timestamp":1760243215969,"version":"build-2065373602"},"reference-count":51,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2014,3,7]],"date-time":"2014-03-07T00:00:00Z","timestamp":1394150400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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\u2019s 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.<\/jats:p>","DOI":"10.3390\/a7010062","type":"journal-article","created":{"date-parts":[[2014,3,7]],"date-time":"2014-03-07T11:44:38Z","timestamp":1394192678000},"page":"62-144","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Modeling Dynamic Programming Problems over Sequences and Trees with Inverse Coupled Rewrite Systems"],"prefix":"10.3390","volume":"7","author":[{"given":"Robert","family":"Giegerich","sequence":"first","affiliation":[{"name":"Faculty of Technology and Center for Biotechnology, Bielefeld University, Bielefeld 33594, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"H\u00b4el'ene","family":"Touzet","sequence":"additional","affiliation":[{"name":"LIFL (UMR CNRS 8022, University of Lille) and INRIA, Villeneuve d'Ascq Cedex 59655, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2014,3,7]]},"reference":[{"key":"ref_1","unstructured":"Bellman, R.E. (1957). Dynamic Programming, Princeton University Press."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Cambridge University Press.","DOI":"10.1017\/CBO9780511574931"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","article-title":"A general method applicable to the search for similarities in the amino acid sequence of two proteins","volume":"48","author":"Needleman","year":"1970","journal-title":"J. Mol. Biol."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","article-title":"Identification of common molecular subsequences","volume":"147","author":"Smith","year":"1981","journal-title":"J. Mol. Biol."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1137\/0145048","article-title":"Simultaneous solution of the RNA folding, alignment and protosequence problems","volume":"45","author":"Sankoff","year":"1985","journal-title":"SIAM J. Appl. Math."},{"key":"ref_6","unstructured":"Ferch, M., Zhang, J., and H\u00f6chsmann, M. (October, January 30). Learning cooperative assembly with the graph representation of a state-action space. Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems, EPFL lausanne, Switzerland."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Reis, D., Golgher, P., Silva, A., and Laender, A. (2004, January 17\u201322). Automatic web news extraction using tree edit distance. Proceedings of the 13th International Conference on World Wide Web, ACM, New York, NY, USA.","DOI":"10.1145\/988672.988740"},{"key":"ref_8","unstructured":"Lusk, E., and Overbecck, R. (1989). Proceedings of the North American Conference on Logic Programming, MIT Press."},{"key":"ref_9","unstructured":"Hunter, L. (1993). Artificial Intelligence and Molecular Biology, AAAI\/MIT Press."},{"key":"ref_10","first-page":"333","article-title":"Linguistic approaches to biological sequences","volume":"13","author":"Searls","year":"1997","journal-title":"CABIOS"},{"key":"ref_11","first-page":"143","article-title":"A grammar-based unification of several alignment and folding algorithms","volume":"4","author":"Lefebvre","year":"1996","journal-title":"AAAI Intell. Syst. Mol. Biol."},{"key":"ref_12","first-page":"127","article-title":"Semantics of context free languages","volume":"2","author":"Knuth","year":"1968","journal-title":"Theory Comput. Syst."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/j.scico.2003.12.005","article-title":"A discipline of dynamic programming over sequence data","volume":"51","author":"Giegerich","year":"2004","journal-title":"Sci. Comput. Program."},{"key":"ref_14","unstructured":"Haddad, H. (2006, January 23\u201327). Challenges in the compilation of a domain specific language for dynamic programming. Proceedings of the 2006 ACM Symposium on Applied Computing, Dijon, France."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"H\u00f6ner zu Siederdissen, C. (2012, January 10\u201312). Sneaking around concatMap: efficient combinators for dynamic programming. Proceedings of the 17th ACM SIGPLAN International Conference on Functional Programming, Copenhagen, Denmark. ICFP \u201912.","DOI":"10.1145\/2364527.2364559"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1093\/bioinformatics\/btt022","article-title":"Bellman\u2019s GAP-A language and compiler for dynamic programming in sequence analysis","volume":"29","author":"Sauthoff","year":"2013","journal-title":"Bioinformatics"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Baader, F., and Nipkow, T. (1998). Term Rewriting and All That, Cambridge University Press.","DOI":"10.1017\/CBO9781139172752"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Ohlebusch, E. (2002). Advanced Topics in Term Rewriting, Springer.","DOI":"10.1007\/978-1-4757-3661-8"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1016\/0022-2836(82)90398-9","article-title":"An improved algorithm for matching biological sequences","volume":"162","author":"Gotoh","year":"1982","journal-title":"J. Mol. Biol."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Durbin, R., Eddy, S.R., Krogh, A., and Mitchison, G. (1998). Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids, Cambridge University Press.","DOI":"10.1017\/CBO9780511790492"},{"key":"ref_21","unstructured":"Giegerich, R. Explaining and controlling ambiguity in dynamic programming. Proceedings of the Combinatorial Pattern Matching."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1137\/0135006","article-title":"Algorithms for loop matchings","volume":"35","author":"Nussinov","year":"1978","journal-title":"SIAM J. Appl. Math."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1121\/1.2017061","article-title":"Trainable grammars for speech recognition","volume":"65","author":"Baker","year":"1979","journal-title":"J. Acoust. Soc. Am."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Sakakibara, Y., Brown, M., Hughey, R., Mian, I., Sj\u00f6lander, K., Underwood, R., and Haussler, D. (1994, January June). Recent Methods for RNA Modeling Using Stochastic Context-Free Grammars. Combinatorial Pattern Matching 1994, Asilomar, CA, USA.","DOI":"10.1109\/HICSS.1994.323568"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1186\/1471-2105-5-71","article-title":"Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction","volume":"5","author":"Dowell","year":"2004","journal-title":"BMC Bioinf."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1089\/10665270252935511","article-title":"A general edit distance between RNA structures","volume":"9","author":"Jiang","year":"2002","journal-title":"J. Comput. Biol."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/0304-3975(95)80029-9","article-title":"Alignment of trees \u2013 An alternative to tree edit","volume":"143","author":"Jiang","year":"1995","journal-title":"Theor. Comput. Sci."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"4724","DOI":"10.1093\/nar\/29.22.4724","article-title":"RNAMotif, an RNA secondary structure definition and search algorithm","volume":"29","author":"Macke","year":"2001","journal-title":"Nucleic Acids Res."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"i392","DOI":"10.1093\/bioinformatics\/btm179","article-title":"Locomotif: from graphical motif description to RNA motif search","volume":"23","author":"Reeder","year":"2007","journal-title":"Bioinformatics"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"2079","DOI":"10.1093\/nar\/22.11.2079","article-title":"RNA sequence analysis using covariance models","volume":"22","author":"Eddy","year":"1994","journal-title":"Nucleic Acids Res."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1109\/TCBB.2010.12","article-title":"Semantics and ambiguity of stochastic RNA family models","volume":"8","author":"Giegerich","year":"2011","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"D136","DOI":"10.1093\/nar\/gkn766","article-title":"Rfam: Updates to the RNA families database","volume":"37","author":"Gardner","year":"2009","journal-title":"Nucleic Acids Res."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/j.tcs.2006.05.031","article-title":"An algebraic view of the relation between largest common subtrees and smallest common supertrees","volume":"362","author":"Valiente","year":"2006","journal-title":"Theor. Comput. Sci."},{"key":"ref_34","unstructured":"Chawathe, S. Comparing hierarchical data in external memory. Proceedings of the 25th International Conference on Very Large Data Bases, San Francisco, CA, USA."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0020-0190(02)00369-1","article-title":"Tree edit distance with gaps","volume":"85","author":"Touzet","year":"2003","journal-title":"Inf. Process. Lett."},{"key":"ref_36","unstructured":"Zhuozhi Wang, K.Z. (2001). Mathematical Foundations of Computer Science, Budapest."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"1074","DOI":"10.1089\/cmb.2007.0062","article-title":"Locality and gaps in RNA comparison","volume":"14","author":"Backofen","year":"2007","journal-title":"J. Comput. Biol."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"702","DOI":"10.1089\/cmb.2006.13.702","article-title":"Local gapped subforest alignment and its application in finding RNA structural motifs","volume":"13","author":"Jansson","year":"2006","journal-title":"J. Comput. Biol."},{"key":"ref_39","unstructured":"Schirmer, S., and Giegerich, R. (2011). Combinatorial Pattern Matching, Springer."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1016\/j.jda.2004.08.018","article-title":"Decomposition algorithms for the tree edit distance problem","volume":"3","author":"Dulucq","year":"2005","journal-title":"J. Discrete Algorithms"},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Erik Demaine, Shay Mozes, B.R., and Weimann, O. (2009). An optimal decomposition algorithm for tree edit distance. ACM Trans. Algorithms, 6.","DOI":"10.1145\/1644015.1644017"},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Sauthoff, G., Janssen, S., and Giegerich, R. (2011, January July). Bellman\u2019s GAP: A declarative language for dynamic programming. Proceedings of the 13th International ACM SIGPLAN Symposium on Principles and Practices of Declarative Programming, Odense, Denmark. PPDP \u201911.","DOI":"10.1145\/2003476.2003484"},{"key":"ref_43","unstructured":"Rawlings, C.J., Clark, D.A., Altman, R.B., Hunter, L., Lengauer, T., and Wodak, S.J. Automata-theoretic models of mutation and alignment. Proceedings of the ISMB, 1995."},{"key":"ref_44","unstructured":"Huet, G., and Lankford, D. (1978). On theUniform Halting Problem for Term Rewriting Systems, Technical Report, Rapport Laboria 283, IRIA."},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Powell, W.B. (2007). Approximate Dynamic Programming: Solving the Curses of Dimensionality, Wiley-Interscience.","DOI":"10.1002\/9780470182963"},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1186\/1741-7007-4-5","article-title":"Complete probabilistic analysis of RNA shapes","volume":"4","author":"Giegerich","year":"2006","journal-title":"BMC Biol."},{"key":"ref_47","unstructured":"Sedgewick, R. (2002). Algorithms, Addison-Wesley."},{"key":"ref_48","unstructured":"Cormen, T., Leiserson, C., and Rivest, R. (1990). Introduction to Algorithms, MIT Press."},{"key":"ref_49","unstructured":"Bra\u00dfel, B., Hanus, M., Peem\u00f6ller, B., and Reck, F. KiCS2: A new compiler from curry to haskell. Proceedings of the 20th International Workshop on Functional and (Constraint) Logic Programming."},{"key":"ref_50","unstructured":"Thompson, S. (2011). Haskell: The Craft of Functional Programming, Addison Wesley."},{"key":"ref_51","unstructured":"Furche, T., Gottlob, G., Grasso, G., de Moor, O., and Sellers, A. (2011). Dyna: Extending Datalog for modern AI. Datalog 2.0, Springer."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/7\/1\/62\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:09:00Z","timestamp":1760216940000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/7\/1\/62"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,3,7]]},"references-count":51,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2014,3]]}},"alternative-id":["a7010062"],"URL":"https:\/\/doi.org\/10.3390\/a7010062","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2014,3,7]]}}}