@inproceedings{Moehl:Will:Backofen:PKalign:RECOMB2009,
author = {Möhl, Mathias and Will, Sebastian and 
          Backofen, Rolf},
title = {Lifting Prediction to Alignment of {RNA}
         Pseudoknots},
booktitle = {RECOMB09},
year = {2009},
doi = {10.1089/cmb.2009.0168},
volume = {5541},
user = {will},
series = {LNBI},
publisher = {Springer},
pages = {285--301},
location = {Heidelberg},
isbn = {978-3-642-02007-0},
editor = {Serafim Batzoglou},
abstract = {Many computational problems concerning RNA
            pseudoknot structures, most prominently their
            prediction and alignment, are NP-hard. For structure
            prediction, several algorithms have been proposed
            that are restricted to certain classes of
            pseudoknots in order to run efficiently. We present
            a general scheme that yields an efficient alignment
            algorithm for arbitrary classes of pseudoknots that
            can be predicted efficiently by dynamic
            programming. Moreover, we show that such an
            alignment algorithm benefits from restrictions to
            certain structure classes in the same way as
            structure prediction algorithms do. We look at five
            of these classes in greater detail. Compared to the
            respective structure prediction algorithm, the time
            and space complexity of the obtained alignment
            algorithm is increased by only a linear factor. For
            four of the classes, there do not exist alignment
            algorithms so far. For the fifth, most general
            class, our algorithm improves the time complexity
            compared to the best algorithm known so far, from
            $O(n^5m^5)$ time to $O(nm^6)$, where $n$ and $m$ are
            the length of the two aligned sequences. Finally, we
            apply the fastest of the generated algorithms with
            complexity $O(nm^4)$ time and $O(nm^2)$ space to
            comparative de-novo prediction of pseudoknots.}
}