A parallel evolutionary algorithm for RNA secondary structure prediction

Candidate: Andrew Hendriks
Type: Master of Science (MSc), School of Interactive Arts and Technology
Date: July 4, 2005
Senior Supervisor: Kay Wiese
Thesis: Download Thesis Document

Abstract

RNA is central in several stages of protein synthesis, and also has structural and functional roles in the cell. The shape of organic molecules such as RNA largely determines their function within an organic system. Current physical methods for structure determination are time consuming and expensive, thus methods for the computational prediction of structure are sought after. Various algorithms that have been used for RNA structure prediction include dynamic programming and comparative methods. This thesis introduces P-RnaPredict, a fully parallel coarse-grained distributed genetic algorithm (GA) for RNA secondary structure prediction. The impact of three pseudorandom number generators (PRNGs) on P-RnaPredict's performance is evaluated. The parallel speedup of P-RnaPredict is analyzed. Finally, the prediction accuracy of P-RnaPredict is evaluated through comparison to ten known structures, and compared to structures predicted by a
Nussinov DPA implementation and the mfold DPA. P-RnaPredict offers similar performance to mfold, and outperforms the Nussinov DPA.