Abstract
Many methods have been proposed for RNA secondary structure comparison, and new ones are still being developed. In this chapter, we first consider structure representations and discuss their suitability for structure comparison. Then, we take a look at the more commonly used methods, restricting ourselves to structures without pseudo-knots. For comparing structures of the same sequence, we study base pair distances. For structures of different sequences (and of different length), we study variants of the tree edit model. We name some of the available tools and give pointers to the literature. We end with a short review on comparing structures with pseudo-knots as an unsolved problem and topic of active research.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Byun Y, Han K (2009) PseudoViewer3: generating planar drawings of large-scale RNA structures with pseudoknots. Bioinformatics 25(11):1435–1437
Hofacker IL, Fontana W, Stadler PF, Sebastian Bonhoeffer L, Tacker M, Schuster P (1994) Fast folding and comparison of RNA secondary structures. Monatshefte für Chemie 125: 167–188
Darty K, Denise A, Ponty Y (2009) VARNA: Interactive drawing and editing of the RNA secondary structure. Bioinformatics 25(15):1974–1975
Fontana W, Konings DAM, Stadler PF, Schuster P (1993) Statistics of RNA secondary structures. Biopolymers 33(9): 1389–1404
Shapiro BA, Zhang KZ (1990) Comparing multiple RNA secondary structures using tree comparisons. Comput Appl Biosci 6(4): 309–318
Shapiro BA (1988) An algorithm for comparing multiple RNA secondary structures. Comput Appl Biosci 4(3):387–393
Giegerich R, Voß B, Rehmsmeier M (2004) Abstract shapes of RNA. Nucleic Acids Res 32(16):4843–4851
Allali J, Sagot M-F (2005) A multiple graph layers model with application to RNA secondary structures comparison. In: String processing and information retrieval. Springer, New York, pp 348–359
Janssen S, Reeder J, Giegerich R (2008) Shape based indexing for faster search of RNA family databases. BMC Bioinformatics 9(1):131
Wilm A, Linnenbrink K, Steger G (2008) ConStruct: Improved construction of RNA consensus structures. BMC Bioinformatics 9(1):219
Höner zu Siederdissen C, Hofacker IL (2010) Discriminatory power of RNA family models. Bioinformatics 26(18):i453–i459
Zuker M (1989) The use of dynamic programming algorithms in RNA secondary structure prediction. CRC Press, Boca Raton, RL, pp 159–184
Rosselló F, Valiente G (2006) An algebraic view of the relation between largest common subtrees and smallest common supertrees. Theor Comput Sci 362(1):33–53
Tai K-C (1979) The tree-to-tree correction problem. J ACM 26(3):422–433
Zhang K, Shasha D (1989) Simple fast algorithms for the editing distance between trees and related problems. SIAM J Comput 18(6):1245–1262
Schirmer S, Giegerich R (2011) Forest alignment with affine gaps and anchors. In: Combinatorial pattern matching. Springer, New York, pp 104–117
Jiang T, Lin G, Ma B, Zhang K (2002) A general edit distance between RNA structures. J Comput Biol 9(2):371–388
Lorenz R, Bernhart SH, Höner zu Siederdissen C, Tafer H, Flamm C, Stadler PF, Hofacker IL (2011) ViennaRNA Package 2.0. Algorithm Mol Biol 6(1):26
Hoechsmann M, Töller T, Giegerich R, Kurtz S (2003) Local similarity in RNA secondary structures. Proc IEEE Comput Syst Bioinformatics Conference (CSB 2003) 2: 159–168
Hoechsmann M, Voß B, Giegerich R (2004) Pure multiple RNA secondary structure alignments: A progressive profile approach. IEEE/ACM Trans Comput Biol Bioinformatics 1:53–62
Ritchie W, Legendre M, Gautheret D (2007) RNA stem loops: to be or not to be cleaved by RNAse III. RNA 13(4):457–462
Blin G, Denise A, Dulucq S, Herrbach C, Touzet H (2010) Alignments of RNA structures. IEEE/ACM Trans Comput Biol Bioinformatics 7(2):309–322
Allali J, Saule C, Chauve C, d’Aubenton Carafa Y, Denise A, Drevet C, Ferraro P, Gautheret D, Herrbach C, Leclerc F, de Monte A, Ouangraoua A, Sagot M-F, Termier M, Thermes C, Touzet H (2012a) Brasero: A resource for benchmarking RNA secondary structure comparison algorithms. Adv Bioinformatics 2012
Klein PN (1998) Computing the edit-distance between unrooted ordered trees. In: Proceedings of the 6th annual European Symposium on Algorithms (ESA). Springer, New York, pp 91–102
Touzet H (2005) A linear tree edit distance algorithm for similar ordered trees. In: CPM ’05: Proceedings of the 16th annual symposium on combinatorial pattern matching, pp 334–345
Dulucq S, Touzet H (2003) Analysis of tree edit distance algorithms. In: CPM ’03: Proceedings of the 14th annual symposium on combinatorial pattern matching, pp 83–95
Dulucq S, Touzet H (2005) Decomposition algorithms for the tree edit distance problem. J Discrete Algorithm 3(2–4):448–471
Zhang K, Shasha D (1987) On the editing distance between trees and related problems. Ultra-computer Note 122, NYU C.S TR 310, August 1987
Touzet H (2003) Tree edit distance with gaps. Inform Process Lett 85(3):123–129
Lozano A, Pinter RY, Rokhlenko O, Valiente G, Ziv-Ukelson M (2008) Seeded tree alignment. IEEE Trans Comput Biol Bioinformatics 503–513
Heyne S, Will S, Beckstette M, Backofen R (2009) Lightweight comparison of RNAs based on exact sequence-structure matches. Bioinformatics 25(16):2095–2102
Allali J, Chauve C, Ferraro P, Gaillard A-L (2012b) Efficient chaining of seeds in ordered trees. J Discrete Algorithm 14:107–118
Jiang T, Wang L, Zhang K (1995) Alignment of trees – an alternative to tree edit. Theor Comput Sci 143(1):137–148
Herrbach C, Denise A, Dulucq S (2010) Average complexity of the Jiang-Wang-Zhang pairwise tree alignment algorithm and of a RNA secondary structure alignment algorithm. Theor Comput Sci 411:2423–2432
Smith TF, Waterman MS (1981) Identification of common molecular subsequences. J Mol Biol 147(1):195–197
Allali J, Sagot M-F (2004) Novel tree edit operations for RNA secondary structure comparison. Algorithms Bioinformatics 412–425
Allali J, Sagot M-F (2008) A multiple layer model to compare RNA secondary structures. Software Pract Exp 38(8):775–792
Blin G, Touzet H (2006) How to compare arc-annotated sequences: The alignment hierarchy. In: SPIRE, pp 291–303
Bon M, Orland H (2011) Tt2ne: a novel algorithm to predict RNA secondary structures with pseudoknots. Nucleic Acids Res 39(14):e93. DOI 10.1093/nar/gkr240. URL http://nar.oxfordjournals.org/content/39/14/e93.abstract
Reidys CM, Huang FWD, Andersen JE, Penner R, Stadler PF, Nebel M (2011) Topology and prediction of RNA pseudoknots. Bioinformatics 27(8):1076–1085
Moehl M, Will S, Backofen R (2010) Lifting prediction to alignment of RNA pseudoknots. J Comput Biol 17(3):429–442
Rastegari B, Condon A (2007) Parsing nucleic acid pseudoknotted secondary structure: Algorithm and applications. J Comput Biol 14: 16–32
Rivas E, Eddy SR (1999) A dynamic programming algorithm for RNA structure prediction including pseudoknots. J Mol Biol 285: 2053–2068
Möhl M, Will S, Backofen R (2008) Fixed parameter tractable alignment of rna structures including arbitrary pseudoknots. In: Proceedings of the 19th annual symposium on combinatorial pattern matching (CPM 2008)
Bauer M, Klau GW (2004) Structural Alignment of Two RNA Sequences with Lagrangian Relaxation. In: Fleischer R, Trippen G (eds) Proceedings of the 15th international symposium ISAAC 2004, vol 3341 of Lecture Notes in Computer Science, pp 113–123. Springer, New York
Notredame C, Higgins DG, Heringa J (2000) T-Coffee: A novel method for fast and accurate multiple sequence alignment. J Mol Biol 302:205–217
Abraham M, Wolfson HJ (2011) Inexact graph matching by “geodesic hashing” for the alignment of pseudoknoted RNA secondary structures. In: Holub J, Žďárek J (eds) Proceedings of the Prague stringology conference 2011, pp 45–57, Czech Technical University in Prague, Czech Republic. ISBN 978-80-01-04870-2
Acknowledgment
Thanks go to Dr. Ralph Kandalla for a careful endodontic therapy of the first author, see also Fig. 15. Without his expertise, this chapter would not have been completed in time. Thanks also go to Sonja Klingberg for a careful reading of the manuscript.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer Science+Business Media New York
About this protocol
Cite this protocol
Schirmer, S., Ponty, Y., Giegerich, R. (2014). Introduction to RNA Secondary Structure Comparison. In: Gorodkin, J., Ruzzo, W. (eds) RNA Sequence, Structure, and Function: Computational and Bioinformatic Methods. Methods in Molecular Biology, vol 1097. Humana Press, Totowa, NJ. https://doi.org/10.1007/978-1-62703-709-9_12
Download citation
DOI: https://doi.org/10.1007/978-1-62703-709-9_12
Published:
Publisher Name: Humana Press, Totowa, NJ
Print ISBN: 978-1-62703-708-2
Online ISBN: 978-1-62703-709-9
eBook Packages: Springer Protocols