MOTIVATION: The calculation of reliable alignments for structured RNA is still considered as an open problem. One approach is the incorporation of secondary structure information into the optimization criteria by using a weighted sum of sequence and structure components as an objective function. As it is not clear how to choose the weighting parameters, we use multi-objective optimization to calculate a set of Pareto-optimal RNA sequence-structure alignments. The solutions in this set then represent all possible trade-offs between the different objectives, independent of any previous weighting. RESULTS: We present a practical multi-objective dynamic programming algorithm, which is a new method for the calculation of the set of Pareto-optimal solutions to the pairwise RNA sequence-structure alignment problem. In selected examples, we show the usefulness of this approach, and its advantages over state-of-the-art single-objective algorithms. AVAILABILITY AND IMPLEMENTATION: The source code of our software (ISO C++11) is freely available at http://sysbio.uni-ulm.de/?Software and is licensed under the GNU GPLv3. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Abstract Summary: Incorporating secondary structure information into the alignment process improves the quality of RNA sequence alignments. Instead of using fixed weighting parameters, sequence and structure components can be treated as different objectives and optimized simultaneously. The result is not a single, but a Pareto-set of equally optimal solutions, which all represent different possible weighting parameters. We now provide the interactive graphical software tool RNA-Pareto, which allows a direct inspection of all feasible results to the pairwise RNA sequence-structure alignment problem and greatly facilitates the exploration of the optimal solution set. Availability and implementation: The software is written in Java 6 (graphical user interface) and C++ (dynamic programming algorithms). The source code and binaries for Linux, Windows and Mac OS are freely available at http://sysbio.uni-ulm.de and are licensed under the GNU GPLv3. Contact: [email protected]