Published Articles >> Table of Contents >> Abstract

IEEE Computer Society Bioinformatics Conference (CSB'03)   p. 159
Local Similarity in RNA Secondary Structures
Matthias Hochsmann, University of Bielefeld
Thomas Toller, University of Bielefeld
Robert Giegerich, University of Bielefeld
Stefan Kurtz, University of Bielefeld

Full Article Text:

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CSB.2003.1227315
Send link to a friend

Abstract
We present a systematic treatment of alignment distance and local similarity algorithms on trees and forests. We build upon the tree alignment algorithm for ordered trees given by Jiang et. al (1995) and extend it to calculate local forest alignments, which is essential for finding local similar regions in RNA secondary structures. The time complexity of our algorithm is O(|F1| \cdot |F2 \cdot deg(F1) \cdot deg(F2) \cdot (deg(F1) + deg(F2)) where |Fi| is the number of nodes in forest Fi and deg (Fi) is the degree of Fi. We provide carefully engineered dynamic programming implementations using dense, two-dimensional tables which considerably reduces the space requirement. We suggest a new representation of RNA secondary structures as forests that allow reasonable scoring of edit operations on RNA secondary structures. The comparison of RNA secondary structures is facilitated by a new visualization technique for RNA secondary structure alignments. Finally, we show how potential regulatory motifs can be discovered solely by their structural preservation, and independent of their sequence conservation and position.
Back to Top Additional Information
Citation:  Matthias Hochsmann, Thomas Toller, Robert Giegerich, Stefan Kurtz, "Local Similarity in RNA Secondary Structures," csb, p. 159,  IEEE Computer Society Bioinformatics Conference (CSB'03),  2003