@article{Backofen:Siebert:Fast_Det_Pat:2007,
author = {Backofen, Rolf and Siebert, Sven},
title = {Fast Detection of Common Sequence Structure Patterns in {RNAs}},
journal = {Journal of Discrete Algorithms},
year = {2007},
doi = {10.1016/j.jda.2006.03.015},
volume = {5},
user = {siebert},
pages = {212-228},
number = {2},
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. }
}