{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T10:31:48Z","timestamp":1762252308277},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"S19","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2015,12]]},"DOI":"10.1186\/1471-2105-16-s19-s2","type":"journal-article","created":{"date-parts":[[2015,12,17]],"date-time":"2015-12-17T05:01:58Z","timestamp":1450328518000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Algebraic Dynamic Programming over general data structures"],"prefix":"10.1186","volume":"16","author":[{"given":"Christian H\u00f6ner","family":"zu Siederdissen","sequence":"first","affiliation":[]},{"given":"Sonja J","family":"Prohaska","sequence":"additional","affiliation":[]},{"given":"Peter F","family":"Stadler","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,12,16]]},"reference":[{"key":"7209_CR1","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/3-540-45719-4_24","volume-title":"Algebraic Methodology And Software Technology. Lect. Notes Comp. Sci","author":"R Giegerich","year":"2002","unstructured":"Giegerich R, Meyer C: Algebraic dynamic programming. Algebraic Methodology And Software Technology. Lect. Notes Comp. Sci. Edited by: Kirchner, H., Ringeissen, C. 2002, Springer, Berlin, Heidelberg, 2422: 349-364."},{"key":"7209_CR2","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/2364527.2364559","volume-title":"Proceedings of the 17th ACM SIGPLAN International Conference on Functional Programming (ICFP'12)","author":"C H\u00f6ner zu Siederdissen","year":"2012","unstructured":"H\u00f6ner zu Siederdissen C: Sneaking around concatMap: efficient combinators for dynamic programming. Proceedings of the 17th ACM SIGPLAN International Conference on Functional Programming (ICFP'12). 2012, ACM, New York, 215-226."},{"key":"7209_CR3","first-page":"29","volume-title":"Proceedings of the 13th International ACM SIGPLAN Symposium on Principles and Practices of Declarative Programming (PPDP'11)","author":"G Sauthoff","year":"2011","unstructured":"Sauthoff G, Janssen S, Giegerich R: Bellman's GAP - a declarative language for dynamic programming. Proceedings of the 13th International ACM SIGPLAN Symposium on Principles and Practices of Declarative Programming (PPDP'11). 2011, ACM, New York, 29-40."},{"key":"7209_CR4","first-page":"62","volume-title":"Algorithms","author":"R Giegerich","year":"2014","unstructured":"Giegerich R, Touzet H: Modeling dynamic programming problems over sequences and trees with inverse coupled rewrite systems. Algorithms. 2014, 62-144."},{"key":"7209_CR5","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1093\/bioinformatics\/btq370","volume":"26","author":"C H\u00f6ner zu Siederdissen","year":"2010","unstructured":"H\u00f6ner zu Siederdissen C, Hofacker IL: Discriminatory power of RNA family models. Bioinformatics. 2010, 26: 453-459.","journal-title":"Bioinformatics"},{"key":"7209_CR6","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1186\/1741-7007-4-5","volume":"4","author":"B Vo\u00df","year":"2006","unstructured":"Vo\u00df B, Giegerich R, Rehmsmeier M: Complete probabilistic analysis of RNA shapes. BMC Biology. 2006, 4: 5-","journal-title":"BMC Biology"},{"key":"7209_CR7","volume-title":"IEEE\/ACM Trans. Comp. Biol. Bioinf","author":"C H\u00f6ner zu Siederdissen","year":"2014","unstructured":"H\u00f6ner zu Siederdissen C, Hofacker IL, Stadler PF: Product grammars for alignment and folding. IEEE\/ACM Trans. Comp. Biol. Bioinf. 2014, 99:"},{"key":"7209_CR8","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1109\/5.18626","volume":"77","author":"LR Rabiner","year":"1989","unstructured":"Rabiner LR: A tutorial on hidden markov models and selected applications in speech recognition. Proc. IEEE. 1989, 77: 257-286.","journal-title":"Proc. IEEE"},{"key":"7209_CR9","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1121\/1.2017061","volume":"65","author":"JK Baker","year":"1979","unstructured":"Baker JK: Trainable grammars for speech recognition. J. Acoust. Soc. Am. 1979, 65: 132-","journal-title":"J. Acoust. Soc. Am"},{"key":"7209_CR10","doi-asserted-by":"publisher","first-page":"2646","DOI":"10.1093\/bioinformatics\/btp481","volume":"25","author":"FWD Huang","year":"2009","unstructured":"Huang FWD, Qin J, Reidys CM, Stadler PF: Partition function and base pairing probabilities for RNA-RNA interaction prediction. Bioinformatics. 2009, 25: 2646-2654.","journal-title":"Bioinformatics"},{"key":"7209_CR11","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1093\/bioinformatics\/btp635","volume":"26","author":"FWD Huang","year":"2010","unstructured":"Huang FWD, Qin J, Reidys CM, Stadler PF: Target prediction and a statistical sampling algorithm for RNA-RNA interaction. Bioinformatics. 2010, 26: 175-181.","journal-title":"Bioinformatics"},{"key":"7209_CR12","doi-asserted-by":"publisher","first-page":"1076","DOI":"10.1093\/bioinformatics\/btr090","volume":"27","author":"CM Reidys","year":"2011","unstructured":"Reidys CM, Huang FWD, Andersen JE, Penner RC, Stadler PF, Nebel ME: Topology and prediction of RNA pseudoknots. Bioinformatics. 2011, 27: 1076-1085. Addendum in: Bioinformatics 28:300 (2012)","journal-title":"Bioinformatics"},{"key":"7209_CR13","volume-title":"PhD thesis, Univ. Bielefeld","author":"S Janssen","year":"2014","unstructured":"Janssen S: Kisses, ambivalent models and more: Contributions to the analysis of RNA secondary structure. PhD thesis, Univ. Bielefeld. 2014, urn: nbn:de:hbz:361-26821318"},{"key":"7209_CR14","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1145\/321105.321111","volume":"9","author":"R Bellman","year":"1962","unstructured":"Bellman R: Dynamic programming treatment of the travelling salesman problem. J. ACM. 1962, 9: 61-63.","journal-title":"J. ACM"},{"key":"7209_CR15","first-page":"196","volume":"10","author":"M Held","year":"1962","unstructured":"Held M, Karp RM: A dynamic programming approach to sequencing problems. J. SIAM. 1962, 10: 196-201.","journal-title":"J. SIAM"},{"key":"7209_CR16","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological Sequence Analysis","author":"R Durbin","year":"1998","unstructured":"Durbin R, Eddy SR, Krogh AGM: Biological Sequence Analysis. 1998, Cambridge University Press, Cambridge"},{"key":"7209_CR17","doi-asserted-by":"crossref","unstructured":"Needleman SB, Wunsch CD: A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Biol. 1970, 443-453. 48","DOI":"10.1016\/0022-2836(70)90057-4"},{"key":"7209_CR18","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/S0022-5193(86)80112-6","volume":"121","author":"O Gotoh","year":"1986","unstructured":"Gotoh O: Alignment of three biological sequences with an efficient traceback procedure. J. theor. Biol. 1986, 121: 327-337.","journal-title":"J. theor. Biol"},{"key":"7209_CR19","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1186\/1748-7188-6-26","volume":"6","author":"R Lorenz","year":"2011","unstructured":"Lorenz R, Bernhart SH, H\u00f6ner zu Siederdissen C, Tafer H, Flamm C, Stadler PF, Hofacker IL: ViennaRNA Package 2.0. Alg. Mol. Biol. 2011, 6: 26-","journal-title":"Alg. Mol. Biol"},{"issue":"2","key":"7209_CR20","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1002\/(SICI)1097-0282(199902)49:2<145::AID-BIP4>3.0.CO;2-G","volume":"49","author":"S Wuchty","year":"1999","unstructured":"Wuchty S, Fontana W, Hofacker IL, Schuster P: Complete suboptimal folding of RNA and the stability of secondary structures. Biopolymers. 1999, 49 (2): 145-165.","journal-title":"Biopolymers"},{"key":"7209_CR21","doi-asserted-by":"publisher","first-page":"1105","DOI":"10.1002\/bip.360290621","volume":"29","author":"JS McCaskill","year":"1990","unstructured":"McCaskill JS: The equilibrium partition function and base pair binding probabilities for RNA secondary structure. Biopolymers. 1990, 29: 1105-1119.","journal-title":"Biopolymers"},{"key":"7209_CR22","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1186\/1471-2105-5-71","volume":"5","author":"RD Dowell","year":"2004","unstructured":"Dowell RD, Eddy SR: Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction. BMC Bioinformatics. 2004, 5: 71-","journal-title":"BMC Bioinformatics"},{"key":"7209_CR23","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1093\/bioinformatics\/btr220","volume":"27","author":"C H\u00f6ner zu Siederdissen","year":"2011","unstructured":"H\u00f6ner zu Siederdissen C, Berhart SH, Stadler PF, Hofacker IL: A folding algorithm for extended RNA secondary structures. Bioinformatics. 2011, 27: 129-137.","journal-title":"Bioinformatics"},{"key":"7209_CR24","doi-asserted-by":"crossref","first-page":"1124","DOI":"10.1002\/bip.22337","volume":"99","author":"C H\u00f6ner zu Siederdissen","year":"2013","unstructured":"H\u00f6ner zu Siederdissen C, Hammer S, Abfalter I, Hofacker IL, Flamm C, Stadler PF: Computational design of RNAs with complex energy landscapes. Biopolymers. 2013, 99: 1124-1136.","journal-title":"Biopolymers"},{"issue":"Suppl 2","key":"7209_CR25","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1093\/bioinformatics\/18.suppl_2.S92","volume":"8","author":"O Elemento","year":"2002","unstructured":"Elemento O, Gascuel O: An efficient and accurate distance based algorithm to reconstruct tandem duplication trees. Bioinformatics. 2002, 8 (Suppl 2): 92-99.","journal-title":"Bioinformatics"},{"key":"7209_CR26","doi-asserted-by":"publisher","first-page":"293","DOI":"10.2307\/276978","volume":"16","author":"WS Robinson","year":"1951","unstructured":"Robinson WS: A method for chronologically ordering archaeological deposits. Amer. Antiquity. 1951, 16: 293-301.","journal-title":"Amer. Antiquity"},{"key":"7209_CR27","volume-title":"Expansion of gene clusters and the shortest Hamiltonian path problem","author":"SJ Prohaska","year":"2015","unstructured":"Prohaska SJ, H\u00f6ner zu Siederdissen C, Stadler PF: Expansion of gene clusters and the shortest Hamiltonian path problem. 2015"},{"key":"7209_CR28","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1038\/sj.hdy.6800621","volume":"94","author":"J Garcia-Fern\u00e0ndez","year":"2005","unstructured":"Garcia-Fern\u00e0ndez J: Hox, parahox, protohox: facts and guesses. Heredity. 2005, 94: 145-152.","journal-title":"Heredity"},{"key":"7209_CR29","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1002\/jez.b.21070","volume":"306","author":"RA Cameron","year":"2006","unstructured":"Cameron RA, Rowen L, Nesbitt R, Bloom S, Rast JP, Berney K, Arenas-Mena C, Martinez P, Lucas S, Richardson PM, Davidson EH, Peterson KJ, Hood L: Unusual gene order and organization of the sea urchin Hox cluster. J Exp Zoolog B Mol Dev Evol. 2006, 306: 45-58.","journal-title":"J Exp Zoolog B Mol Dev Evol"},{"key":"7209_CR30","first-page":"82","volume-title":"Brazilian Symposium on Bioinformatics (BSB 2013). Lect. Notes Bioinf","author":"C H\u00f6ner zu Siederdissen","year":"2013","unstructured":"H\u00f6ner zu Siederdissen C, Hofacker IL, Stadler PF: How to multiply Dynamic Programming algorithms. Brazilian Symposium on Bioinformatics (BSB 2013). Lect. Notes Bioinf. 2013, Springer, Heidelberg, 8213: 82-93."},{"key":"7209_CR31","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/j.tcs.2004.12.030","volume":"337","author":"P Billie","year":"2005","unstructured":"Billie P: A survey on tree edit distance and related problems. Theor. Comp. Sci. 2005, 337: 217-239.","journal-title":"Theor. Comp. Sci"},{"key":"7209_CR32","first-page":"287","volume":"43","author":"C McBride","year":"2008","unstructured":"McBride C: Clowns to the left of me, jokers to the right (pearl): dissecting data structures. 2008, 43: 287-295.","journal-title":"Clowns to the left of me, jokers to the right (pearl): dissecting data structures"},{"key":"7209_CR33","volume-title":"Master's thesis, Hochschule f\u00fcr Technik, Wirtschaft und Kultur, Leipzig","author":"M Riechert","year":"2013","unstructured":"Riechert M: Algebraic dynamic programming for multiple context-free languages. Master's thesis, Hochschule f\u00fcr Technik, Wirtschaft und Kultur, Leipzig. 2013"},{"key":"7209_CR34","volume-title":"Algebraic dynamic programming for multiple context-free languages","author":"M Riechert","year":"2015","unstructured":"Riechert M, H\u00f6ner zu Siederdissen C, Stadler PF, Waldmann J: Algebraic dynamic programming for multiple context-free languages. 2015"},{"key":"7209_CR35","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/978-3-319-12418-6_8","volume-title":"Advances in Bioinformatics and Computational Biology: BSB 2014. Lect. Notes Comp. Sci","author":"C H\u00f6ner zu Siederdissen","year":"2014","unstructured":"H\u00f6ner zu Siederdissen C, Prohaska SJ, Stadler PF: Dynamic programming for set data types. Advances in Bioinformatics and Computational Biology: BSB 2014. Lect. Notes Comp. Sci. Edited by: Campos, S. 2014, 8826: 57-64."}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-16-S19-S2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,13]],"date-time":"2024-06-13T04:21:23Z","timestamp":1718252483000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-16-S19-S2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12]]},"references-count":35,"journal-issue":{"issue":"S19","published-print":{"date-parts":[[2015,12]]}},"alternative-id":["7209"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-16-s19-s2","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,12]]},"assertion":[{"value":"16 December 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"S2"}}