@Article{Backofen:Siebert:Fast_Det_Pat:2007,
  author = 	 {Rolf Backofen and Sven Siebert},
  title = 	 {Fast Detection of Common Sequence Structure Patterns in {RNAs}},
  journal = 	 {Journal of Discrete Algorithms},
  year = 	 {2007},
  volume =       {5},
  number =       {2},
  pages =        {212-228},
  abstract = {We developed a dynamic programming approach for
  computing common exact sequential and structural patterns between
  two RNAs, given their sequences and their secondary structures. An
  RNA consists of a sequence of nucleotides and a secondary structure
  defined via bonds linking together complementary nucleotides. It is
  known that secondary structures are more preserved than sequences in
  the evolution of RNAs.

  We are able to compute all patterns between two RNAs in time O(nm)
  and space O(nm), where n and m are the lengths of the RNAs.  Our
  method is useful for describing and detecting local motifs. It is
  especially suitable for finding similar regions of large RNAs that
  do not share global similarities.  An implementation is available in
  C++ and can be obtained by contacting one of the authors. } ,
  user =	 {siebert}
}