By Rosalia Aguirre-Hernandez (joint work with Holger Hoos and Anne Condon)

Ribonucleic acids (RNA) are macromolecules that play fundamental roles in many biological processes and their structure is essential for their biological function. This work is focused on the design of RNA strands that is predicted to fold to a given secondary structure, according to a standard thermodynamic model such as that of Mathews et al. This problem is relevant because it will facilitate the characterization of biological RNAs by their function and the design of new ribozymes that can be used as therapeutic agents. There are also applications in nanobiotechnology in the context of building self-assembling structures from small RNA molecules.

One solution to the RNA secondary structure design problem is provided by Hofacker et al., the implementation of which is included in the Vienna RNA Secondary Structure Package. A more recent stochastic local search algorithm, the RNA Designer of Andronescu et al. shows a better performance.

The purpose of this work is to understand better the factors that make RNA structures hard to design. Such understanding provides the basis for improving the performance of RNA Designer and for characterizing its limitations. I will describe a modification of the RNA Designer that improves the performance of the algorithm. Furthermore, it is not known whether there is a polynomial time algorithm for RNA secondary structure design. Therefore, to gain insights into the practical complexity of the problem, I present a scaling analysis to investigate the hardness of the problem on random RNA structures using the improved RNA Designer. I found that the median expected run-time of both, RNA Designer and the Vienna algorithm scales polynomially with the size of the random structures. In future work, I will extend the analysis to biologically more realistic structures.