A Genetic Algorithm for RNA Secondary Structure Prediction using Stacking Energy Thermodynamic Models

Candidate: Alain Deschenes
Type: Master of Science (MSc), School of Interactive Arts and Technology
Date: April 18, 2005
Senior Supervisor: Kay Wiese
Thesis: Download Thesis Document

Abstract

RNA structure is an important field of study. Predicting structure can overcome many of the issues with physical structure determination. Structure prediction can be simplified as an energy minimization problem. Common optimization techniques are the DPA and the GA. RnaPredict is a GA used for RNA secondary structure prediction using energy minimization and is evolved from Dr. Wiese's lab. Selection, recombination, mutation, and elitism are used to optimize the candidate structures in a population. Candidate solutions get closer to the global energy optimum with each generation. This thesis focuses on the addition of a hydrogen bond model and two stacking energy models, and studies their relative merits. It also studies different types of encoding used in the GA. The prediction accuracy is compared with known structures, the Nussinov DPA predictions and the mfold DPA predictions. RnaPredict is able to predict more accurate structures than Nussinov and performs similarly to mfold.