@InProceedings{Moehl:Will:Backofen:CPM2008,
  author =       {Mathias M{\"o}hl and Sebastian Will and Rolf
                  Backofen},
  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,
  pages =        {69-81},
  series =       {LNCS},
  vol =          5029,
  publisher =    {Springer-Verlag},
  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.},
  user =         {will}
}