A hybrid evolutionary/clustering algorithm for RNA secondary structure prediction

The shape that organic molecules such as biopolymers form within organic systems largely determines the function said molecules perform. RNA is a biopolymer that plays a central part in several stages of protein synthesis, and also has structural, functional, and regulatory roles in the cell. In an ab initio case where only a single RNA sequence is determined, the most common structure prediction techniques employ minimization of the free energy of a given RNA molecule via a thermodynamic model. Regrettably, the minimum free energy structure is rarely the native structure; typically the native structure can be found within 5 percent of the minimum free energy. While suboptimal energy structures may also be predicted, there is no still no method to determine which suboptimal fold best represents the native fold. One possible technique is to apply clustering algorithms to a population of potential structures. This thesis presents the hybridization of an evolutionary algorithm (EA) with a clustering algorithm. The effects of two additional thermodynamic models on the EA, including a pseudoknot enabled model, are also investigated. Finally, the prediction sensitivity, specificity, and F-measure of RnaPredict is evaluated through comparison to known structures. Comparisons are also made with existing prediction algorithms including sfold, mfold, and HotKnots. RnaPredict offers comparable performance to these algorithms and can outperform these algorithms on specific sequences.