Cargando…

Pareto optimization in algebraic dynamic programming

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 d...

Descripción completa

Detalles Bibliográficos
Autores principales: Saule, Cédric, Giegerich, Robert
Formato: Online Artículo Texto
Lenguaje:English
Publicado: BioMed Central 2015
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4491898/
https://www.ncbi.nlm.nih.gov/pubmed/26150892
http://dx.doi.org/10.1186/s13015-015-0051-7
_version_ 1782379714497740800
author Saule, Cédric
Giegerich, Robert
author_facet Saule, Cédric
Giegerich, Robert
author_sort Saule, Cédric
collection PubMed
description 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 [Formula: see text] 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 [Formula: see text] 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. ELECTRONIC SUPPLEMENTARY MATERIAL: The online version of this article (doi:10.1186/s13015-015-0051-7) contains supplementary material, which is available to authorized users.
format Online
Article
Text
id pubmed-4491898
institution National Center for Biotechnology Information
language English
publishDate 2015
publisher BioMed Central
record_format MEDLINE/PubMed
spelling pubmed-44918982015-07-07 Pareto optimization in algebraic dynamic programming Saule, Cédric Giegerich, Robert Algorithms Mol Biol Research 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 [Formula: see text] 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 [Formula: see text] 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. ELECTRONIC SUPPLEMENTARY MATERIAL: The online version of this article (doi:10.1186/s13015-015-0051-7) contains supplementary material, which is available to authorized users. BioMed Central 2015-07-07 /pmc/articles/PMC4491898/ /pubmed/26150892 http://dx.doi.org/10.1186/s13015-015-0051-7 Text en © Saule and Giegerich. 2015 Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. The Creative Commons Public Domain Dedication waiver (http://creativecommons.org/publicdomain/zero/1.0/) applies to the data made available in this article, unless otherwise stated.
spellingShingle Research
Saule, Cédric
Giegerich, Robert
Pareto optimization in algebraic dynamic programming
title Pareto optimization in algebraic dynamic programming
title_full Pareto optimization in algebraic dynamic programming
title_fullStr Pareto optimization in algebraic dynamic programming
title_full_unstemmed Pareto optimization in algebraic dynamic programming
title_short Pareto optimization in algebraic dynamic programming
title_sort pareto optimization in algebraic dynamic programming
topic Research
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4491898/
https://www.ncbi.nlm.nih.gov/pubmed/26150892
http://dx.doi.org/10.1186/s13015-015-0051-7
work_keys_str_mv AT saulecedric paretooptimizationinalgebraicdynamicprogramming
AT giegerichrobert paretooptimizationinalgebraicdynamicprogramming