{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,8]],"date-time":"2024-07-08T22:33:47Z","timestamp":1720478027033},"reference-count":20,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":1346,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013,3,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Dynamic programming is ubiquitous in bioinformatics. Developing and implementing non-trivial dynamic programming algorithms is often error prone and tedious. Bellman\u2019s GAP is a new programming system, designed to ease the development of bioinformatics tools based on the dynamic programming technique.<\/jats:p>\n               <jats:p>Results: In Bellman\u2019s GAP, dynamic programming algorithms are described in a declarative style by tree grammars, evaluation algebras and products formed thereof. This bypasses the design of explicit dynamic programming recurrences and yields programs that are free of subscript errors, modular and easy to modify. The declarative modules are compiled into C++ code that is competitive to carefully hand-crafted implementations.<\/jats:p>\n               <jats:p>This article introduces the Bellman\u2019s GAP system and its language, GAP-L. It then demonstrates the ease of development and the degree of re-use by creating variants of two common bioinformatics algorithms. Finally, it evaluates Bellman\u2019s GAP as an implementation platform of \u2018real-world\u2019 bioinformatics tools.<\/jats:p>\n               <jats:p>Availability: Bellman\u2019s GAP is available under GPL license from http:\/\/bibiserv.cebitec.uni-bielefeld.de\/bellmansgap. This Web site includes a repository of re-usable modules for RNA folding based on thermodynamics.<\/jats:p>\n               <jats:p>Contact: \u00a0robert@techfak.uni-bielefeld.de<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online<\/jats:p>","DOI":"10.1093\/bioinformatics\/btt022","type":"journal-article","created":{"date-parts":[[2013,1,26]],"date-time":"2013-01-26T02:29:08Z","timestamp":1359167348000},"page":"551-560","source":"Crossref","is-referenced-by-count":15,"title":["Bellman\u2019s GAP\u2014a language and compiler for dynamic programming in sequence analysis"],"prefix":"10.1093","volume":"29","author":[{"given":"Georg","family":"Sauthoff","sequence":"first","affiliation":[{"name":"1 Center of Biotechnology and Faculty of Technology, Bielefeld University, 33615 Bielefeld, Germany and 2Department of Computer Science and 3Centre for Biological Signalling Studies (BIOSS), Albert-Ludwigs-Universit\u00e4t 97110 Freiburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mathias","family":"M\u00f6hl","sequence":"additional","affiliation":[{"name":"1 Center of Biotechnology and Faculty of Technology, Bielefeld University, 33615 Bielefeld, Germany and 2Department of Computer Science and 3Centre for Biological Signalling Studies (BIOSS), Albert-Ludwigs-Universit\u00e4t 97110 Freiburg, Germany"},{"name":"1 Center of Biotechnology and Faculty of Technology, Bielefeld University, 33615 Bielefeld, Germany and 2Department of Computer Science and 3Centre for Biological Signalling Studies (BIOSS), Albert-Ludwigs-Universit\u00e4t 97110 Freiburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Janssen","sequence":"additional","affiliation":[{"name":"1 Center of Biotechnology and Faculty of Technology, Bielefeld University, 33615 Bielefeld, Germany and 2Department of Computer Science and 3Centre for Biological Signalling Studies (BIOSS), Albert-Ludwigs-Universit\u00e4t 97110 Freiburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Giegerich","sequence":"additional","affiliation":[{"name":"1 Center of Biotechnology and Faculty of Technology, Bielefeld University, 33615 Bielefeld, Germany and 2Department of Computer Science and 3Centre for Biological Signalling Studies (BIOSS), Albert-Ludwigs-Universit\u00e4t 97110 Freiburg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2013,1,25]]},"reference":[{"key":"2023051607332898800_btt022-B1","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1142\/S0219720009004060","article-title":"Alignment of minisatellite maps based on run-length encoding scheme","volume":"7","author":"Abouelhoda","year":"2009","journal-title":"J. Bioinform. Comput. Biol."},{"key":"2023051607332898800_btt022-B2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological Sequence Analysis","author":"Durbin","year":"1998"},{"key":"2023051607332898800_btt022-B3","article-title":"A domain-specific compiler for linear algebra operations","volume-title":"High Performance Computing for Computational Science\u2014VECPAR 2012","author":"Fabregat-Traver","year":"2012"},{"key":"2023051607332898800_btt022-B4","doi-asserted-by":"crossref","DOI":"10.1145\/1141277.1141653","article-title":"Challenges in the compilation of a domain specific language for dynamic programming","volume-title":"Proceedings of the 2006 ACM Symposium on Applied Computing","author":"Giegerich","year":"2006"},{"key":"2023051607332898800_btt022-B5","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":"2023051607332898800_btt022-B6","doi-asserted-by":"crossref","first-page":"2135","DOI":"10.1261\/rna.033548.112","article-title":"Abstract folding space analysis based on helices","volume":"18","author":"Huang","year":"2012","journal-title":"RNA"},{"key":"2023051607332898800_btt022-B7","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1186\/1471-2105-12-429","article-title":"Lost in folding space? Comparing four variants of the thermodynamic model for RNA secondary structure prediction","volume":"12","author":"Janssen","year":"2011","journal-title":"BMC Bioinformatics"},{"key":"2023051607332898800_btt022-B8","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1186\/1748-7188-6-26","article-title":"ViennaRNA package 2.0","volume":"6","author":"Lorenz","year":"2011","journal-title":"Algorithms for Mol. Biol."},{"key":"2023051607332898800_btt022-B9","volume-title":"Analysis of minisatellite sequences with Algebraic Dynamic Programming in Bellman\u2019s GAP","author":"L\u00f6wes","year":"2012"},{"key":"2023051607332898800_btt022-B10","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":"2023051607332898800_btt022-B11","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":"2023051607332898800_btt022-B12","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1186\/1471-2105-12-38","article-title":"Removing noise from pyrosequenced amplicons","volume":"12","author":"Quince","year":"2011","journal-title":"BMC Bioinformatics"},{"key":"2023051607332898800_btt022-B13","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1038\/nmeth0910-668b","article-title":"Rapidly denoising pyrosequencing amplicon reads by exploiting rank-abundance distributions","volume":"7","author":"Reeder","year":"2010","journal-title":"Nat. Methods"},{"key":"2023051607332898800_btt022-B14","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":"2023051607332898800_btt022-B15","doi-asserted-by":"crossref","first-page":"925","DOI":"10.3390\/genes2040925","article-title":"Conservation and occurrence of trans-encoded srnas in the rhizobiales","volume":"2","author":"Reinkensmeier","year":"2011","journal-title":"Genes"},{"key":"2023051607332898800_btt022-B16","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1261\/rna.030049.111","article-title":"A range of complex probabilistic models for RNA secondary structure prediction that includes the nearest-neighbor model and more","volume":"18","author":"Rivas","year":"2012","journal-title":"RNA"},{"key":"2023051607332898800_btt022-B17","doi-asserted-by":"crossref","DOI":"10.1145\/2003476.2003484","volume-title":"Bellman\u2019s GAP: A 2nd Generation Language and System for Algebraic Dynamic Programming","author":"Sauthoff","year":"2011"},{"key":"2023051607332898800_btt022-B18","doi-asserted-by":"crossref","DOI":"10.1145\/2003476.2003484","article-title":"Bellman\u2019s GAP: a declarative language for dynamic programming","volume-title":"Proceedings of the 13th International ACM SIGPLAN Symposium on Principles and Practices of Declarative Programming","author":"Sauthoff","year":"2011"},{"key":"2023051607332898800_btt022-B19","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1093\/bioinformatics\/btk010","article-title":"RNAshapes: an integrated RNA analysis package based on abstract shapes","volume":"22","author":"Steffen","year":"2006","journal-title":"Bioinformatics"},{"key":"2023051607332898800_btt022-B20","first-page":"52","article-title":"Prediction of RNA secondary structure including kissing hairpin motifs","volume-title":"Proceedings of the 10th Workshop on Algorithms in Bioinformatics (WABI 2010) LNBI 6293","author":"Theis","year":"2010"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/5\/551\/50335812\/bioinformatics_29_5_551.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/5\/551\/50335812\/bioinformatics_29_5_551.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T07:58:17Z","timestamp":1684223897000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/29\/5\/551\/254334"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1,25]]},"references-count":20,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2013,3,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btt022","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2013,3,1]]},"published":{"date-parts":[[2013,1,25]]}}}