SARNA-Predict: A Simulated Annealing Algorithm for RNA Secondary Structure Prediction

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 DeltaG 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)