Saule, Cedric; Giegerich, Robert: Pareto optimization in algebraic dynamic programming. In: Algorithms for Molecular Biology. Jg.10 H. 1. 2015
Inhalt
- Pareto sets and the Pareto front operator
- Worst case and expected size of Pareto fronts
- Computing the Pareto front
- From an unsorted list
- From a lexicographically sorted list
- A smooth Pareto front algorithm for the general case
- Unsorted Pareto front computation
- Pareto operator complexity, revisited
- Pareto merge in linear time
- Pareto set extension
- Pareto optimization in ADP
- Algebraic framework
- Relation between Pareto and other products
- A hand-crafted use case of the Pareto product
- Sankoff problem signature and algebras
- Tree grammar for the Sankoff problem
- Calling the Sankoff program
- Preservation of Bellman’s principle by the Pareto product
- Implementation
- Standard implementation
- Lexicographically sorted implementation
- Pareto-eager implementation
- Runtime impact of Pareto front size
- Applications
- Evaluation goals
- Algorithms implemented
- Runtime and memory measurements
- Pareto front size
- Anti-correlation and real worst case behaviour
- Pareto solutions in the Sankoff algorithm
- Internal structure of the Pareto front of MFE and MEA folding
- Pareto optimization versus abtract shape analysis
- Conclusion
- Endnotes
- Authors’ contributions
- Received: 28 August 2014 Accepted: 7 May 2015References