Exact pattern matching for RNA secondary structures
Authors: 
Ying Xu, Lusheng Wang, Xiaotie DengAuthors Info & Claims
Pages 257 - 263
Abstract
Many RNA structures are assembled from a collection of RNA motifs, which appear repeatedly and in various combinations. Identification of RNA structural motifs will enhance our understanding of RNA structures and functions. Searching for secondary structural patterns in sequence databases is the basic technique and fundamental problem for extracting and identifying such motifs. A number of algorithms and programs have been developed for this purpose.In this paper, we adopt a representation of secondary structure called secondary expressions, and present two algorithms for finding all exact matches of a given secondary expression.
References
[1]
Baeza -Yates, R. (1996), 'A unified view to pattern matching algorithms', SOFSEM96, pp. 1--15.
[2]
Baeza-Yates, R. & Gonnet, F. (1992), 'A new approach to text searching', Communication of ACM, 35, pp. 74--82.
[3]
Billoud, B., Kontic, M. & Viari, A., (1996), 'Palingol: a declarative programming language to describe nucleic acids' secondary structures and to scan sequence databases', Nucleic Acids Res., 24, pp. 1395--1403.
[4]
hastain, M. & Tinoco, I. (1991), 'Structural elements in RNA', Prog. Nucleic Acids Res., 41, pp. 131--177.
[5]
Earley, J., (1970), 'An efficient context-free parsing algorithm', Communication of ACM, 13, pp. 94--102.
[6]
El-Mabrouk, N. & Lisacek, F., (1996), 'Very fast identification of RNA motifs in genomic DNA. Application to tRNA search in the yeast genome', J. Mol. Biol., 264, pp. 46--55.
[7]
El-Mabrouk, N. & Raffinot, M., (2002), 'Approximate matching of secondary structures', RECOMB02, 156--164.
[8]
Gusfield, D., (1997), 'Algorithms on strings, trees and sequences', Cambridge University Press.
[9]
Hopcroft, J. & Ullman, J., (1979), Introduction to automata theory, languages and computation, Addison-Wesley.
[10]
Lisacek, F., Diaz, Y. & Michel, F., (1994), 'Automatic identification of group I introns cores in genomic DNA sequences', J. Mol. Biol. 235, pp. 1206--1217.
[11]
Macke, T. J., Ecker, D. J., Gutell, R. R., Gautheret, D., Case, D. A. & Sampath, R., (2001), 'RNAMotif, an RNA secondary structure definition and search algorithm', Nucleid Acids Research, 29, pp. 4724--4735.
[12]
Myers, E., (1996), 'Approximate Matching of network expressions with spacers', J. of Computational Biology, 3, pp. 33--51.
[13]
Myers, E., (1992), 'A four-russians algorithm for regular expression pattern matching', Journal of ACM, 39, pp. 430--448.
[14]
Navarro, G., (2001), 'A guided tour to approximate string matching', ACM Computing surveys, 33, pp. 31--88.
[15]
Pesole, G., Liuni, S. & D'Souza, M., (2000), 'Pat-Search: a pattern matcher software that finds functional elements in nucleotide and protein sequences and assesses their statistical significance', Bioinformatics, 16, pp. 439--450.
[16]
Thompson, K., (1968), 'Regular expression search algorithm', Communications of the ACM, 11, 419--422.
[17]
Wu, S. & Manber, U., (1992), 'Fast text searching allowing errors', Communication of ACM, 35, pp. 83--91.
Index Terms
- Exact pattern matching for RNA secondary structures
Recommendations
Local exact pattern matching for non-fixed RNA structures
Detecting local common sequence-structure regions of RNAs is a biologically important problem. Detecting such regions allows biologists to identify functionally relevant similarities between the inspected molecules. We developed dynamic programming ...
Exact matching of RNA secondary structure patterns
Pattern discovery in the post genomeMany RNA structures are assembled from a collection of RNA motifs, which appear repeatedly and in various combinations. Identification of RNA structural motifs will enhance our understanding of RNA structures and functions. Searching for secondary ...
Efficient pattern matching for RNA secondary structures
We propose efficient methods to address key pattern matching problems in RNA secondary structures using the notion of structural strings. A structural string (s-string) is composed of constant symbols and parameter symbols from the alphabets Σ and , ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Australian Computer Society, Inc.
Australia
Publication History
Published: 01 January 2004
Author Tags
Qualifiers
- Article
Conference
APBC '04
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 386Total Downloads
- Downloads (Last 12 months)31
- Downloads (Last 6 weeks)7
Reflects downloads up to 31 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in