A genetic algorithm for inferring pseudoknotted RNA structures from sequence data

Pseudoknotted RNA structures are much more difficult to predict than non-pseudoknotted RNA structures both from the computational viewpoint and from the practical viewpoint. This is in part due to the unavailability of an exact energy model for pseudoknots, structural complexity of pseudoknots, and to the high time complexity of predicting algorithms. Therefore, existing approaches to predicting pseudoknotted RNA structures mostly focus on so-called H-type pseudoknots of small RNAs. We have developed a heuristic energy model and genetic algorithm for predicting RNA structures with various types of pseudoknots, including H-type pseudoknots. This paper analyzes the predictions by a genetic algorithm and compares the predictions to those by a dynamic programming algorithm.