{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T21:17:29Z","timestamp":1791407849000,"version":"4.3.3"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"abstract":"<jats:title>Abstract<\/jats:title><jats:sec>\n                <jats:title>Background<\/jats:title>\n                <jats:p>Dynamic programming is a widely used programming technique in bioinformatics. In sharp contrast to the simplicity of textbook examples, implementing a dynamic programming algorithm for a novel and non-trivial application is a tedious and error prone task. The algebraic dynamic programming approach seeks to alleviate this situation by clearly separating the dynamic programming recurrences and scoring schemes.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Results<\/jats:title>\n                <jats:p>Based on this programming style, we introduce a generic product operation of scoring schemes. This leads to a remarkable variety of applications, allowing us to achieve optimizations under multiple objective functions, alternative solutions and backtracing, holistic search space analysis, ambiguity checking, and more, without additional programming effort. We demonstrate the method on several applications for RNA secondary structure prediction.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Conclusion<\/jats:title>\n                <jats:p>The product operation as introduced here adds a significant amount of flexibility to dynamic programming. It provides a versatile testbed for the development of new algorithmic ideas, which can immediately be put to practice.<\/jats:p>\n              <\/jats:sec>","DOI":"10.1186\/1471-2105-6-224","type":"journal-article","created":{"date-parts":[[2005,9,13]],"date-time":"2005-09-13T06:14:12Z","timestamp":1126592052000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":25,"title":["Versatile and declarative dynamic programming using pair algebras"],"prefix":"10.1186","volume":"6","author":[{"given":"Peter","family":"Steffen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert","family":"Giegerich","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,9,12]]},"reference":[{"key":"549_CR1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences","author":"D Gusfield","year":"1997","unstructured":"Gusfield D: Algorithms on Strings, Trees, and Sequences. Cambridge University Press; 1997."},{"key":"549_CR2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological Sequence Analysis","author":"R Durbin","year":"1998","unstructured":"Durbin R, Eddy S, Krogh A, Mitchison G: Biological Sequence Analysis. Cambridge University Press; 1998."},{"key":"549_CR3","first-page":"9","volume-title":"Proceedings of the seventh annual international conference on Computational molecular biology","author":"V Bafna","year":"2003","unstructured":"Bafna V, Edwards N: On de novo interpretation of tandem mass spectra for peptide identification. In Proceedings of the seventh annual international conference on Computational molecular biology. ACM Press; 2003:9\u201318."},{"key":"549_CR4","unstructured":"Algebraic Dynamic Programming homepage[http:\/\/bibiserv.techfak.uni-bielefeld.de\/adp\/]"},{"issue":"3","key":"549_CR5","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/j.scico.2003.12.005","volume":"51","author":"R Giegerich","year":"2004","unstructured":"Giegerich R, Meyer C, Steffen P: A Discipline of Dynamic Programming over Sequence Data. Science of Computer Programming 2004, 51(3):215\u2013263.","journal-title":"Science of Computer Programming"},{"key":"549_CR6","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1137\/0135006","volume":"35","author":"R Nussinov","year":"1978","unstructured":"Nussinov R, Pieczenik G, Griggs J, Kleitman D: Algorithms for loop matchings. SIAM J Appl Math 1978, 35: 68\u201382.","journal-title":"SIAM J Appl Math"},{"key":"549_CR7","volume-title":"Dynamic Programming","author":"R Bellman","year":"1957","unstructured":"Bellman R: Dynamic Programming. Princeton University Press; 1957."},{"key":"549_CR8","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: 145\u2013165.","journal-title":"Biopolymers"},{"key":"549_CR9","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1016\/0022-247X(82)90223-2","volume":"86","author":"TL Morin","year":"1982","unstructured":"Morin TL: Monotonicity and the principle of optimality. J Math Anal Appl 1982, 86: 665\u2013674.","journal-title":"J Math Anal Appl"},{"issue":"16","key":"549_CR10","doi-asserted-by":"publisher","first-page":"4843","DOI":"10.1093\/nar\/gkh779","volume":"32","author":"R Giegerich","year":"2004","unstructured":"Giegerich R, Voss B, Rehmsmeier M: Abstract Shapes of RNA. Nucleic Acids Res 2004, 32(16):4843\u20134851.","journal-title":"Nucleic Acids Res"},{"key":"549_CR11","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1007\/3-540-45123-4_6","volume-title":"Proc Combinatorial Pattern Matching","author":"R Giegerich","year":"2000","unstructured":"Giegerich R: Explaining and Controlling Ambiguity in Dynamic Programming. In Proc Combinatorial Pattern Matching. Springer LNCS 1848; 2000:46\u201359."},{"key":"549_CR12","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: Evalution of lightweight stochastic context-free grammars for RNA secondary structure prediction. BMC Bioinformatics 2004, 5: 71.","journal-title":"BMC Bioinformatics"},{"key":"549_CR13","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1186\/1471-2105-6-153","volume":"6","author":"J Reeder","year":"2005","unstructured":"Reeder J, Steffen P, Giegerich R: Effective ambiguity checking in biosequence analysis. BMC Bioinformatics 2005, 6: 153.","journal-title":"BMC Bioinformatics"},{"key":"549_CR14","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1186\/1471-2105-5-104","volume":"5","author":"J Reeder","year":"2004","unstructured":"Reeder J, Giegerich R: Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics. BMC Bioinformatics 2004, 5: 104.","journal-title":"BMC Bioinformatics"},{"key":"549_CR15","doi-asserted-by":"publisher","first-page":"1507","DOI":"10.1261\/rna.5248604","volume":"10","author":"M Rehmsmeier","year":"2004","unstructured":"Rehmsmeier M, Steffen P, H\u00f6chsmann M, Giegerich R: Fast and effective prediction of microRNA\/target duplexes. RNA 2004, 10: 1507\u20131517.","journal-title":"RNA"},{"key":"549_CR16","doi-asserted-by":"publisher","first-page":"3516","DOI":"10.1093\/bioinformatics\/bti577","volume":"21","author":"J Reeder","year":"2005","unstructured":"Reeder J, Giegerich R: Consensus Shapes: an alternative to the Sankoff Algorithm for RNA consensus structure prediction. Bioinformatics 2005, 21: 3516\u201323. [Advance access]","journal-title":"Bioinformatics"}],"updated-by":[{"DOI":"10.1186\/1471-2105-7-214","type":"erratum","label":"Erratum","source":"publisher","updated":{"date-parts":[[2006,4,20]],"date-time":"2006-04-20T00:00:00Z","timestamp":1145491200000}}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-6-224.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,1]],"date-time":"2024-02-01T17:51:12Z","timestamp":1706809872000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-6-224"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,9,12]]},"references-count":16,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2005,12]]}},"alternative-id":["549"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-6-224","relation":{"erratum":[{"id-type":"doi","id":"10.1186\/1471-2105-7-214","asserted-by":"object"}]},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,9,12]]},"assertion":[{"value":"24 May 2005","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 September 2005","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 September 2005","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"224"}}