A hybrid clustering/evolutionary algorithm for RNA folding

RNA is central in several stages of protein synthesis, and also has structural, functional, and regulatory roles in the cell. The shape of organic molecules such as RNA largely determines their function within an organic system, thus methods for the computational prediction of structure are sought after. In the ab initio case where only the RNA sequence is known, the currently dominant structure prediction techniques employ minimization of the free energy of a given RNA molecule via a thermodynamic model. However, the minimum free energy structure is rarely the native structure; this is thought to be due to errors in the thermodynamic model parameters, which are experimentally determined. Cluster analysis performed by [6] on a sampling of structures from a Boltzmann weighted ensemble determined that the best cluster centroid had an improved sensitivity and significantly improved positive predictive value over the minimum free energy structure in the ensemble. Based on this result, we investigated the combination of an existing evolutionary algorithm for RNA secondary structure prediction with a clustering algorithm.