HOME HELP FEEDBACK SUBSCRIPTIONS ARCHIVE SEARCH TABLE OF CONTENTS		QUICK SEARCH:   [advanced] Author: Keyword(s): Year:  Vol:  Page:

This Article Full Text Full Text (PDF) All Versions of this Article: rna.968808v1 14/4/630    most recent Alert me when this article is cited Alert me if a correction is posted Citation Map Services Email this article to a friend Similar articles in this journal Similar articles in PubMed Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Sperschneider, J. Articles by Datta, A. PubMed PubMed Citation Articles by Sperschneider, J. Articles by Datta, A. Social Bookmarking                   What's this?

KnotSeeker: Heuristic pseudoknot detection in long RNA sequences

¹ School of Computer Science and Software Engineering, University of Western Australia, Perth, WA 6009, Australia
² Institut für Informatik, Albert-Ludwigs-Universität Freiburg, 79085 Freiburg, Germany

Pseudoknots are folded structures in RNA molecules that perform essential functions as part of cellular transcription machinery and regulatory processes. The prediction of these structures in RNA molecules has important implications in antiviral drug design. It has been shown that the prediction of pseudoknots is an NP-complete problem. Practical structure prediction algorithms based on free energy minimization employ a restricted problem class and dynamic programming. However, these algorithms are computationally very expensive, and their accuracy deteriorates if the input sequence containing the pseudoknot is too long. Heuristic methods can be more efficient, but do not guarantee an optimal solution in regards to the minimum free energy model. We present KnotSeeker, a new heuristic algorithm for the detection of pseudoknots in RNA sequences as a preliminary step for structure prediction. Our method uses a hybrid sequence matching and free energy minimization approach to perform a screening of the primary sequence. We select short sequence fragments as possible candidates that may contain pseudoknots and verify them by using an existing dynamic programming algorithm and a minimum weight independent set calculation. KnotSeeker is significantly more accurate in detecting pseudoknots compared to other common methods as reported in the literature. It is very efficient and therefore a practical tool, especially for long sequences. The algorithm has been implemented in Python and it also uses C/C++ code from several other known techniques. The code is available from http://www.csse.uwa.edu.au/datta/pseudoknot.

Keywords: RNA pseudoknots; minimum free energy; dynamic programming; heuristic algorithms; minimum weight independent set; RNA structure prediction

CiteULike    Connotea    Del.icio.us    Digg    Reddit    Technorati    What's this?