Institute of Theoretical Computer Science, Ulm University, 89069 Ulm, Germany.
Bioinformatics. 2013 Jul 1;29(13):1607-13. doi: 10.1093/bioinformatics/btt188. Epub 2013 Apr 24.
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.
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.
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 data are available at Bioinformatics online.
对于结构化 RNA 的可靠比对计算仍被认为是一个未解决的问题。一种方法是通过将序列和结构成分的加权和作为目标函数，将二级结构信息纳入优化标准中。由于不清楚如何选择权重参数，我们使用多目标优化来计算一组帕累托最优的 RNA 序列-结构比对。该集合中的解决方案代表了不同目标之间的所有可能权衡，而不依赖于任何先前的权重。
我们提出了一种实用的多目标动态规划算法，这是计算成对 RNA 序列-结构比对问题的帕累托最优解集的新方法。在选定的示例中，我们展示了这种方法的有用性，以及它相对于最先进的单目标算法的优势。
我们的软件（ISO C++11）的源代码可在 http://sysbio.uni-ulm.de/?Software 上免费获得，并根据 GNU GPLv3 获得许可。
补充数据可在 Bioinformatics 在线获得。
