Pareto optimization in algebraic dynamic programming
Saule C, Giegerich R (2015)
Algorithms for Molecular Biology 10(1): 22.
Zeitschriftenaufsatz
| Veröffentlicht | Englisch
Download
Autor*in
Einrichtung
Abstract / Bemerkung
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.
Stichworte
Algebraic dynamic programming;
Sankoff algorithm;
RNA structure;
Dynamic programming;
Pareto optimization
Erscheinungsjahr
2015
Zeitschriftentitel
Algorithms for Molecular Biology
Band
10
Ausgabe
1
Art.-Nr.
22
ISSN
1748-7188
Finanzierungs-Informationen
Open-Access-Publikationskosten wurden durch die Deutsche Forschungsgemeinschaft und die Universität Bielefeld gefördert.
Page URI
https://pub.uni-bielefeld.de/record/2763075
Zitieren
Saule C, Giegerich R. Pareto optimization in algebraic dynamic programming. Algorithms for Molecular Biology. 2015;10(1): 22.
Saule, C., & Giegerich, R. (2015). Pareto optimization in algebraic dynamic programming. Algorithms for Molecular Biology, 10(1), 22. doi:10.1186/s13015-015-0051-7
Saule, Cedric, and Giegerich, Robert. 2015. “Pareto optimization in algebraic dynamic programming”. Algorithms for Molecular Biology 10 (1): 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(1): 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.1 (2015): 22.
Alle Dateien verfügbar unter der/den folgenden Lizenz(en):
Copyright Statement:
Dieses Objekt ist durch das Urheberrecht und/oder verwandte Schutzrechte geschützt. [...]
Volltext(e)
Access Level
![Open access file OA](https://pub.uni-bielefeld.de/images/access_open.png)
Zuletzt Hochgeladen
2019-09-06T09:18:32Z
MD5 Prüfsumme
cb6d9a701a844e42ec6e3f79d76518f5
Daten bereitgestellt von European Bioinformatics Institute (EBI)
38 References
Daten bereitgestellt von Europe PubMed Central.
An improved algorithm for matching biological sequences.
Gotoh O., J. Mol. Biol. 162(3), 1982
PMID: 7166760
Gotoh O., J. Mol. Biol. 162(3), 1982
PMID: 7166760
A novel approach to remote homology detection: jumping alignments.
Spang R, Rehmsmeier M, Stoye J., J. Comput. Biol. 9(5), 2002
PMID: 12487762
Spang R, Rehmsmeier M, Stoye J., J. Comput. Biol. 9(5), 2002
PMID: 12487762
Simultaneous solutions of the RNA folding, alignment and proto-sequences problems
Sankoff D., 1985
Sankoff D., 1985
Finding the most significant common sequence and structure motifs in a set of RNA sequences.
Gorodkin J, Heyer LJ, Stormo GD., Nucleic Acids Res. 25(18), 1997
PMID: 9278497
Gorodkin J, Heyer LJ, Stormo GD., Nucleic Acids Res. 25(18), 1997
PMID: 9278497
The FOLDALIGN web server for pairwise structural RNA alignment and mutual motif search.
Havgaard JH, Lyngso RB, Gorodkin J., Nucleic Acids Res. 33(Web Server issue), 2005
PMID: 15980555
Havgaard JH, Lyngso RB, Gorodkin J., Nucleic Acids Res. 33(Web Server issue), 2005
PMID: 15980555
Predicting a set of minimal free energy RNA secondary structures common to two sequences.
Mathews DH., Bioinformatics 21(10), 2005
PMID: 15731207
Mathews DH., Bioinformatics 21(10), 2005
PMID: 15731207
A study of accessible motifs and RNA folding complexity.
Wexler Y, Zilberstein C, Ziv-Ukelson M., J. Comput. Biol. 14(6), 2007
PMID: 17691898
Wexler Y, Zilberstein C, Ziv-Ukelson M., J. Comput. Biol. 14(6), 2007
PMID: 17691898
Alignment of RNA base pairing probability matrices.
Hofacker IL, Bernhart SH, Stadler PF., Bioinformatics 20(14), 2004
PMID: 15073017
Hofacker IL, Bernhart SH, Stadler PF., Bioinformatics 20(14), 2004
PMID: 15073017
AUTHOR UNKNOWN, 0
Versatile and declarative dynamic programming using pair algebras.
Steffen P, Giegerich R., BMC Bioinformatics 6(), 2005
PMID: 16156887
Steffen P, Giegerich R., BMC Bioinformatics 6(), 2005
PMID: 16156887
Complete probabilistic analysis of RNA shapes.
Voss B, Giegerich R, Rehmsmeier M., BMC Biol. 4(), 2006
PMID: 16480488
Voss B, Giegerich R, Rehmsmeier M., BMC Biol. 4(), 2006
PMID: 16480488
Toward efficient multiple molecular sequence alignment: a system of genetic algorithm and dynamic programming.
Zhang C, Wong AC., IEEE Trans Syst Man Cybern B Cybern 27(6), 1997
PMID: 18263101
Zhang C, Wong AC., IEEE Trans Syst Man Cybern B Cybern 27(6), 1997
PMID: 18263101
Multi-objective pairwise RNA sequence alignment.
Taneda A., Bioinformatics 26(19), 2010
PMID: 20679330
Taneda A., Bioinformatics 26(19), 2010
PMID: 20679330
MODENA: a multi-objective RNA inverse folding
Taneda A., 2011
Taneda A., 2011
Multiclass gene selection using Pareto-fronts.
Rajapakse JC, Mundra PA., IEEE/ACM Trans Comput Biol Bioinform 10(1), 2013
PMID: 23702546
Rajapakse JC, Mundra PA., IEEE/ACM Trans Comput Biol Bioinform 10(1), 2013
PMID: 23702546
AUTHOR UNKNOWN, 0
The principle of optimality in dynamic programming with returns in partially ordered states
Henig MI., 1985
Henig MI., 1985
AUTHOR UNKNOWN, 0
Pareto optimal allocation and dynamic programming
Sitarz S., 2009
Sitarz S., 2009
Structural RNA alignment by multi-objective optimization.
Schnattinger T, Schoning U, Kestler HA., Bioinformatics 29(13), 2013
PMID: 23620356
Schnattinger T, Schoning U, Kestler HA., Bioinformatics 29(13), 2013
PMID: 23620356
RNA-Pareto: interactive analysis of Pareto-optimal RNA sequence-structure alignments.
Schnattinger T, Schoning U, Marchfelder A, Kestler HA., Bioinformatics 29(23), 2013
PMID: 24045774
Schnattinger T, Schoning U, Marchfelder A, Kestler HA., Bioinformatics 29(23), 2013
PMID: 24045774
Pareto-optimal phylogenetic tree reconciliation.
Libeskind-Hadas R, Wu YC, Bansal MS, Kellis M., Bioinformatics 30(12), 2014
PMID: 24932009
Libeskind-Hadas R, Wu YC, Bansal MS, Kellis M., Bioinformatics 30(12), 2014
PMID: 24932009
A discipline of dynamic programming over sequence data
Giegerich R, Meyer C, Steffen P., 2004
Giegerich R, Meyer C, Steffen P., 2004
Graham RL, Knuth DE, Patashnik O., 1994
AUTHOR UNKNOWN, 0
finding on the maxima of a set of vectors
Kung H, Luccio F, Preparata F., 1975
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
Sauthoff G, Giegerich R., 2014
AUTHOR UNKNOWN, 0
Monotonicity and the principle of optimality
Morin TL., 1982
Morin TL., 1982
On quantitative effects of RNA shape abstraction.
Nebel ME, Scheid A., Theory Biosci. 128(4), 2009
PMID: 19756808
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
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
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
Giegerich R, Evers DJ., 1999
The four ingredients of single-sequence RNA secondary structure prediction. A unifying perspective.
Rivas E., RNA Biol 10(7), 2013
PMID: 23695796
Rivas E., RNA Biol 10(7), 2013
PMID: 23695796
Export
Markieren/ Markierung löschen
Markierte Publikationen
Web of Science
Dieser Datensatz im Web of Science®Quellen
PMID: 26150892
PubMed | Europe PMC
Suchen in