# Integrating Pareto Optimization into Dynamic Programming
## 4 Experiments
### A Short Description of Tested Bioinformatics Applications  
To achieve both a varied and a representative benchmark, we used, in total, four biosequence analysis problems already implemented with [PERSON]'s GAP. In each case, we use a two-dimensional Pareto product and, if suitable, also a three- or four-dimensional product, totaling seven main test cases shown in Table 2. The applications Ali2D/3D, Fold2D/3D and Prob2D/4D address the task of RNA structure prediction, using the same tree grammar, but varying in the specified evaluation algebras. The application Gotoh performs sequence alignment under an affine gap model. More complete definitions are given later in this section. For each application, realistic test sets were downloaded from biogeochemical databases, and a subset of inputs of different sizes were manually extracted. For detailed analysis, a number of different inputs of varying sizes were tested. Where applicable, only representative results of preferably large inputs will be shown to lower the amount of data presented in this article. For each dimension and application, we additionally tested different combinations of algebras for each input, yielding no significant variation in our test set. Therefore, only a representative subset of Pareto products is shown here. Only inputs were chosen for which profiling data could be extracted within 5 days of computation time. While 5 days seems to be a rather long time frame and sufficient for many applications, as we shall see, this poses a strong restriction on Pareto optimization with more than two dimensions. The asymptotic complexity of the tested ADP applications can be described in terms of the initial input length \(n\), as well as the runtime \(p\) and the space \(s\) of the Pareto computations per subproblem. The Pareto front is computed once per table entry; therefore, complexities multiply. The fold programs' asymptotic complexity is \(O(n^{3}p)\) in time and \(O(n^{2}s)\) in space. The alignment program's asymptotic complexity is \(O(n^{2}p)\) in time and \(O(n^{2}s)\) in space. The input length will be given as the number of bases (characters) in the input sequence for the remainder of this work. Ali and Fold were tested on the the same inputs taken from Rfamseed alignments [31], which contains alignments of sequences known to produce stable structures. No special attention was given to the nature of the optimal structures, only to input length. The sequences and reactivities used to evaluate Prob originate from the RMDB [33]. The selected dataset contains 146 sequences, but only three could be taken under the condition of length and that data for three different reactivities was available. Gotoh2D was evaluated with BAliBASE 3.0 [32]. Again, sequences were chosen solely on length. [PERSON]'s algorithm: The test case Gotoh2D is an implementation of [PERSON]'s algorithm [25] that solves the pairwise sequence alignment problem, also known as string edit distance, for affine gap costs. For Gotoh2D, the gap initiation cost is combined with the gap extension cost in a Pareto product, and the results are printed as an alignment string via a lexicographic product. See our introductory example in Figure 1.  
RNA folding: The RNA folding space is defined by the \"Overdangle\" grammar first described by [PERSON] _et al._[34]. Depending on the application and the number of dimensions in the Pareto product, the folding space is evaluated with different algebras. For Fold2D, we use the minimum free energy (MFE), according to the Turner energy model [35], combined with the maximum expected accuracy (MEA) that consists of the accumulation of base pairs' probabilities computed with the partition function of the Turner model. For Fold3D, the maximization of the number of predicted base pairs (BP) is added to the Pareto product. In Prob, we study the integration of reactivity data in RNA secondary prediction with Pareto optimization.