title: Sparsification of RNA structure prediction including pseudoknots.
abstract: BACKGROUND
  Although many RNA molecules contain pseudoknots, computational prediction of pseudoknotted RNA structure is still in its infancy due to high running time and space consumption implied by the dynamic programming formulations of the problem.
  
  
  RESULTS
  In this paper, we introduce sparsification to significantly speedup the dynamic programming approaches for pseudoknotted RNA structure prediction, which also lower the space requirements. Although sparsification has been applied to a number of RNA-related structure prediction problems in the past few years, we provide the first application of sparsification to pseudoknotted RNA structure prediction specifically and to handling gapped fragments more generally - which has a much more complex recursive structure than other problems to which sparsification 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-Giegerich algorithm). 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 over the unsparsified implementation.
authors.affiliation: Bioinformatics, Institute of Computer Science, Albert-Ludwigs-Universität, Freiburg, Germany.
authors.forename: Mathias
authors.initials: M
authors.lastname: Möhl
authors.affiliation: Lab for Computational Biology, School of Computing Science, Simon Fraser University, Burnaby, BC, Canada.
authors.forename: Raheleh
authors.initials: R
authors.lastname: Salari
authors.affiliation: Bioinformatics, Institute of Computer Science, Albert-Ludwigs-Universität, Freiburg, Germany.|Computation and Biology Lab, CSAIL, MIT, Cambridge MA, USA.
authors.forename: Sebastian
authors.initials: S
authors.lastname: Will
authors.affiliation: Bioinformatics, Institute of Computer Science, Albert-Ludwigs-Universität, Freiburg, Germany.|Centre for Biological Signalling Studies (bioss), Albert-Ludwigs-Universität, Freiburg, Germany.
authors.forename: Rolf
authors.initials: R
authors.lastname: Backofen
authors.affiliation: Lab for Computational Biology, School of Computing Science, Simon Fraser University, Burnaby, BC, Canada.
authors.forename: S Cenk
authors.initials: SC
authors.lastname: Sahinalp