@article{SiebertJCB07,
author = {Siebert, Sven and Backofen, Rolf},
title = {A dynamic programming approach for finding common patterns 
         in {RNAs}},
journal = {JCB},
year = {2007},
doi = {10.1089/cmb.2006.0089},
volume = {14},
user = {heyne},
pmid = {17381344},
pages = {33-44},
number = {1},
abstract = {We developed a dynamic programming approach of computing 
            common sequence structure patterns among two RNAs given 
            their primary sequences and their secondary structures. 
            Common patterns between two RNAs are defined to share the 
            same local sequential and structural properties. The 
            locality is based on the connections of nucleotides given by 
            their phosphodiester and hydrogen bonds. The idea of 
            interpreting secondary structures as chains of structure 
            elements leads us to develop an efficient dynamic 
            programming approach in time O(nm) and space O(nm), where n 
            and m are the lengths of the RNAs. The biological motivation 
            is given by detecting common, local regions of RNAs, 
            although they do not necessarily share global sequential and 
            structural properties. This might happen if RNAs fold into 
            different structures but share a lot of local, stable 
            regions. Here, we illustrate our algorithm on Hepatitis C 
            virus internal ribosome entry sites. Our method is useful 
            for detecting and describing local motifs as well. An 
            implementation in C++ is available and can be obtained by 
            contacting one of the authors.}
}