Bioinformatics | Structure: RNA | Theory & Simulation
An O(n5) algorithm for predicting RNA kissing hairpins
Hosna Jabbari*, Anne Condon
*Corresponding author: Hosna Jabbari
Computer Science Department, University of British Columbia, Vancouver, BC, Canada
F1000 Posters 2011, 2: 260 (poster) [ENGLISH]
Poster [1.32 MB]
Presented at
15th Annual International Conference on Research in Computational Molecular Biology (RECOMB) 2011,
28 - 31 Mar 2011, 226
Our knowledge of the variety of functions played by RNA molecules in the cell continues to expand, with the functions determined in part by structure. To improve our ability to determine function from DNA or RNA sequences, and also to aid in the design of nucleic acids with novel structural or functional properties, accurate and efficient structure prediction methods are very valuable.
Currently, computational methods focus mostly on secondary structure prediction. Of particular interest, from a computational standpoint, is the prediction of pseudoknotted secondary structures.
A common approach of predicting secondary structures from the base sequence is to find the minimum free energy (MFE) structure. Since the general problem of MFE secondary structure prediction is NP-hard, polynomial-time algorithms handle a restricted class of secondary structures.
We present a novel MFE secondary structure prediction algorithm with respect to a thermodynamic model that encompasses the Turner model and significantly expands the class of structures handled in O(n5) time.
Our algorithm can handle biologically important examples including H-type pseudoknots, kissing hairpins (previously handled in O(n6) time) and chains of four pair wise overlapping stems, as well as nested sub-structures of these types which have not been handled by previous O(n5) algorithms.
No relevant conflicts of interest declared.
Please note that most posters on this site present work that is preliminary in nature and has not been peer reviewed.
This poster is open access subject to the Non-Commercial Creative Commons 3.0 License