Title: |
SARNA-Predict: A Simulated Annealing Algorithm for RNA Secondary Structure Prediction Herbert H. Tsang and Kay C. Wiese 2006 IEEE |
Speaker: | Hosna Jabbari |
Abstract |
Ribonucleic Acid (RNA) plays fundamental roles
in cellular processes and its structure is directly related to its
functions. This paper describes and presents a novel algorithm
for RNA secondary structure prediction based on Simulated
Annealing (SA). SA is known to be effective in solving many
different types of minimization problems and for finding the
global minima in the solution space. Based on free energy
minimization techniques, this permutation-based SA algorithm
heuristically searches for the structure with a free energy value
close to the minimum free energy $\Delta G $ for that strand, within
given constraints. A detailed study of the convergence behavior
of the algorithm is conducted and various cooling schedules
are investigated. An evaluation of the performance of the new
algorithm in terms of prediction accuracy is made via comparison
with the dynamic programming algorithm mfold for eight individual
known structures from three RNA classes (5S rRNA, Group
I intron 16S rRNA and 16S rRNA). The significant contribution
of this algorithm is in showing comparable results with the most
common dynamic programming prediction application mfold and
surpassing results from an Evolutionary Algorithm (EA).
|