Gesellschaft für Informatik e.V.

Lecture Notes in Informatics

German Conference on Bioinformatics P-136, 189-199 (2008).

Gesellschaft für Informatik, Bonn


Andreas Beyer (ed.), Michael Schroeder (ed.)

Copyright © Gesellschaft für Informatik, Bonn


Lightweight comparison of rnas based on exact sequence-structure matches

Steffen Heyne , Sebastian Will , Michael Beckstette and Rolf Backofen


Specific functions of RNA molecules are often associated with different motifs in the RNA structure. The key feature that forms such an RNA motif is the combination of sequence and structure properties. 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(n2m2)$ 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 (

Full Text: PDF

Gesellschaft für Informatik, Bonn
ISBN 978-3-88579-226-0

Last changed 04.10.2013 18:19:05