@InProceedings{Heyne:Will:Beckstette:Backofen:GCB08,
  author =	 {Heyne, Steffen and Will, Sebastian and Beckstette,
                  Michael and Backofen, Rolf},
  title =	 {Lightweight comparison of {RNAs} based on exact
                  sequence-structure matches},
  booktitle = {Proceedings of the German Conference on Bioinformatics
                  (GCB'2008)},
  publisher = {Gesellschaft f{\"u}r Informatik (GI)},
  series    = {Lecture Notes in Informatics (LNI)},
  volume    = {P-136},
  year      = 2008,
  pages     = {189-198},
  isbn      = {987-3-88579-230-7},
  issn      = {1617-5468},
  abstract =	 {Specific functions of RNA molecules are often
                  associated to different motifs in the RNA
                  structure. The key feature is that the combination
                  of sequence and structure properties form such an
                  RNA motif. In this paper we introduce a new RNA
                  sequence-structure comparison method which maintains
                  exact matching substructures. Existing common
                  substructures are treated as whole unit while
                  variability is allowed between such structural
                  motifs.
		  
                  Based on a fast detectable set of overlapping and
                  crossing substructure matches for two nested RNA
                  secondary structures, our method computes the
                  longest colinear sequence of substructures common to
                  two RNAs in $O(n^2m^2)$ time and $O(nm)$
                  space. Applied to different RNAs, our method
                  correctly identifies sequence-structure similarities
                  between two RNAs. The results of our experiments are
                  in good agreement with existing alignment-based
                  methods, but can be obtained in a fraction of
                  running time, in particular for larger RNAs. The
                  proposed algorithm is implemented in the program
                  expaRNA, which is available from our website
                  (www.bioinf.uni-freiburg.de/Software).},
	user	= {heyne}
}