@inproceedings{moehl_wabi10:Sparsification,
author = {Mö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},
doi = {10.1007/978-3-642-15294-8_4},
volume = {6293},
user = {mmohl},
series = {Lecture Notes in Computer Science},
publisher = {Springer Berlin / Heidelberg},
pages = {40-51},
editor = {Moulton, Vincent and Singh, Mona},
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.}
}