{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T03:38:55Z","timestamp":1767843535135,"version":"3.49.0"},"reference-count":56,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2017,12,6]],"date-time":"2017-12-06T00:00:00Z","timestamp":1512518400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Where string grammars describe how to generate and parse strings, tree grammars describe how to generate and parse trees. We show how to extend generalized algebraic dynamic programming to tree grammars. The resulting dynamic programming algorithms are efficient and provide the complete feature set available to string grammars, including automatic generation of outside parsers and algebra products for efficient backtracking. The complete parsing infrastructure is available as an embedded domain-specific language in Haskell. In addition to the formal framework, we provide implementations for both tree alignment and tree editing. Both algorithms are in active use in, among others, the area of bioinformatics, where optimization problems on trees are of considerable practical importance. This framework and the accompanying algorithms provide a beneficial starting point for developing complex grammars with tree- and forest-based inputs.<\/jats:p>","DOI":"10.3390\/a10040135","type":"journal-article","created":{"date-parts":[[2017,12,6]],"date-time":"2017-12-06T11:29:36Z","timestamp":1512559776000},"page":"135","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Algebraic Dynamic Programming on Trees"],"prefix":"10.3390","volume":"10","author":[{"given":"Sarah","family":"Berkemer","sequence":"first","affiliation":[{"name":"Bioinformatics Group, Department of Computer Science, Interdisciplinary Center for Bioinformatics, University Leipzig, H\u00e4rtelstra\u00dfe 16-18, D-04107 Leipzig, Germany"},{"name":"Max Planck Institute for Mathematics in the Sciences, Inselstra\u00dfe 22, D-04103 Leipzig, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9517-5839","authenticated-orcid":false,"given":"Christian","family":"H\u00f6ner zu Siederdissen","sequence":"additional","affiliation":[{"name":"Bioinformatics Group, Department of Computer Science, Interdisciplinary Center for Bioinformatics, University Leipzig, H\u00e4rtelstra\u00dfe 16-18, D-04107 Leipzig, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5016-5191","authenticated-orcid":false,"given":"Peter","family":"Stadler","sequence":"additional","affiliation":[{"name":"Bioinformatics Group, Department of Computer Science, Interdisciplinary Center for Bioinformatics, University Leipzig, H\u00e4rtelstra\u00dfe 16-18, D-04107 Leipzig, Germany"},{"name":"Max Planck Institute for Mathematics in the Sciences, Inselstra\u00dfe 22, D-04103 Leipzig, Germany"},{"name":"German Centre for Integrative Biodiversity Research (iDiv) Halle-Jena-Leipzig, Competence Center for Scalable Data Services and Solutions, and Leipzig Research Center for Civilization Diseases, University Leipzig, D-04103 Leipzig, Germany"},{"name":"Fraunhofer Institute for Cell Therapy and Immunology, Perlickstrasse 1, D-04103 Leipzig, Germany"},{"name":"Institute for Theoretical Chemistry, University of Vienna, W\u00e4hringerstra\u00dfe 17, A-1090 Wien, Austria"},{"name":"Center for RNA in Technology and Health, Univ. Copenhagen, Gr\u00f8nneg\u00e5rdsvej 3, 1870 Frederiksberg C, Denmark"},{"name":"Santa Fe Institute, 1399 Hyde Park Rd., Santa Fe, NM 87501, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2017,12,6]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"716","DOI":"10.1073\/pnas.38.8.716","article-title":"On the theory of dynamic programming","volume":"38","author":"Bellman","year":"1952","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_2","unstructured":"Sankoff, D., and Kruskal, J.B. (1983). Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison, Addison-Wesley."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/BF00818163","article-title":"Fast folding and comparison of RNA secondary structures","volume":"125","author":"Hofacker","year":"1994","journal-title":"Monatshefte f\u00fcr Chemie\/Chem. Mon."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Lorenz, R., Bernhart, S.H., H\u00f6ner zu Siederdissen, C., Tafer, H., Flamm, C., Stadler, P.F., and Hofacker, I.L. (2011). ViennaRNA Package 2.0. Algorithms Mol. Biol.","DOI":"10.1186\/1748-7188-6-26"},{"key":"ref_5","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_6","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1007\/BF01734359","article-title":"Evolutionary trees from DNA sequences: A maximum likelihood approach","volume":"17","author":"Felsenstein","year":"1981","journal-title":"J. Mol. Evol."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Chauve, C., Courtiel, J., and Ponty, Y. (2016, January 21\u201322). Counting, generating and sampling tree alignments. Proceedings of the International Conference on Algorithms for Computational Biology, Trujillo, Spain.","DOI":"10.1007\/978-3-319-38827-4_5"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1245","DOI":"10.1137\/0218082","article-title":"Simple fast algorithms for the editing distance between trees and related problems","volume":"18","author":"Zhang","year":"1989","journal-title":"SIAM J Comput."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"2056","DOI":"10.1093\/bioinformatics\/btw105","article-title":"ecceTERA: Comprehensive gene tree-species tree reconciliation using parsimony","volume":"32","author":"Jacox","year":"2016","journal-title":"Bioinformatics"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Schirmer, S., Ponty, Y., and Giegerich, R. (2014). Introduction to RNA secondary structure comparison. RNA Sequence, Structure, and Function: Computational and Bioinformatic Methods, Humana Press.","DOI":"10.1007\/978-1-62703-709-9_12"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Rinaudo, P., Ponty, Y., Barth, D., and Denise, A. (2012, January 9\u201311). Tree decomposition and parameterized algorithms for RNA structure-sequence alignment including tertiary interactions and pseudoknots. Proceedings of the 12th Workshop on Algorithms in Bioinformatics (WABI 2012), Ljubljana, Slovenia.","DOI":"10.1007\/978-3-642-33122-0_12"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"62","DOI":"10.3390\/a7010062","article-title":"Modeling Dynamic Programming Problems over Sequences and Trees with Inverse Coupled Rewrite Systems","volume":"7","author":"Giegerich","year":"2014","journal-title":"Algorithms"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1145\/321138.321145","article-title":"On the ambiguity problem of Backus systems","volume":"9","author":"Cantor","year":"1962","journal-title":"J. ACM"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1145\/368959.368993","article-title":"On ambiguity in phrase structure languages","volume":"5","author":"Floyd","year":"1962","journal-title":"Commun. ACM"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"176","DOI":"10.1016\/j.scico.2009.11.002","article-title":"Analyzing ambiguity of context-free grammars","volume":"75","author":"Brabrand","year":"2010","journal-title":"Sci. Comput. Program."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1093\/bioinformatics\/16.8.665","article-title":"A systematic approach to dynamic programming in bioinformatics","volume":"16","author":"Giegerich","year":"2000","journal-title":"Bioinformatics"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1109\/TCBB.2014.2326155","article-title":"Product Grammars for Alignment and Folding","volume":"12","author":"Hofacker","year":"2015","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_18","first-page":"215","article-title":"Sneaking around concatMap: Efficient combinators for dynamic programming","volume":"Volume 47","year":"2012","journal-title":"Proceedings of the 17th ACM SIGPLAN International Conference on Functional Programming, ICFP \u201912"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Sauthoff, G., Janssen, S., and Giegerich, R. (2011, January 20\u201322). Bellman\u2019s GAP\u2014A Declarative Language for Dynamic Programming. Proceedings of the 13th International ACM SIGPLAN Symposium on Principles and Practices of Declarative Programming, PPDP \u201911, Odense, Denmark.","DOI":"10.1145\/2003476.2003484"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1093\/bioinformatics\/btt022","article-title":"Bellman\u2019s GAP\u2014A Language and Compiler for Dynamic Programming in Sequence Analysis","volume":"29","author":"Sauthoff","year":"2013","journal-title":"Bioinformatics"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/S0019-9958(69)90065-5","article-title":"Tree generating regular systems","volume":"14","author":"Brainerd","year":"1969","journal-title":"Inf. Control"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0304-3975(90)90145-8","article-title":"Code selection by inversion of order-sorted derivors","volume":"73","author":"Giegerich","year":"1990","journal-title":"Theor. Comput. Sci."},{"key":"ref_23","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_24","doi-asserted-by":"crossref","unstructured":"H\u00f6ner zu Siederdissen, C., Prohaska, S.J., and Stadler, P.F. (2015). Algebraic Dynamic Programming over General Data Structures. BMC Bioinform., 16.","DOI":"10.1186\/1471-2105-16-S19-S2"},{"key":"ref_25","first-page":"243","article-title":"Algebraic Dynamic Programming","volume":"Volume 2422","author":"Giegerich","year":"2002","journal-title":"Algebraic Methodology and Software Technology"},{"key":"ref_26","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_27","first-page":"82","article-title":"How to Multiply Dynamic Programming Algorithms","volume":"Volume 8213","author":"Hofacker","year":"2013","journal-title":"Brazilian Symposium on Bioinformatics (BSB 2013)"},{"key":"ref_28","first-page":"57","article-title":"Dynamic Programming for Set Data Types","volume":"Volume 8826","author":"Prohaska","year":"2014","journal-title":"Brazilian Sympositum on Bioinformatics (BSB 2014)"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/j.tcs.2016.05.032","article-title":"Algebraic Dynamic Programming for Multiple Context-Free Languages","volume":"639","author":"Riechert","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1006\/jagm.2001.1170","article-title":"New algorithm for ordered tree-to-tree correction problem","volume":"40","author":"Chen","year":"2001","journal-title":"J. Algorithms"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Schwarz, S., Pawlik, M., and Augsten, N. (2017, January 4\u20136). A New Perspective on the Tree Edit Distance. Proceedings of the International Conference on Similarity Search and Applications, Munich, Germany.","DOI":"10.1007\/978-3-319-68474-1_11"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1145\/322139.322143","article-title":"The tree-to-tree correction problem","volume":"26","author":"Tai","year":"1979","journal-title":"J. ACM (JACM)"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"6309","DOI":"10.1073\/pnas.77.11.6309","article-title":"Fast algorithm for predicting the secondary structure of single-stranded RNA","volume":"77","author":"Nussinov","year":"1980","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1137\/0128004","article-title":"Minimal mutation trees of sequences","volume":"28","author":"Sankoff","year":"1975","journal-title":"SIAM J. Appl. Math."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1093\/sysbio\/20.4.406","article-title":"Towards defining the course of evolution: Minimum change for a specific tree topology","volume":"20","author":"Fitch","year":"1971","journal-title":"Syst. Biol."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"53","DOI":"10.2307\/2529676","article-title":"Minimum mutation fits to a given tree","volume":"29","author":"Hartigan","year":"1973","journal-title":"Biometrics"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1006\/jtbi.1999.1050","article-title":"Testing Character Correlation using Pairwise Comparisons on a Phylogeny","volume":"202","author":"Maddison","year":"2000","journal-title":"J. Theor. Biol."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1086\/656490","article-title":"Phylogenetic Targeting of Research Effort in Evolutionary Biology","volume":"176","author":"Arnold","year":"2010","journal-title":"Am. Nat."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1186\/1748-7188-5-25","article-title":"Polynomial algorithms for the Maximal Pairing Problem: Efficient phylogenetic targeting on arbitrary trees","volume":"5","author":"Arnold","year":"2010","journal-title":"Algorithms Mol. Biol."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1016\/0020-0190(77)90064-3","article-title":"The tree-to-tree editing problem","volume":"6","author":"Selkow","year":"1977","journal-title":"Inf. Process. Lett."},{"key":"ref_41","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_42","unstructured":"Schirmer, S. (2011). Comparing Forests. [Ph.D. Thesis, Bielefeld University]."},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Schirmer, S., and Giegerich, R. (2011). Forest alignment with affine gaps and anchors. Combinatorial Pattern Matching, Springer.","DOI":"10.1007\/978-3-642-21458-5_11"},{"key":"ref_44","unstructured":"H\u00f6chsmann, M. (2005). The Tree Alignment Model: Algorithms, Implementations and Applications for the Analysis of RNA Secondary Structures. [Ph.D. Thesis, Technische Fakult\u00e4t, Universit\u00e4t Bielefeld]."},{"key":"ref_45","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_46","doi-asserted-by":"crossref","first-page":"1500","DOI":"10.1093\/bioinformatics\/18.11.1500","article-title":"Empirical determination of effective gap penalties for sequence comparison","volume":"18","author":"Reese","year":"2002","journal-title":"Bioinformatics"},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/j.is.2015.08.004","article-title":"Tree edit distance: Robust and memory-efficient","volume":"56","author":"Pawlik","year":"2016","journal-title":"Inf. Syst."},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Bringmann, K., Gawrychowski, P., Mozes, S., and Weimann, O. (2018, January 7\u20138). Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can). Proceedings of the SODA 2018, New Orleans, LA, USA.","DOI":"10.1137\/1.9781611975031.77"},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/j.tcs.2004.12.030","article-title":"A survey on tree edit distance and related problems","volume":"337","author":"Bille","year":"2005","journal-title":"Theor. Comput. Sci."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1016\/S0304-3975(03)00323-2","article-title":"RNA secondary structure comparison: Exact analysis of the Zhang-Shasha tree edit algorithm","volume":"306","author":"Dulucq","year":"2003","journal-title":"Theor. Comput. Sci."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"461","DOI":"10.3233\/FI-2014-1054","article-title":"Segmental mapping and distance for rooted labeled ordered trees","volume":"132","author":"Kan","year":"2014","journal-title":"Fundam. Inform."},{"key":"ref_52","unstructured":"Kuboyama, T. (2007). Matching and Learning in Trees. [Ph.D. Thesis, Gakushuin University]."},{"key":"ref_53","doi-asserted-by":"crossref","unstructured":"Keller, G., Chakravarty, M.M., Leshchinskiy, R., Peyton Jones, S., and Lippmeier, B. (2010, January 27\u201329). Regular, Shape-polymorphic, Parallel Arrays in Haskell. Proceedings of the 15th ACM SIGPLAN International Conference on Functional Programming, ICFP \u201910, Baltimore, MD, USA.","DOI":"10.1145\/1863543.1863582"},{"key":"ref_54","doi-asserted-by":"crossref","unstructured":"Coutts, D., Leshchinskiy, R., and Stewart, D. (2007, January 1\u20133). Stream Fusion: From Lists to Streams to Nothing at All. Proceedings of the 12th ACM SIGPLAN International Conference on Functional Programming, ICFP \u201907, Freiburg, Germany.","DOI":"10.1145\/1291151.1291199"},{"key":"ref_55","doi-asserted-by":"crossref","unstructured":"Peyton Jones, S. (2007, January 1\u20133). Call-pattern Specialisation for Haskell Programs. Proceedings of the 12th ACM SIGPLAN International Conference on Functional Programming, ICFP \u201907, Freiburg, Germany.","DOI":"10.1145\/1291151.1291200"},{"key":"ref_56","doi-asserted-by":"crossref","unstructured":"Mainland, G. (2007, January 1\u20133). Why It\u2019s Nice to be Quoted: Quasiquoting for Haskell. Proceedings of the ACM SIGPLAN Workshop on Haskell Workshop, Freiburg, Germany.","DOI":"10.1145\/1291201.1291211"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/10\/4\/135\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T18:52:50Z","timestamp":1760208770000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/10\/4\/135"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,6]]},"references-count":56,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2017,12]]}},"alternative-id":["a10040135"],"URL":"https:\/\/doi.org\/10.3390\/a10040135","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12,6]]}}}