Pareto optimization in algebraic dynamic programming.

Area of Science:

• Computational Biology
• Bioinformatics
• Algorithm Design

Background:

• Pareto optimization combines multiple objectives, offering richer insights than single-objective methods but is computationally intensive.
• Existing non-heuristic Pareto optimization is rarely applied in bioinformatics.
• Genetic algorithms often use heuristic Pareto optimization.

Purpose of the Study:

• To develop and analyze an exact, non-heuristic Pareto optimization framework for two objectives within a dynamic programming context.
• To introduce a binary Pareto product operator for combining scoring schemes.
• To evaluate the efficiency and applicability of this method in RNA structure prediction.

Main Methods:

• Defined a binary Pareto product operator for arbitrary scoring schemes.
• Developed a dynamic programming framework for exact Pareto optimization.
• Analyzed asymptotic and empirical efficiency of Pareto operator implementations.
• Applied the method to RNA structure prediction using minimum free energy and maximum expected accuracy models.

Main Results:

• Proved that the defined Pareto product operator correctly performs Pareto optimization.
• Demonstrated that this Pareto optimization is computationally faster than separate objective computations.
• Showed that the Pareto front size in RNA structure prediction remains manageable.
• Observed that the Pareto front comprises distinct macrostates and microstates.

Conclusions:

• Exact Pareto optimization offers a more efficient and informative approach compared to traditional methods for multi-objective problems in bioinformatics.
• The developed framework provides a valuable tool for comparative analysis of scoring schemes and understanding complex biological systems like RNA folding.
• Combining Pareto optimization with abstract shape analysis yields complementary insights into folding space.