@Article{Moehl:Sparsification:AMB2011,
   author =	 {Mathias M{\"o}hl and Raheleh Salari and Sebastian Will and Rolf Backofen and S. Cenk Sahinalp},
  title =	 {Sparsification of {RNA} structure prediction including 
                  pseudoknots},
  journal =	 {Algorithms Mol Biol},
  year =	 {2010},
  issn = 	 {1748-7188},
  volume =	 {5},
  number =	 {1},
  pages =	 {39},
  user =	 {mmohl},
  pmid =	 {21194463},
  doi = 	 {10.1186/1748-7188-5-39},
  abstract =	 {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: 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. CONCLUSION: 
                  Experimental results on the sparsified Reeder-Giegerich 
                  algorithm suggest a linear speedup over the unsparsified 
                  implementation.}
}