@InProceedings{moehl_wabi10:Sparsification,
  author =      {M{\"o}hl, Mathias and Salari, Raheleh and Will, Sebastian and
                 Backofen, Rolf and Sahinalp, S. Cenk},
  title =       {Sparsification of {RNA} Structure Prediction Including
                 Pseudoknots},
  booktitle =   {Proc. of the 10th Workshop on Algorithms in
                 Bioinformatics {(WABI)}},
  year =        {2010},
  series =      {Lecture Notes in Computer Science},
  editor =      {Moulton, Vincent and Singh, Mona},
  publisher =   {Springer Berlin / Heidelberg},
  pages =       {40-51},
  volume =      {6293},
  doi =         {10.1007/978-3-642-15294-8_4},
   abstract =   {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. 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 show that sparsification, when applied to
                the fastest, as well as the most general pseudoknotted structure
                prediction methods available, - respectively the
                Reeder-Giegerich algorithm and the Rivas-Eddy algorithm -
                reduces the number of candidate substructures to be considered
                significantly. In fact, experimental results on the sparsified
                Reeder-Giegerich algorithm suggest a linear speedup over the
                unsparsified implementation.},
  user =        {mmohl}
}