SARNA-Predict: An Algorithm for RNA Folding: Based on Free Energy MinimizationTechniques, a Permutation-based Simulated Annealing Algorithm for Ribonucleic Acid Secondary Structure Prediction

Our knowledge of Ribonucleic Acid (RNA) importance is still expan­ding rapidly. RNA is no longer only a passive messenger of in-formation and scaffold for proteins, it has a central and active role in the functioning of the cell. There is a resurgence of interest in the RNA secondary structure prediction problem due to the discovery of many new families of non-coding RNAs with a variety of functions. This book describes and presents SARNA-Predict, 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 minimum in the solution space. Based on free energy minimization techniques, SARNA-Predict heuristically searches for the structure with a free energy close to the minimum free energy for a strand of RNA, within given constraints. Furthermore, SARNA-Predict has also been extended to predict RNA secondary structures with pseudoknots. Based on the performance evaluation in terms of prediction accuracy, SARNA-Predict can out-perform other state-of-the-art algorithms.