Comparing methods for rna secondary structure prediction minimizing the free energy

Abstract

The behaviour of an RNA molecule is directly linked to its secondary and tertiary structures. However, it has been proved that the secondary structure prediction problem with arbitrary pseudoknots is an NP-complete problem. In this paper, we present a comparative study of three algorithms based on the dynamic programming technique. The Nussinov and Zuker algorithms predict secondary structures without pseudoknots, whereas Akutsu algorithm does it with simple pseudoknots. We also present a metaheuristic that uses a genetic algorithm to produce quasi-optimal substructures which in turn allow the prediction of secondary structures with simple pseudoknots. Finally, we present an experimental analysis of the four algorithms using public instances of RNA structures provided by RNA STRAND and PseudoBase ++ databases.