Metrics for RNA Secondary Structure Comparison.
Pseudoknot
RNA secondary structure
Topological centroid
Tree edit distance
Journal
Methods in molecular biology (Clifton, N.J.)
ISSN: 1940-6029
Titre abrégé: Methods Mol Biol
Pays: United States
ID NLM: 9214969
Informations de publication
Date de publication:
2023
2023
Historique:
pubmed:
28
1
2023
medline:
1
2
2023
entrez:
27
1
2023
Statut:
ppublish
Résumé
RNA secondary structure comparison is one of the important analyses for elucidating individual functions of RNAs since it is widely accepted that their functions and structures are strongly correlated. However, although the RNA secondary structures with pseudoknot play important roles in vivo, it is difficult to deal with such structures in silico due to their structural complexity, which is a major obstacle to the analysis of RNA functions.Here, we introduce an algorithm and a metric for comparing pseudoknotted RNA secondary structures based on topological centroid identification and tree edit distance and describe the usage protocol of a software enabling us to run the comparison. This software is publicly available and works on both Microsoft Windows and Apple macOS.
Identifiants
pubmed: 36705899
doi: 10.1007/978-1-0716-2768-6_5
doi:
Substances chimiques
RNA
63231-63-0
Types de publication
Journal Article
Langues
eng
Sous-ensembles de citation
IM
Pagination
79-88Informations de copyright
© 2023. Springer Science+Business Media, LLC, part of Springer Nature.
Références
Lorenz R, Bernhart SH, Höner zu Siederdissen C et al (2011) Vienna RNA package 2.0. Algotrithms Mol Biol 6(26):14
Akutsu T (2000) Dynamic programming algorithms for RNA secondary structure predictions with pseudoknots. Discrete Appl Math 104:45–62
doi: 10.1016/S0166-218X(00)00186-4
Jiang T, Lin G, Ma B et al (2002) A general edit distance between RNA structures. J Comput Biol 9:371–388
doi: 10.1089/10665270252935511
pubmed: 12015887
Blin G, Denise A, Dulucq S et al (2010) Alignments of RNA structures. IEEE/ACM Trans Comput Biol Bioinform 7:309–322
doi: 10.1109/TCBB.2008.28
pubmed: 20431150
Smit S, Yarus M, Knight R (2006) Natural selection is not required to explain universal compositional patterns in rRNA secondary structure categories. RNA 12:1–14
doi: 10.1261/rna.2183806
pubmed: 16373489
pmcid: 1370880
Andronescu M, Condon A, Hoos HH et al (2007) Efficient parameter estimation for RNA secondary structure prediction. Bioinformatics 23:i19–i28
doi: 10.1093/bioinformatics/btm223
pubmed: 17646296
Smit S, Rother K, Heringa J et al (2008) From knotted to nested RNA structures: a variety of computational methods for pseudoknot removal. RNA 14:410–416
doi: 10.1261/rna.881308
pubmed: 18230758
pmcid: 2248259
Poolsap U, Kato Y, Akutsu T (2009) Prediction if RNA secondary structure with pseudoknots using integer linear programming. BMC Bioinformatics 10(Suppl 1):S38
doi: 10.1186/1471-2105-10-S1-S38
pubmed: 19208139
pmcid: 2648744
Sato K, Kato Y, Hamada M, Akutsu T (2011) IPknot: fast and accurate prediction of RNA secondary structures with pseudoknots using integer programming. Bioinformatics 27:i85–i93
doi: 10.1093/bioinformatics/btr215
pubmed: 21685106
pmcid: 3117384
Hochsmann M, Voss B, Giegerich R (2004) Pure multiple RNA secondary structure alignments: a progressive profile approach. IEEE/ACM Trans Comput Biolo Bioinform 1:53–62
doi: 10.1109/TCBB.2004.11
Evans PA (2006) Finding common RNA pseudoknot structures in polynomial time. In: Lewenstein M, Valiente G (eds) Combinatorial pattern matching. CPM2006. Lecture notes in computer science, vol 4009. Springer, Berlin/Heidelberg
Chiu JKH, Chen YPP (2015) Pairwise RNA secondary structure alignment with conserved stem pattern. Bioinformatics 31:3914–3921
pubmed: 26275897
Möhl M, Will S, Backofen R (2008) Fixed parameter tractable alignment of RNA structures including arbitrary pseudoknots. In: Ferragina P, Landau GM (eds) Combinatorial pattern matching. CPM2006. Lecture notes in computer science, vol 5029. Springer, Berlin/Heidelberg
Akutsu T, de la Higuera C, Tamura T (2018) A simple linear-time algorithm for computing the centroid and canonical form of a plane graph and its applications. In: Navarro G, Sankoff D, Zhu B (eds) Proceedings of combinatorial pattern matching. CPM2018, 105. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl
Bille P (2005) A survey on tree edit distance and related problems. Theor Comput Sci 337:217–239
doi: 10.1016/j.tcs.2004.12.030
Wang F, Akutsu T, Mori T (2020) Comparison of pseudoknotted RNA secondary structures by topological centroid identification and tree edit distance. J Comput Biol 27(9):1443–1451. https://doi.org/10.1089/cmb.2019.0512
doi: 10.1089/cmb.2019.0512
pubmed: 32058802
Pawlik M, Augsten N (2011) RTED: a robust algorithm for the tree edit distance. Proc VLDB Endow 5(4):334–345
doi: 10.14778/2095686.2095692
Taufer M, Licon A, Araiza R et al (2008) PseudoBase++: an extension of PseudoBase for easy searching, formatting and visualization of pseudoknots. Nucleic Acids Res 37(Suppl 1):D127–D135
pubmed: 18988624
pmcid: 2686561
Ioanna K, Janna A, Natalia QO et al (2017) Rfam 13.0: shifting to a genome-centric resource for non-coding RNA families. Nucleic Acids Res 46(D1):D335–D342
Ashburner M, Ball CA, Blake JA et al (2000) Gene ontology: tool for the unification of biology. Nat Genet 25:25–29
doi: 10.1038/75556
pubmed: 10802651
pmcid: 3037419
The Gene Ontology Consortium (2019) The gene ontology resource: 20 years and still going strong. Nucleic Acids Res 47(D1):D330–D338
doi: 10.1093/nar/gky1055
Zhang K, Statman R, ShaSha D (1992) On the editing distance between unordered labeled trees. Inform Process Lett 42:133–139
doi: 10.1016/0020-0190(92)90136-J