@inproceedings{Moehl:Schmiedl:Zakov:SparsificationADP:2011,
  author =	 {M{\"o}hl, Mathias and Schmiedl, Christina and Zakov,
                  Shay},
  title =	 {Sparsification in Algebraic Dynamic Programming},
  booktitle =	 {Proceedings of the German Conference on
                  Bioinformatics (GCB 2011)},
  year =	 2011,
  abstract =	 {Sparsification is a technique to speed up dynamic
                  programming algorithms which has been suc- cessfully
                  applied to RNA structure prediction,
                  RNA-RNA-interaction prediction, simultaneous align-
                  ment and folding, and pseudoknot prediction. So far,
                  sparsification has been more a collection of loosely
                  related examples and no general, well understood
                  theory. In this work we propose a general theory to
                  describe and implement sparsification in dynamic
                  programming algorithms. The approach is formalized
                  as an extension of Algebraic Dynamic Programming
                  (ADP) which makes it applicable to a variety of
                  algorithms and scoring schemes. In particular, this
                  is the first approach that shows how to sparsify
                  algorithms with scoring schemes that go beyond
                  simple minimization or maximiza- tion, like
                  enumeration of suboptimal solutions and
                  approximation of the partition function. As an
                  example, we show how to sparsify different variants
                  of RNA structure prediction algorithms.},
  user =	 {mmohl}
}