Structural RNA alignment by multi-objective optimization.

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.