Evolutionary Strategy to Enhance an RNA Design Tool Performance

Abstract

At present, designing an RNA sequence that folds into a specific secondary structure is a problem that is not fully solved, due to its exponentially increasing complexity. To address this matter, many computational methods have been developed, but none of them has been able to completely and in an affordable time solve Eterna100, a widely recognized benchmark used to test the performance of RNA inverse folding algorithms. In previous publications we presented the m2dRNAs tool, a Multiobjective Evolutionary Algorithm, and its extension eM2dRNAs, which added a recursive decomposition of the target structure, thus simplifying the problem. At that time they successfully improved the ability to solve the RNA inverse folding problem, but were still unable to complete the Eterna100 benchmark. Here we introduce ES+eM2dRNAs, an improvement of eM2dRNAs that optimizes the decomposition process, as a drawback in its nature was identified.A comparative study of this new tool against its predecessors and other RNA design methods was performed using the two current versions of the Eterna100 benchmark. ES+eM2dRNAs was shown to be the best in all performance indicators considered (number of structures solved, success rate, and total run time). Moreover, it is able to solve two Eterna100 structures for which none of the compared methods had ever found a solution.

Keywords

• Bioinformatics
• evolutionary strategy
• genetic algorithm
• multiobjective evolutionary algorithm
• multiobjective optimization problem
• ncRNA design