@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)},
year = {2008},
volume = {P-136},
user = {heyne},
series = {Lecture Notes in Informatics (LNI)},
publisher = {Gesellschaft für Informatik (GI)},
pages = {189-198},
issn = {1617-5468},
isbn = {987-3-88579-230-7},
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).}
}