×

zbMATH — the first resource for mathematics

Integrating Pareto optimization into dynamic programming. (English) Zbl 07042321
Summary: Pareto optimization combines independent objectives by computing the Pareto front of the search space, yielding a set of optima where none scores better on all objectives than any other. Recently, it was shown that Pareto optimization seamlessly integrates with algebraic dynamic programming: when scoring schemes \(A\) and \(B\) can correctly evaluate the search space via dynamic programming, then so can Pareto optimization with respect to \(A\) and \(B\). However, the integration of Pareto optimization into dynamic programming opens a wide range of algorithmic alternatives, which we study in substantial detail in this article, using real-world applications in biosequence analysis, a field where dynamic programming is ubiquitous. Our results are two-fold: (1) We introduce the operation of a “Pareto algebra product” in the dynamic programming framework of Bellman’s GAP. Users of this framework can now ask for Pareto optimization with a single keystroke. Careful evaluation of the implementation alternatives by means of an extended Bellman’s GAP compiler demonstrates the dependence of the best implementation choice on the application at hand. (2) We extract from our experiments several pieces of advice to programmers who do not use a system such as Bellman’s GAP, but who choose to hand-craft their dynamic programming recurrences, incorporating Pareto optimization from scratch.

MSC:
90 Operations research, mathematical programming
68 Computer science
Software:
MODENA; Rfam; RNAalifold
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] ; Multiobjective Optimization, Interactive and Evolutionary Approaches (Outcome of Dagstuhl Seminars): Berlin, Germany; Heidelberg, Germany 2008; Volume Volume 5252 .
[2] Goodrich, M.T.; Pszona, P.; Two-Phase Bicriterion Search for Finding Fast and Efficient Electric Vehicle Routes; Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems: New York, NY, USA 2014; ,193-202.
[3] Müller-Hannemann, M.; Weihe, K.; Pareto Shortest Paths Is Often Feasible in Practice; Algorithm Engineering: Berlin, Germany; Heidelberg, Germany 2001; Volume Volume 2141 ,185-197. · Zbl 1002.68656
[4] Delling, D.; Pajor, T.; Werneck, R.F.; Round-Based Public Transit Routing; Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX’12), Society for Industrial and Applied Mathematics: ; .
[5] Rajapakse, J.; Mundra, P.; Multiclass gene selection using Pareto-fronts; IEEE/ACM Trans. Comput. Biol. Bioinform.: 2013; Volume 10 ,87-97.
[6] Taneda, A.; MODENA: A multi-objective RNA inverse folding; Adv. Appl. Bbioinform. Chem.: 2011; Volume 4 ,1-12.
[7] Zhang, C.; Wong, A.; Toward efficient molecular sequence alignment: A system of genetic algorithm and dynamic programming; Trans. Syst. Man Cybern. B Cybern.: 1997; Volume 27 ,918-932.
[8] Bellman, R.; ; Dynamic Programming: Princeton, NJ, USA 1957; . · Zbl 0077.13605
[9] Cormen, T.H.; Stein, C.; Rivest, R.L.; Leiserson, C.E.; ; Introduction to Algorithms: Cambridge, MA, USA and London, UK 2001; . · Zbl 1047.68161
[10] Durbin, R.; Eddy, S.R.; Krogh, A.; Mitchison, G.; ; Biological Sequence Analysis: Cambridge, UK 1998; . · Zbl 0929.92010
[11] Giegerich, R.; Touzet, H.; Modeling Dynamic Programming Problems over Sequences and Trees with Inverse Coupled Rewrite Systems; Algorithms: 2014; Volume 7 ,62-144. · Zbl 07042196
[12] Getachew, T.; Kostreva, M.; Lancaster, L.; A generalization of dynamic programming for Pareto optimization in dynamic networks; Revue Fr. Autom. Inform. Rech. Opér. Rech. Opér.: 2000; Volume 34 ,27-47. · Zbl 0963.90055
[13] Sitarz, S.; Pareto optimal allocation and dynamic programming; Ann. Oper. Res.: 2009; Volume 172 ,203-219. · Zbl 1184.90162
[14] Schnattinger, T.; Schoening, U.; Marchfelder, A.; Kestler, H.; Structural RNA alignment by multi-objective optimization; Bioinformatics: 2013; Volume 29 ,1607-1613.
[15] Schnattinger, T.; Schoening, U.; Marchfelder, A.; Kestler, H.; RNA-Pareto: Interactive analysis of Pareto-optimal RNA sequence-structure alignments; Bioinformatics: 2013; Volume 29 ,3102-3104.
[16] Libeskind-Hadas, R.; Wu, Y.C.; Bansal, M.; Kellis, M.; Pareto-optimal phylogenetic tree reconciliation; Bioinformatics: 2014; Volume 30 ,i87-i95.
[17] Giegerich, R.; Meyer, C.; Steffen, P.; A discipline of dynamic programming over sequence data; Sci. Comput. Program.: 2004; Volume 51 ,215-263. · Zbl 1067.90157
[18] Zu Siederdissen, C.H.; Sneaking around Concatmap: Efficient Combinators for Dynamic Programming; Proceedings of the 17th ACM SIGPLAN International Conference on Functional Programming, ICFP ’12: New York, NY, USA 2012; ,215-226. · Zbl 1291.68122
[19] Sauthoff, G.; Möhl, M.; Janssen, S.; Giegerich, R.; Bellman’s GAP—A Language and Compiler for Dynamic Programming in Sequence Analysis; Bioinformatics: 2013; Volume 29 ,551-560.
[20] Sauthoff, G.; Giegerich, R.; Yield grammar analysis and product optimization in a domain-specific language for dynamic programming; Sci. Comput. Program.: 2014; Volume 87 ,2-22.
[21] Saule, C.; Giegerich, R.; Pareto optimization in algebraic dynamic programming; Algorithms Mol. Biol.: 2015; Volume 10 ,22. · Zbl 07042321
[22] Graham, R.L.; Knuth, D.E.; Patashnik, O.; ; Concrete Mathematics: A Foundation for Computer Science: Boston, MA, USA 1994; . · Zbl 0836.00001
[23] Yukish, M.; Algorithms to Identify Pareto Points in Multi-Dimensional Data Sets; Ph.D. Thesis: University Park, PA, USA 2004; .
[24] Bentley, J.L.; Multidimensional Divide-and-Conquer; Commun. ACM: 1980; Volume 23 ,214-229. · Zbl 0434.68049
[25] Gotoh, O.; An Improved Algorithm for Matching Biological Sequences; J. Mol. Biol.: 1982; Volume 162 ,705-708.
[26] Sedgewick, R.; Implementing Quicksort Programs; Commun. ACM: 1978; Volume 21 ,847-857. · Zbl 0386.68058
[27] Brodal, G.S.; Fagerberg, R.; Moruz, G.; On the Adaptiveness of Quicksort; J. Exp. Algorithmics: 2008; Volume 12 ,3.2:1-3.2:20. · Zbl 1365.68190
[28] Dudzinski, K.; Dydek, A.; On a Stable Storage Merging Algorithm; Inf. Process. Lett.: 1981; Volume 12 ,5-8. · Zbl 0453.68037
[29] Gatter, T.; Integrating Pareto Optimization into the Dynamic Programming Framework Bellman’s GAP; Master’s Thesis: Bielefeld, Germany 2015; .
[30] Boost Timer Library; ; .
[31] Nawrocki, E.P.; Burge, S.W.; Bateman, A.; Daub, J.; Eberhardt, R.Y.; Eddy, S.R.; Floden, E.W.; Gardner, P.P.; Jones, T.A.; Tate, J.; Rfam 12.0: Updates to the RNA families database; Nucleic Acids Res.: 2015; Volume 43 ,D130-D137.
[32] Thompson, J.D.; Koehl, P.; Poch, O.; BAliBASE 3.0: Latest developments of the multiple sequence alignment benchmark; Proteins: 2005; Volume 61 ,127-136.
[33] Cordero, P.; Lucks, J.B.; Das, R.; An RNA Mapping DataBase for curating RNA structure mapping experiments; Bioinform.: 2012; Volume 28 ,3006-3008.
[34] Janssen, S.; Schudoma, C.; Steger, G.; Giegerich, R.; Lost in folding space? Comparing four variants of the thermodynamic model for RNA secondary structure prediction; BMC Bioinformatics: 2011; Volume 12 ,429.
[35] Xia, T.; SantaLucia, J.J.; Burkard, M.E.; Kierzek, R.; Schroeder, S.J.; Jiao, X.; Cox, C.; Turner, D.H.; Thermodynamic parameters for an expanded nearest-neighbor model for formation of RNA duplexes with Watson-Crick base pairs; Biochemistry: 1998; Volume 37 ,14719-14735.
[36] Mortimer, S.; Trapnell, C.; Aviran, S.; Pachter, L.; Lucks, J.; SHAPE-Seq: High-Throughput RNA Structure Analysis; Curr. Protoc. Chem. Biol.: 2012; Volume 4 ,275-297.
[37] Loughrey, D.; Watters, K.E.; Settle, A.H.; Lucks, J.B.; SHAPE-Seq 2.0: Systematic optimization and extension of high-throughput chemical probing of RNA secondary structure with next generation sequencing; Nucleic Acids Res.: 2014; Volume 42 .
[38] Ziehler, W.A.; Engelke, D.R.; Probing RNA Structure with Chemical Reagents and Enzymes; Curr. Protoc. Nucleic Acid Chem.: 2001; .
[39] Wells, S.E.; Hughes, J.M.; Igel, A.H.; Ares, M.J.; Use of dimethyl sulfate to probe RNA structure in vivo; Methods Enzymol.: 2000; Volume 318 ,479-493.
[40] Talkish, J.; May, G.; Lin, Y.; Woolford, J.L.; McManus, C.J.; Mod-seq: High-throuput sequencing for chemical probing of RNA structure; RNA: 2014; Volume 20 ,713-720.
[41] Gardner, P.P.; Giegerich, R.; A comprehensive comparison of comparative RNA structure prediction approaches; BMC Bioinform.: 2004; Volume 5 ,140.
[42] Saule, C.; Janssen, S.; Alternatives in integrating probing data in RNA secondary structure prediction; ; .
[43] Hofacker, I.L.; Bernhart, S.H.F.; Stadler, P.F.; Alignment of RNA base pairing probability matrices; Bioinformatics: 2004; Volume 20 ,2222-2227.
[44] Bernhart, S.; Hofacker, I.L.; Will, S.; Gruber, A.; Stadler, P.F.; RNAalifold: improved consensus structure prediction for RNA alignments; BMC Bioinform.: 2008; Volume 9 ,474.
[45] Janssen, S.; Giegerich, R.; Ambivalent covariance models; BMC Bioinform.: 2015; Volume 16 ,178.
[46] Sauthoff, G.; Bellman’s GAP: A 2nd Generation Language and System for Algebraic Dynamic Programming; Ph.D. Thesis: Bielefeld, Germany 2011; .
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.