@inproceedings{Moehl:Will:Backofen:CPM2008,
author = {Möhl, Mathias and Will, Sebastian and Backofen, Rolf},
title = {Fixed Parameter Tractable Alignment of {RNA}
         Structures Including Arbitrary Pseudoknots},
booktitle = {Proceedings of the 19th Annual Symposium on
             Combinatorial Pattern Matching (CPM 2008)},
year = {2008},
doi = {https://link.springer.com/chapter/10.1007/978-3-540-69068-9_9},
vol = {5029},
user = {will},
series = {LNCS},
publisher = {Springer-Verlag},
pages = {69-81},
abstract = {We present an algorithm that computes the edit
            distance of two RNA structures with arbitrary kinds
            of pseudoknots. A main benefit of the algorithm is
            that, despite the problem is NP-hard, the
            algorithmic complexity adapts to the complexity of
            the RNA structures. Due to fixed parameter
            tractability, we can guarantee polynomial run-time
            for a parameter which is small in practice. Our
            algorithm can be considered as a generalization of
            the algorithm of Jiang et al.~(Jiang, 2002) to
            arbitrary pseudoknots. In their absence, it
            gracefully degrades to the same polynomial
            algorithm. A prototypical implementation
            demonstrates the applicability of the method.}
}