Local similarity in RNA secondary structures | IEEE Conference Publication | IEEE Xplore

- Donate
- Personal Sign In

ADVANCED SEARCH

Conferences >Computational Systems Bioinfo...

Local similarity in RNA secondary structures

Download PDF
Download References
Request Permissions
Save to
Alerts

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...Show More

Metadata

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(/F/sub 1///spl middot//F/sub 2//)/spl middot/deg(F/sub 1/)/spl middot/deg(F/sub 2/)/spl middot/(deg(F/sub 1/)+deg(F/sub 2/)) 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.

Published in: Computational Systems Bioinformatics. CSB2003. Proceedings of the 2003 IEEE Bioinformatics Conference. CSB2003

Date of Conference: 11-14 August 2003

Date Added to IEEE Xplore: 08 September 2003

Print ISBN:0-7695-2000-6

DOI: 10.1109/CSB.2003.1227315

Conference Location: Stanford, CA, USA

References is not available for this document.

1. Motivation

RNA is a chain molecule, mathematically a string over a four letter alphabet. It is built from nucleotides containing the bases A(denine), c(ytosine), G(uanine), and U(racil). By folding back onto itself, an RNA molecule forms structure, stabilized by the forces of hydrogen bonds between certain pairs of bases (A–U, C–G, G–U), and dense stacking of neighbouring base pairs.

Select All

1.

A. Apostolico and Z. Galil, Pattern Matching Algorithms, Oxford University Press, 1997.

2.

R. Bellman, Dynamic Programming, Princeton University Press, 1957.

3.

R. Giegerich, "A systematic approach to dynamic programming in bioinformatics", Bioinformatics, vol. 16, pp. 665-677, 2000.

CrossRef Google Scholar

4.

R. Giegerich and C. Meyer, "Algebraic dynamic programming", Algebraic Methodology And Software Technology 9th International Conference AMAST 2002, pp. 349-364, 2002.

CrossRef Google Scholar

5.

N. Gray and M. Wickens, "Control of translation initiation in animals", Annu. Rev. Cell Dev. Biol., vol. 14, pp. 399-458, 1998.

CrossRef Google Scholar

6.

J. Guhaniyogi and G. Brewer, "Regulation of mRNA stability in mammalian cells", Gene, vol. 265, pp. 11-23, 2001.

CrossRef Google Scholar

7.

R. Gutell, N. Larsen and C. Woese, "Lessons from an evolving rRNA: 16s and 23s rRNA structures from comparative perspective", Microbiol Rev, vol. 58, pp. 10-26, 1994.

CrossRef Google Scholar

8.

M. Hentze and L. Kuehn, "Molecular control of vertebrate iron metabolism: mRNA-based regulatory circuits operated by iron nitric oxide and oxidative stress", Proc. Natl. Acad. Sci. USA, vol. 93, pp. 8175-8182, 1996.

CrossRef Google Scholar

9.

R. Jansen, "mRNA localization: Message on the move", Nature Rev Mol Cell Biol, vol. 2, pp. 247-256, 2001.

CrossRef Google Scholar

10.

J. Jansson and A. Lingas, "A fast algorithm for optimal alignment between similar ordered trees", Lecture Notes in Computer Science, no. 2089, pp. 232-240, 2001.

CrossRef Google Scholar

11.

T. Jiang, G. Lin, B. Ma and K. Zhang, "A general edit distance between RNA structures", J. of Computational Biology, vol. 9, no. 2, pp. 371-388, 2002.

CrossRef Google Scholar

12.

T. Jiang, J. Wang and K. Zhang, "Alignment of trees – an alternative to tree edit", Theoretical Computer Science, vol. 143, no. 1, pp. 137-148, 1995.

CrossRef Google Scholar

13.

T. Kiss, "Small nucleolar RNAs: An abundant group of non-coding RNAs with diverse cellular functions", Cell, vol. 109, pp. 145-148, 2002.

CrossRef Google Scholar

14.

R. Klausner, T. Rouault and J. Harford, "Regulating the fate of mRNA: The control of cellular iron metabolism", Cell, vol. 72, pp. 19-28, 1993.

CrossRef Google Scholar

15.

P. N. Klein, "Computing the edit-distance between unrooted ordered trees", Proceedings of the 6th Annual European Symposium, no. 1461, pp. 91-102, 1998.

CrossRef Google Scholar

16.

S. Le, R. Nussinov and J. Mazel, "Tree graphs of RNA secondary structures and their comparison", Computational Biomedical Research, vol. 22, pp. 461-473, 1989.

CrossRef Google Scholar

17.

T. Lowe and S. Eddy, "tRNAscan-se: A program for improved detection of transfer RNA genes in genomic sequence", Nucleic Acids Res, vol. 25, pp. 955-964, 1997.

CrossRef Google Scholar

18.

G. Pesole, S. Liuni, G. Grillo, F. Licciulli, F. Mignone, C. Gissi, et al., "Utrdb and utrsite: specialized database of sequences and functional elements of 5’ and 3’ untranslated regions of eukaryotic mRNAs", Nucleic Acids Research, vol. 30, pp. 335-340, 2002.

CrossRef Google Scholar

19.

B. Shapiro, "An algorithm for comparing multiple RNA secondary stuctures", Comp. Appl. Biosci., vol. 4, no. 3, pp. 387-393, 1988.

CrossRef Google Scholar

20.

B. A. Shapiro and K. Zhang, "Comparing multiple rna secondary structures using tree comparisons", Comp. Appl. Biosci., vol. 6, no. 4, pp. 309-318, 1990.

CrossRef Google Scholar

21.

T. Smith and M. Waterman, "Identification of common molecular subsequences", J. Mol. Biol., vol. 147, pp. 195-197, 1981.

CrossRef Google Scholar

22.

M. Sprinzl, C. Horn, M. Brown, A. Ioudovitch and S. Steinberg, "Compilation of tRNA sequences and sequences of tRNA genes", Nucleic Acids Research, vol. 26, pp. 148-153, 1998.

CrossRef Google Scholar

23.

K. Tai, "The tree-to-tree corection problem", Journal of the ACM, vol. 26, pp. 422-433, 1979.

CrossRef Google Scholar

24.

T. Villa, J. Pleiss and C. Guthrie, "Spliceosomal snRNAs:mg(2+)-dependent chemistry at the catalytic core?", Cell, vol. 109, pp. 149-152, 2002.

CrossRef Google Scholar

25.

R. Wagner and M. Fischer, "The string to string correction problem", Journal of the ACM, vol. 21, no. 1, pp. 168-173, 1974.

CrossRef Google Scholar

26.

J. Wang, B. A. Shapiro, D. Sasha, K. Zhang and K. M. Currey, "An algorithm for finding the largest approxemately common substructures of two trees", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 20, no. 8, pp. 889-895, 1998.

27.

J. Wang and K. Zhang, "Identifying consensus of trees through alignment", Information Sciences, vol. 126, pp. 165-189, 2000.

CrossRef Google Scholar

28.

J. Wang, K. Zhang and C.-Y. Chang, "Identifying approximate common substructures in trees based on a restricted edit distance", Information Sciences, vol. 121, pp. 367-386, 1999.

CrossRef Google Scholar

29.

K. Zhang, "A new editing based distance between unordered labeled trees", Proc. CPM Combinatorial Pattern Matchins, no. 684, pp. 254-265, 1993.

CrossRef Google Scholar

30.

K. Zhang, "Computing similarity between RNA secondary structures", IEEE International Joint Symposia on Intelligence and Systems, pp. 126-132, 1998.

References is not available for this document.