Comparison of dynamic programming and evolutionary algorithms for RNA secondary structure prediction

This work builds on previous research from an EA used to predict secondary structure of RNA molecules. The EA has the goal of predicting which canonical base pairs will form hydrogen bonds and helices. The addition of stacking energies, through INN and INN-HB, to our thermodynamic model has enhanced our predictions. We test three RNA sequences of lengths 118, 543, and 784 nucleotides using a variety of previously successful operators and parameter settings. The accuracy of the predicted structures are compared against those generated by the Nussinov DPA and also to known structures. The EA showed high accuracy of prediction especially on short sequences. On all tested sequences, the EA outperforms the Nussinov DPA.

I. Introduction

THE question of how macromolecules fold to attain specific shapes is fundamental to biology since the function of molecules is largely determined by structure [1]. Ribonucleic acid (RNA) is a molecule made up of a chain of nucleotides consisting of adenine (A), cytosine (C). guanine (G), and uracil (U), An RNA strand folds onto itself by forming hydrogen bonds between GC, AU, and GU, and their respective mirror images. It is widely believed that RNA molecules are closely related to the molecules from which life originally evolved.