A new algorithm for RNA secondary structure prediction and fast method for prediction of simple H-type pseudoknots

摘要

The base pairing of an RNA secondary structure is a sort of biological palindrome. In this paper we present a new algorithm for RNA secondary structure prediction. We introduce a new scoring table and trace back method to find longest biological palindrome from RNA secondary structure. After then we apply this method to predict RNA secondary structure with simple H-type pseudoknots. Our algorithms called "RNA longest Palindrome" and "Iterated RNA Longest Palindrome" has better space and time complexity than the previously known algorithms. The algorithms has a worst case complexity of O(N{sup}3), O(N{sup}4) in time and O(N{sup}2), O(N{sup}2) in storage respectively. In addition, our approach can be easily extended and applied to other classes of more general pseudoknots. Availability: The algorithm has been implemented in C++ in a program called "RNALP", which is available at http://dblab.cbu.ac.kr/～oyunerdene/rna.html.