Pareto optimization in algebraic dynamic programming

Saule C, Giegerich R (2015)
Algorithms for Molecular Biology 10: 22.

Download
OA
Journal Article | Published | English
Abstract
Pareto optimization combines independent objectives by computing the Pareto front of its search space, defined as the set of all solutions for which no other candidate solution scores better under all objectives. This gives, in a precise sense, better information than an artificial amalgamation of different scores into a single objective, but is more costly to compute. Pareto optimization naturally occurs with genetic algorithms, albeit in a heuristic fashion. Non-heuristic Pareto optimization so far has been used only with a few applications in bioinformatics. We study exact Pareto optimization for two objectives in a dynamic programming framework. We define a binary Pareto product operator ∗Par on arbitrary scoring schemes. Independent of a particular algorithm, we prove that for two scoring schemes A and B used in dynamic programming, the scoring scheme A∗ParB correctly performs Pareto optimization over the same search space. We study different implementations of the Pareto operator with respect to their asymptotic and empirical efficiency. Without artificial amalgamation of objectives, and with no heuristics involved, Pareto optimization is faster than computing the same number of answers separately for each objective. For RNA structure prediction under the minimum free energy versus the maximum expected accuracy model, we show that the empirical size of the Pareto front remains within reasonable bounds. Pareto optimization lends itself to the comparative investigation of the behavior of two alternative scoring schemes for the same purpose. For the above scoring schemes, we observe that the Pareto front can be seen as a composition of a few macrostates, each consisting of several microstates that differ in the same limited way. We also study the relationship between abstract shape analysis and the Pareto front, and find that they extract information of a different nature from the folding space and can be meaningfully combined.
Publishing Year
ISSN
Financial disclosure
Article Processing Charge funded by the Deutsche Forschungsgemeinschaft and the Open Access Publication Fund of Bielefeld University.
PUB-ID

Cite this

Saule C, Giegerich R. Pareto optimization in algebraic dynamic programming. Algorithms for Molecular Biology. 2015;10: 22.
Saule, C., & Giegerich, R. (2015). Pareto optimization in algebraic dynamic programming. Algorithms for Molecular Biology, 10: 22.
Saule, C., and Giegerich, R. (2015). Pareto optimization in algebraic dynamic programming. Algorithms for Molecular Biology 10:22.
Saule, C., & Giegerich, R., 2015. Pareto optimization in algebraic dynamic programming. Algorithms for Molecular Biology, 10: 22.
C. Saule and R. Giegerich, “Pareto optimization in algebraic dynamic programming”, Algorithms for Molecular Biology, vol. 10, 2015, : 22.
Saule, C., Giegerich, R.: Pareto optimization in algebraic dynamic programming. Algorithms for Molecular Biology. 10, : 22 (2015).
Saule, Cedric, and Giegerich, Robert. “Pareto optimization in algebraic dynamic programming”. Algorithms for Molecular Biology 10 (2015): 22.
Main File(s)
Access Level
OA Open Access
Last Uploaded
2016-02-26T07:02:50Z

This data publication is cited in the following publications:
This publication cites the following data publications:

38 References

Data provided by Europe PubMed Central.

finding on the maxima of a set of vectors
Kung H, Luccio F, Preparata F., 1975

AUTHOR UNKNOWN, 0

AUTHOR UNKNOWN, 0
Yield grammar analysis and product optimization in a domain-specific language for dynamic programming
Sauthoff G, Giegerich R., 2014

AUTHOR UNKNOWN, 0
Monotonicity and the principle of optimality
Morin TL., 1982
On quantitative effects of RNA shape abstraction.
Nebel ME, Scheid A., Theory Biosci. 128(4), 2009
PMID: 19756808
Computational approaches for RNA energy parameter estimation.
Andronescu M, Condon A, Hoos HH, Mathews DH, Murphy KP., RNA 16(12), 2010
PMID: 20940338
Rfam 11.0: 10 years of RNA families
Burge SW, Daub J, Eberhardt R, Tate J, Barquist L, Nawrocki EP., 2012

AUTHOR UNKNOWN, 0

AUTHOR UNKNOWN, 0
RNAmovies: visualizing RNA secondary structure spaces
Giegerich R, Evers DJ., 1999

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Sources

PMID: 26150892
PubMed | Europe PMC

Search this title in

Google Scholar