{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,16]],"date-time":"2025-12-16T11:53:26Z","timestamp":1765886006293},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2015,12]]},"DOI":"10.1186\/s13015-015-0051-7","type":"journal-article","created":{"date-parts":[[2015,7,6]],"date-time":"2015-07-06T06:04:00Z","timestamp":1436162640000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Pareto optimization in algebraic dynamic programming"],"prefix":"10.1186","volume":"10","author":[{"given":"C\u00e9dric","family":"Saule","sequence":"first","affiliation":[]},{"given":"Robert","family":"Giegerich","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,7,7]]},"reference":[{"key":"51_CR1","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1016\/0022-2836(82)90398-9","volume":"162","author":"O Gotoh","year":"1982","unstructured":"Gotoh O (1982) An improved algorithm for matching biological sequences. J Mol Biol 162:705\u2013708","journal-title":"J Mol Biol"},{"issue":"5","key":"51_CR2","doi-asserted-by":"crossref","first-page":"747","DOI":"10.1089\/106652702761034172","volume":"9","author":"R Spang","year":"2002","unstructured":"Spang R, Rehmsmeier M, Stoye J (2002) A novel approach to remote homology detection: jumping alignments. J Comput Biol 9(5):747\u2013760","journal-title":"J Comput Biol"},{"issue":"5","key":"51_CR3","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1137\/0145048","volume":"45","author":"D Sankoff","year":"1985","unstructured":"Sankoff D (1985) Simultaneous solutions of the RNA folding, alignment and proto-sequences problems. SIAM J Appl Math 45(5):810\u2013825","journal-title":"SIAM J Appl Math"},{"issue":"18","key":"51_CR4","doi-asserted-by":"crossref","first-page":"3724","DOI":"10.1093\/nar\/25.18.3724","volume":"25","author":"J Gorodkin","year":"1997","unstructured":"Gorodkin J, Heyer LJ, Stormo GD (1997) Finding the most significant common sequence and structure motifs in a set of RNA sequences. Nucleic Acid Res 25(18):3724\u20133732","journal-title":"Nucleic Acid Res"},{"key":"51_CR5","doi-asserted-by":"crossref","first-page":"650","DOI":"10.1093\/nar\/gki473","volume":"33","author":"JH Havgaard","year":"2005","unstructured":"Havgaard JH, Lyngs\u00f8 RB, Gorodkin J (2005) The FOLDALIGN web server for pairwise structural RNA alignment and mutual motif search. Nucleic Acid Res 33:650\u2013653","journal-title":"Nucleic Acid Res"},{"issue":"10","key":"51_CR6","doi-asserted-by":"crossref","first-page":"2246","DOI":"10.1093\/bioinformatics\/bti349","volume":"21","author":"DH Mathews","year":"2005","unstructured":"Mathews DH (2005) Predicting a set of minimal free energy RNA secondary structures common to two sequences. Bioinformatics 21(10):2246\u20132253","journal-title":"Bioinformatics"},{"issue":"6","key":"51_CR7","doi-asserted-by":"crossref","first-page":"856","DOI":"10.1089\/cmb.2007.R020","volume":"14","author":"Y Wexler","year":"2007","unstructured":"Wexler Y, Zilberstein C, Ziv-Ukelson M (2007) A study of accessible motifs and RNA folding complexity. J Comput Biol 14(6):856\u2013872","journal-title":"J Comput Biol"},{"issue":"14","key":"51_CR8","doi-asserted-by":"crossref","first-page":"2222","DOI":"10.1093\/bioinformatics\/bth229","volume":"20","author":"IL Hofacker","year":"2004","unstructured":"Hofacker IL, Bernhart SHF, Stadler PF (2004) Alignment of RNA base pairing probabilities matrices. Bioinformatics 20(14):2222\u20132227","journal-title":"Bioinformatics"},{"key":"51_CR9","unstructured":"Schnattinger T (2014) Multi-objective optimization for RNA folding, alignment and phylogeny. PhD thesis, Fakult\u00e4t f\u00fcr Ingenieurwissenschaften und Informatik der Universit\u00e4t Ulm"},{"issue":"1","key":"51_CR10","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1186\/1471-2105-6-224","volume":"6","author":"P Steffen","year":"2005","unstructured":"Steffen P, Giegerich R (2005) Versatile and declarative dynamic programming using pair algebras. BMC Bioinform 6(1):224. doi: 10.1186\/1471-2105-6-224","journal-title":"BMC Bioinform"},{"issue":"1","key":"51_CR11","doi-asserted-by":"crossref","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 (2006) Complete probabilistic analysis of RNA shapes. BMC Biol 4(1):5. doi: 10.1186\/1741-7007-4-5","journal-title":"BMC Biol"},{"issue":"6","key":"51_CR12","doi-asserted-by":"crossref","first-page":"918","DOI":"10.1109\/3477.650054","volume":"27","author":"C Zhang","year":"1997","unstructured":"Zhang C, Wong AKC (1997) Toward efficient molecular sequence alignment: a system of genetic algorithm and dynamic programming. Trans Syst Man Cybern Part B Cybern 27(6):918\u2013932","journal-title":"Trans Syst Man Cybern Part B Cybern"},{"issue":"19","key":"51_CR13","doi-asserted-by":"crossref","first-page":"2383","DOI":"10.1093\/bioinformatics\/btq439","volume":"26","author":"A Taneda","year":"2010","unstructured":"Taneda A (2010) Multi-objective pairwise RNA sequence alignment. Bioinformatics 26(19):2383\u20132390","journal-title":"Bioinformatics"},{"key":"51_CR14","first-page":"1","volume":"4","author":"A Taneda","year":"2011","unstructured":"Taneda A (2011) MODENA: a multi-objective RNA inverse folding. Adv Appl Bbioinform Chem 4:1\u201312","journal-title":"Adv Appl Bbioinform Chem"},{"issue":"1","key":"51_CR15","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1109\/TCBB.2013.1","volume":"10","author":"JC Rajapakse","year":"2013","unstructured":"Rajapakse JC, Mundra PA (2013) Multiclass gene selection using Pareto-fronts. IEEE\/ACM Trans Comput Biol Bioinform 10(1):87\u201397","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"key":"51_CR16","doi-asserted-by":"crossref","unstructured":"Forman G (2004) A pitfall and solution in multi-class feature selection for text classification. In: Proceedings of the 21th International Conference on Machine Learning","DOI":"10.1145\/1015330.1015356"},{"issue":"3","key":"51_CR17","first-page":"462","volume":"10","author":"MI Henig","year":"1985","unstructured":"Henig MI (1985) The principle of optimality in dynamic programming with returns in partially ordered states. Inst Op Res Manag Sci 10(3):462\u2013470","journal-title":"Inst Op Res Manag Sci"},{"key":"51_CR18","doi-asserted-by":"crossref","unstructured":"Getachew T, Kostreva M, Lancaster L (2000) A generalization of dynamic programming for Pareto optimization in dynamic networks. Revue Fran\u00e7aise d\u2019Automatique, d\u2019Informatique et de Recherche op\u00e9rationnelle. Recherche Op\u00e9rationelle 34(1):27\u201347","DOI":"10.1051\/ro:2000100"},{"key":"51_CR19","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/s10479-009-0558-8","volume":"172","author":"S Sitarz","year":"2009","unstructured":"Sitarz S (2009) Pareto optimal allocation and dynamic programming. Ann Op Res 172:203\u2013219","journal-title":"Ann Op Res"},{"issue":"13","key":"51_CR20","doi-asserted-by":"crossref","first-page":"1607","DOI":"10.1093\/bioinformatics\/btt188","volume":"29","author":"T Schnattinger","year":"2013","unstructured":"Schnattinger T, Sch\u00f6ning U, Marchfelder A, Kestler HA (2013) Structural RNA alignment by multi-objective optimization. Bioinformatics 29(13):1607\u20131613","journal-title":"Bioinformatics"},{"issue":"23","key":"51_CR21","doi-asserted-by":"crossref","first-page":"3102","DOI":"10.1093\/bioinformatics\/btt536","volume":"29","author":"T Schnattinger","year":"2013","unstructured":"Schnattinger T, Sch\u00f6ning U, Marchfelder A, Kestler HA (2013) RNA-Pareto: interactive analysis of Pareto-optimal RNA sequence-structure alignments. Bioinformatics 29(23):3102\u20133104","journal-title":"Bioinformatics"},{"issue":"12","key":"51_CR22","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1093\/bioinformatics\/btu289","volume":"30","author":"R Libeskind-Hadas","year":"2014","unstructured":"Libeskind-Hadas R, Wu Y-C, Bansal MS, Kellis M (2014) Pareto-optimal phylogenetic tree reconciliation. Bioinformatics 30(12):87\u201395","journal-title":"Bioinformatics"},{"issue":"3","key":"51_CR23","doi-asserted-by":"crossref","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 (2004) A discipline of dynamic programming over sequence data. Sci Comput Program 51(3):215\u2013263. doi: 10.1016\/j.scico.2003.12.005","journal-title":"Sci Comput Program"},{"key":"51_CR24","volume-title":"Concrete mathematics: a foundation for computer science","author":"RL Graham","year":"1994","unstructured":"Graham RL, Knuth DE, Patashnik O (1994) Concrete mathematics: a foundation for computer science, 2nd edn. Addison-Wesley Longman Publishing Co., Inc, Boston","edition":"2"},{"key":"51_CR25","doi-asserted-by":"crossref","unstructured":"Yukish MA (2004) Algorithms to identify Pareto points in multi-dimensional data sets. PhD thesis, Pennsylvania State University, Graduate School, College of Engineering","DOI":"10.2514\/6.2004-4324"},{"issue":"4","key":"51_CR26","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1145\/321906.321910","volume":"4","author":"H Kung","year":"1975","unstructured":"Kung H, Luccio F, Preparata F (1975) $${\\cal O}(n)$$ O ( n ) finding on the maxima of a set of vectors. J Assoc Comput Mach 4(4):469\u2013476","journal-title":"J Assoc Comput Mach"},{"key":"51_CR27","doi-asserted-by":"crossref","unstructured":"zu Siederdissen CH (2012) Sneaking around concatMap: efficient combinators for dynamic programming. In: Proceedings of the 17th ACM SIGPLAN International Conference on Functional Programming. ICFP \u201912, pp 215\u2013226. ACM, New York, NY, USA. doi: 10.1145\/2364527.2364559","DOI":"10.1145\/2364527.2364559"},{"key":"51_CR28","doi-asserted-by":"crossref","unstructured":"Sauthoff G, M\u00f6hl M, Janssen S, Giegerich R (2013) Bellman\u2019s GAP\u2014a language and compiler for dynamic programming in sequence analysis. Bioinformatics 29(5):551\u2013560. doi: 10.1093\/bioinformatics\/btt022 . http:\/\/bioinformatics.oxfordjournals.org\/content\/early\/2013\/01\/25\/bioinformatics.btt022.full.pdf+html","DOI":"10.1093\/bioinformatics\/btt022"},{"key":"51_CR29","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.scico.2013.09.011","volume":"87","author":"G Sauthoff","year":"2014","unstructured":"Sauthoff G, Giegerich R (2014) Yield grammar analysis and product optimization in a domain-specific language for dynamic programming. Sci Comput Program 87:2\u201322. doi: 10.1016\/j.scico.2013.09.011","journal-title":"Sci Comput Program"},{"key":"51_CR30","doi-asserted-by":"crossref","unstructured":"Sauthoff G, Janssen S, Giegerich R (2011) Bellman\u2019s GAP: a declarative language for dynamic programming. In: Proceedings of the 13th International ACM SIGPLAN Symposium on Principles and Practices of Declarative Programming. PPDP \u201911, pp 29\u201340. ACM, New York, NY, USA. doi: 10.1145\/2003476.2003484","DOI":"10.1145\/2003476.2003484"},{"key":"51_CR31","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1016\/0022-247X(82)90223-2","volume":"86","author":"TL Morin","year":"1982","unstructured":"Morin TL (1982) Monotonicity and the principle of optimality. J Math Anal Appl 86:665\u2013674","journal-title":"J Math Anal Appl"},{"key":"51_CR32","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/s12064-009-0074-z","volume":"128","author":"M Nebel","year":"2009","unstructured":"Nebel M, Scheid A (2009) On quantitative effects of RNA shape abstraction. Theory Biosci 128:211\u2013225. doi: 10.1007\/s12064-009-0074-z","journal-title":"Theory Biosci"},{"key":"51_CR33","doi-asserted-by":"crossref","first-page":"2304","DOI":"10.1261\/rna.1950510","volume":"16","author":"M Andronescu","year":"2010","unstructured":"Andronescu M, Condon A, Hoos HH, Mathews DH, Murphy KP (2010) Computational approaches for RNA energy parameter estimation. RNA 16:2304\u20132316","journal-title":"RNA"},{"key":"51_CR34","author":"SW Burge","year":"2012","unstructured":"Burge SW, Daub J, Eberhardt R, Tate J, Barquist L, Nawrocki EP et al (2012) Rfam 11.0: 10 years of RNA families. Nucleic Acid Res. doi: 10.1093\/nar\/gks1005","journal-title":"Nucleic Acid Res"},{"key":"51_CR35","doi-asserted-by":"crossref","unstructured":"Janssen S, Schudoma C, Steger G, Giegerich R (2011) Lost in folding space? Comparing four variants of the thermodynamic model for RNA secondary structure prediction. BMC Bioinform 12(429). doi: 10.1186\/1471-2105-12-429","DOI":"10.1186\/1471-2105-12-429"},{"key":"51_CR36","unstructured":"Mostaghim S, Teich J (2003) Quad-trees: a data structure for storing Pareto-sets in multi-objective evolutionary algorithms with elitism. In: In evolutionary computation based multi-criteria optimization: theoretical advances and applications"},{"key":"51_CR37","first-page":"32","volume":"15","author":"R Giegerich","year":"1999","unstructured":"Giegerich R, Evers DJ (1999) RNAmovies: visualizing RNA secondary structure spaces. Bioinform Former CABIOS 15:32\u201337","journal-title":"Bioinform Former CABIOS"},{"issue":"7","key":"51_CR38","doi-asserted-by":"crossref","first-page":"1185","DOI":"10.4161\/rna.24971","volume":"10","author":"E Rivas","year":"2013","unstructured":"Rivas E (2013) The four ingredients of single-sequence RNA secondary structure prediction. A unifying perspective. RNA Biol 10(7):1185","journal-title":"RNA Bio"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-015-0051-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,27]],"date-time":"2019-08-27T20:59:40Z","timestamp":1566939580000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.almob.org\/content\/10\/1\/22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,7]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,12]]}},"alternative-id":["51"],"URL":"https:\/\/doi.org\/10.1186\/s13015-015-0051-7","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,7,7]]},"article-number":"22"}}