Abstract
The primary structure of a ribonucleic acid (RNA) molecule can be represented as a sequence of nucleotides (bases) over the four-letter alphabet {A,C, G, U}. The RNA secondary and tertiary structures can be represented as a set of nested base pairs and a set of crossing base pairs, respectively. These base pairs form bonds between A–U,–C–G, and G–U.
This paper considers alignment with affine gap penalty between two RNA molecule structures. In general this problem is Max SNP-hard for tertiary structures. We present an algorithm for the case where aligned base pairs are non-crossing. Experimental results show that this algorithm can be used for practical application of RNA structure alignment.
Research supported partially by the Natural Sciences and Engineering Research Council of Canada under Grant No. OGP0046373.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
V. Bafna, S. Muthukrishnan, and R. Ravi, ‘Comparing similarity between RNA strings’, Proc. Combinatorial Pattern Matching Conf. 95, LNCS 937, pp. 1–14, 1995
J. W. Brown, ‘The Ribonuclease P Database’, Nucleic Acids Research, 27:314, 1999.
J. H. Chen, S. Y. Le, and J. V. Maizel, ‘Prediction of common secondary structures of RNAs: a genetic algorithm approach’, Nucleic Acids Research, 28:4, pp. 991–999, 2000.
G. Collins, S. Y. Le, and K. Zhang, ‘A new method for computing similarity between RNA structures’, Proceedings of the Second International workshop on Biomolecular Informatics, pp. 761–765, Atlantic City, March 2000.
F. Corpet and B. Michot, ‘RNAlign program: alignment of RNA sequences using both primary and secondary structures’, Comput. Appl. Biosci vol. 10, no. 4, pp. 389–399, 1995.
P. A. Evans, Algorithms and Complexity for Annotated Sequence Analysis, PhD thesis, University of Victoria, 1999.
O. Gotoh, ‘An improved algorithm for matching biological sequences’, J. Mol. Biol., 162, pp. 705–708, 1982.
T. Jiang, G.-H. Lin, B. Ma, and K. Zhang, ‘The longest common subsequence problem for arc-annotated sequences’, Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching (CPM 2000), LNCS 1848, pages 154–165, 2000.
H. Lenhof, K. Reinert, and M. Vingron. ‘A polyhedral approach to RNA sequence structure alignment’. Proceedings of the Second Annual International Conference on Computational Molecular Biology (RECOMB’98), pages 153–159, 1998.
G.-H. Lin, B. Ma, and K. Zhang, ‘Edit distance between two RNA structures’, to appear Proceedings of the Fifth Annual International Conference on Computational Molecular Biology (RECOMB’2001), pp. 200–209, 2001.
S. E. Needleman and C. D. Wunsch, ‘A general method applicable to the search for similarities in the amino-acid sequences of two proteins’, J. Mol. Bio., 48, pp. 443–453, 1970
C. H. Papadimitriou and M. Yannakakis, ‘Optimization, approximation, and complexity classes’, J. Comput. System Sciences, vol. 43, pp. 425–440, 1991.
Y. Sakakibara, M. Brown, R. Hughey, I. S. Mian, K. Sjölander, R. Underwood, and D. Haussler, ‘Stochastic context-free grammar for tRNA modeling’, Nucleic aids research, vol. 22, no. 23, pp. 5112–5120, 1994.
D. Sankoff, ‘Simultaneous solution of the RNA folding, alignment and protose-quence problems’, SIAM J. Appl. Math vol. 45, no. 5, pp. 810–824, 1985.
T. F. Smith and M. S. Waterman, ‘Comparison of biosequences’, Adv. in Appl. Math. 2, pp. 482–489, 1981
K. Zhang, L. Wang, and B. Ma, ‘Computing similarity between RNA structures’, Proceedings of the Tenth Symposium on Combinatorial Pattern Matching. LNCS 1645, pp. 281–293, 1999.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wang, Z., Zhang, K. (2001). Alignment between Two RNA Structures. In: Sgall, J., Pultr, A., Kolman, P. (eds) Mathematical Foundations of Computer Science 2001. MFCS 2001. Lecture Notes in Computer Science, vol 2136. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44683-4_60
Download citation
DOI: https://doi.org/10.1007/3-540-44683-4_60
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42496-3
Online ISBN: 978-3-540-44683-5
eBook Packages: Springer Book Archive