A method for discovering common patterns from two RNA secondary structures and its application to structural repeat detection.
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.
Department of Computer Science, New Jersey Institute of Technology, Newark, New Jersey 07102, USA. lh56@njit.edu
Lei
L
Hua
Jason T L
JT
Wang
Xiang
X
Ji
Ankur
A
Malhotra
Mugdha
M
Khaladkar
Bruce A
BA
Shapiro
Kaizhong
K
Zhang
D020413:3' Untranslated Regions; D000465:Algorithms; D001483:Base Sequence; D019295:Computational Biology / Q000379:methods*; D008969:Molecular Sequence Data; D009690:Nucleic Acid Conformation; D011494:Protein Kinases / Q000737:chemistry; D012313:RNA / Q000737:chemistry*; D017423:Sequence Analysis, RNA
D020413:3' Untranslated Regions; D012313:RNA; D011494:Protein Kinases