A New Parameterized Algorithm for Predicting the Secondary Structure of RNA Sequences Including Pseudoknots

摘要

An important problem in structural bioinformatics is to determine the secondary structure of an RNA molecule from its primary sequence. The problem is nondeterministic polynomial time hard when the secondary structure of the sequence may contain pseudoknot structures. In this paper, we develop a parameterized algorithm that can efficiently predict the secondary structure of an RNA sequence that may contain pseudoknot structures with high accuracy. We use a graph model to describe the overlapping relationships of energetically stable stems in the sequence. A new structure parameter is identified for the graph. Based on this parameter, we develop a parameterized algorithm that can efficiently compute the most energetically favored secondary structure from the primary sequence of an RNA molecule. Our experiments show that the parameter is a small integer for many RNA molecules and our testing results also demonstrate the advantages of this new algorithm in prediction accuracy and computational efficiency over existing prediction tools.