@Article{cpm09j,
  author =	 {Rolf Backofen and Gad M. Landau and Mathias M\"ohl
                  and Dekel Tsur and Oren Weimann},
  title =	 {Fast {RNA} Structure Alignment for Crossing Input
                  Structures},
  journal =	 {Journal of Discrete Algorithms},
  issn =	 {1570-8667},
  volume =	 9,
  number =	 1,
  year =	 2011,
  pages =	 {2-11},
  publisher =	 {Elsevier},
  editor =	 {Gregory Kucherov and Esko Ukkonen},
  ee =		 {http://dx.doi.org/10.1016/j.jda.2010.07.004},
  abstract =	 {The complexity of pairwise RNA structure alignment
                  depends on the structural restrictions assumed for
                  both the input structures and the computed consensus
                  structure. For arbitrarily crossing input and
                  consensus structures, the problem is NP-hard. For
                  non-crossing consensus structures, Jiang et al's
                  algorithm [1] computes the alignment in $O(n^2 m^2)$
                  time where $n$ and $m$ denote the lengths of the two
                  input sequences. If also the input structures are
                  non-crossing, the problem corresponds to tree
                  editing which can be solved in $O(m^2 n(1 + log n/m
                  ))$ time [2]. We present a new algorithm that solves
                  the problem for d-crossing structures in $O(dm^2 n
                  log n)$ time, where d is a parameter that is one for
                  non-crossing structures, bounded by $n$ for crossing
                  structures, and much smaller than $n$ on most
                  practical examples. Crossing input structures allow
                  for applications where the input is not a fixed
                  structure but is given as base-pair probability
                  matrices. Keywords : RNA, sequence structure
                  alignment, simultaneous alignment and folding},
  user =	 {mmohl}
}