Resource type
Date created
2010
Authors/Contributors
Abstract
Background: Although many RNA molecules contain pseudoknots, computational prediction of pseudoknottedRNA structure is still in its infancy due to high running time and space consumption implied by the dynamicprogramming formulations of the problem.Results: In this paper, we introduce sparsification to significantly speedup the dynamic programming approachesfor pseudoknotted RNA structure prediction, which also lower the space requirements. Although sparsification hasbeen applied to a number of RNA-related structure prediction problems in the past few years, we provide the firstapplication of sparsification to pseudoknotted RNA structure prediction specifically and to handling gappedfragments more generally - which has a much more complex recursive structure than other problems to whichsparsification has been applied. We analyse how to sparsify four pseudoknot structure prediction algorithms,among those the most general method available (the Rivas-Eddy algorithm) and the fastest one (Reeder-Giegerichalgorithm). In all algorithms the number of “candidate” substructures to be considered is reduced.Conclusions: Our experimental results on the sparsified Reeder-Giegerich algorithm suggest a linear speedup overthe unsparsified implementation.
Document
Published as
Möhl et al. Algorithms for Molecular Biology 2010, 5:39
http://www.almob.org/content/5/1/39
http://www.almob.org/content/5/1/39
Publication details
Publication title
Algorithms for Molecular Biology
Document title
Sparsification of RNA Structure Prediction Including Pseudoknots
Date
2010
Volume
5
Issue
39
Published article URL
Copyright statement
Copyright is held by the author(s).
Scholarly level
Peer reviewed?
Yes
Language
English
Member of collection
Download file | Size |
---|---|
1748-7188-5-39.pdf | 617.09 KB |