Abstract
We propose an ab initio method, named DiscoverR, for finding common patterns from two RNA secondary structures. The method works by representing RNA secondary structures as ordered labeled trees and performs tree pattern discovery using an efficient dynamic programming algorithm. DiscoverR is able to identify and extract the largest common substructures from two RNA molecules having different sizes without prior knowledge of the locations and topologies of these substructures. We also extend DiscoverR to find repeated regions in an RNA secondary structure, and apply this extended method to detect structural repeats in the 3′-untranslated region of a protein kinase gene. We describe the biological significance of a repeated hairpin found by our method, demonstrating the usefulness of the method. DiscoverR is implemented in Java; a jar file including the source code of the program is available for download at http://bioinformatics.njit.edu/DiscoverR.
Original language | English (US) |
---|---|
Article number | 1250001 |
Journal | Journal of Bioinformatics and Computational Biology |
Volume | 10 |
Issue number | 4 |
DOIs | |
State | Published - Aug 2012 |
All Science Journal Classification (ASJC) codes
- Biochemistry
- Molecular Biology
- Computer Science Applications
Keywords
- RNA secondary structure
- pattern discovery
- repeat finding