New models and algorithms for RNA pseudoknot order assignment

• Autorzy: Zok Tomasz , Badura Jan , Swat Sylwester , Figurski Kacper , Popenda Mariusz , Antczak Maciej

Identyfikatory

DOI

10.34768/amcs-2020-0024

• Języki publikacji: EN

Abstrakty

EN

The pseudoknot is a specific motif of the RNA structure that highly influences the overall shape and stability of a molecule. It occurs when nucleotides of two disjoint single-stranded fragments of the same chain, separated by a helical fragment, interact with each other and form base pairs. Pseudoknots are characterized by great topological diversity, and their systematic description is still a challenge. In our previous work, we have introduced the pseudoknot order: a new coefficient representing the topological complexity of the pseudoknotted RNA structure. It is defined as the minimum number of base pair set decompositions, aimed to obtain the unknotted RNA structure. We have suggested how it can be useful in the interpretation and understanding of a hierarchy of RNA folding. However, it is not trivial to unambiguously identify pseudoknots and determine their orders in an RNA structure. Therefore, since the introduction of this coefficient, we have worked on the method to reliably assign pseudoknot orders in correspondence to the mechanisms that control the biological process leading to their formation in the molecule. Here, we introduce a novel graph coloring-based model for the problem of pseudoknot order assignment. We show a specialized heuristic operating on the proposed model and an alternative integer programming algorithm. The performance of both approaches is compared with that of state-of-the-art algorithms which so far have been most efficient in solving the problem in question. We summarize the results of computational experiments that evaluate our new methods in terms of classification quality on a representative data set originating from the non-redundant RNA 3D structure repository.

Słowa kluczowe

EN

RNA pseudoknot order; conflict graph; vertex coloring; maximum independent set; integer programming

PL

kolorowanie grafu; zbiór niezależny; programowanie całkowitoliczbowe

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2020
• Tom: Vol. 30, no. 2
• Strony: 315--324
• Opis fizyczny: Bibliogr. 71 poz., rys., tab.

Twórcy

autor

Zok Tomasz

• Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznan, Poland; Poznan Supercomputing and Networking Center, Jana Pawla II 10, 61-131 Poznan, Poland

autor

Badura Jan

• Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznan, Poland

autor

Swat Sylwester

• Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznan, Poland

autor

Figurski Kacper

• Poznan Supercomputing and Networking Center, Jana Pawla II 10, 61-131 Poznan, Poland

autor

Popenda Mariusz

• Institute of Bioorganic Chemistry, Polish Academy of Sciences, Noskowskiego 12/14, 61-704 Poznan, Poland

autor

Antczak Maciej

• Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznan, Poland; Institute of Bioorganic Chemistry, Polish Academy of Sciences, Noskowskiego 12/14, 61-704 Poznan, Poland

Bibliografia

• [1] Aalberts, D.P. (2005). Asymmetry in RNA pseudoknots: Observation and theory, Nucleic Acids Research 33(7): 2210–2214.
• [2] Adamiak, R., Blazewicz, J., Formanowicz, P., Gdaniec, Z., Kasprzak, M., Popenda, M. and Szachniuk, M. (2004). An algorithm for an automatic NOE pathways analysis in 2D NMR spectra of RNA duplexes, Journal of Computational Biology 42(11): 163–180.
• [3] Adrjanowicz, K., Kaminski, K., Tarnacka, M., Szutkowski, K., Popenda, L., Bartkowiak, G. and Paluch, M. (2016). The effect of hydrogen bonding propensity and enantiomeric composition on the dynamics of supercooled ketoprofen—Dielectric, rheological and NMR studies, Physical Chemistry Chemical Physics 18(15): 10585–10593.
• [4] Antczak, M., Popenda, M., Zok, T., Sarzynska, J., Ratajczak, T., Tomczyk, K., Adamiak, R.W. and Szachniuk, M. (2016). New functionality of RNAComposer: Application to shape the axis of miR160 precursor structure, Acta Biochimica Polonica 63(4): 737–744.
• [5] Antczak, M., Popenda, M., Zok, T., Zurkowski, M., Adamiak, R.W. and Szachniuk, M. (2018). New algorithms to represent complex pseudoknotted RNA structures in dot-bracket notation, Bioinformatics 34(8): 1304–1312.
• [6] Antczak, M., Zok, T., Popenda, M., Lukasiak, P., Adamiak, R.W., Blazewicz, J. and Szachniuk, M. (2014). RNApdbee—A webserver to derive secondary structures from PDB files of knotted and unknotted RNAs, Nucleic Acids Research 42(W1): W368–W372.
• [7] Blazewicz, J., Figlerowicz, M., Kasprzak, M., Nowacka, M. and Rybarczyk, A. (2011). RNA partial degradation problem: Motivation, complexity, algorithm, Journal of Computational Biology 18(6): 821–834.
• [8] Blazewicz, J., Frohmberg, W., Gawron, P., Kasprzak, M., Kierzynka, M., Swiercz, A. and Wojciechowski, P. (2013). DNA sequence assembly involving an acyclic graph model, Foundations of Computing and Decision Sciences 38(1): 25–34.
• [9] Blazewicz, J., Kasprzak, M., Kierzynka, M., Frohmberg, W., Swiercz, A., Wojciechowski, P. and Zurkowski, P. (2018). Graph algorithms for DNA sequencing—Origins, current models and the future, European Journal of Operational Research 264(3): 799–812.
• [10] Blazewicz, J., Szachniuk, M. and Wojtowicz, A. (2005). RNA tertiary structure determination: NOE pathways construction by tabu search, Bioinformatics 21(10): 2356–2361.
• [11] Bon, M., Micheletti, C. and Orland, H. (2012). McGenus: a Monte Carlo algorithm to predict RNA secondary structures with pseudoknots, Nucleic Acids Research 41(3): 1895–1900.
• [12] Bon, M., Vernizzi, G., Orland, H. and Zee, A. (2008). Topological classification of RNA structures, Journal of Molecular Biology 379(4): 900–911.
• [13] Bron, C. and Kerbosch, J. (1973). Algorithm 457: Finding all cliques of an undirected graph, Communications of the ACM 16(9): 575–577.
• [14] Cheng, L., Connor, T.R., Siren, J., Aanensen, D.M. And Corander, J. (2013). Hierarchical and spatially explicit clustering of DNA sequences with BAPS software, Molecular Biology and Evolution 30(5): 1224–1228.
• [15] Chiu, J.K.H. and Chen, Y.-P.P. (2012). Conformational features of topologically classified RNA secondary structures, PLoS ONE 7(7): e39907.
• [16] Desai, N., Brown, A.A. and Ramakrishnan, V. (2017). The structure of the yeast mitochondrial ribosome, Science 355(6324): 528–531.
• [17] Gan, H.H., Pasquali, S. and Schlick, T. (2003). Exploring the repertoire of RNA secondary motifs using graph theory: Implications for RNA design, Nucleic Acids Research 31(11): 2926–2943.
• [18] Gebert, J., Lätsch, M., Pickl, S.W., Weber, G. and Wünschiers, R. (2006). An algorithm to analyze stability of gene-expression patterns, Discrete Applied Mathematics 154(7): 1140–1156.
• [19] Giuliani, A., Krishnan, A., Zbilut, J. and Tomita, M. (2008). Proteins as networks: Usefulness of graph theory in protein science, Current Protein & Peptide Science 9(1): 28–38.
• [20] Kropat, E., Özmen, A., Weber, G., Meyer-Nieberg, S. and Defterli, O. (2016). Fuzzy prediction strategies for gene-environment networks—Fuzzy regression analysis for two-modal regulatory systems, RAIRO Operations Research 50(2): 413–435.
• [21] Kruthika, H.A., Mahindrakar, A.D. and Pasumarthy, R. (2017). Stability analysis of nonlinear time-delayed systems with application to biological models, International Journal of Applied Mathematics and Computer Science 27(1): 91–103, DOI: 10.1515/amcs-2017-0007.
• [22] Kuang, R., Leslie, C.S. and Yang, A.-S. (2004). Protein backbone angle prediction with machine learning approaches, Bioinformatics 20(10): 1612–1621.
• [23] Kucharík, M., Hofacker, I.L., Stadler, P.F. and Qin, J. (2016). Pseudoknots in RNA folding landscapes, Bioinformatics 32(2): 187–194.
• [24] Kuppusamy, L. and Mahendran, A. (2016). Modelling DNA and RNA secondary structures using matrix insertion–deletion systems, International Journal of Applied Mathematics and Computer Science 26(1): 245–258, DOI: 10.1515/amcs-2016-0017.
• [25] Lai, D., Proctor, J.R., Zhu, J.Y.A. and Meyer, I.M. (2012). R-CHIE: A web server and R package for visualizing RNA secondary structures, Nucleic Acids Research 40(12): e95.
• [26] Leontis, N.B. and Zirbel, C.L. (2012). Nonredundant 3D structure datasets for RNA knowledge extraction and benchmarking, in N. Leontis and E. Westhof (Eds), Nucleic Acids and Molecular Biology, Springer Nature, Berlin/Heidelberg, pp. 281–298.
• [27] Leontis, N. and Westhof, E. (2012). RNA 3D Structure Analysis and Prediction, Springer, Berlin/New York, NY.
• [28] Lim, C.S. and Brown, C.M. (2018). Know your enemy: Successful bioinformatic approaches to predict functional RNA structures in viral RNAs, Frontiers in Microbiology 8: 2582.
• [29] Lu, X.-J. and Olson, W.K. (2008). 3DNA: A versatile, integrated software system for the analysis, rebuilding and visualization of three-dimensional nucleic-acid structures, Nature Protocols 3(7): 1213–1227.
• [30] Luby, M. (1986). A simple parallel algorithm for the maximal independent set problem, SIAM Journal on Computing 15(4): 1036–1053.
• [31] Lukasiak, P., Antczak, M., Ratajczak, T., Szachniuk, M., Popenda, M., Adamiak, R.W. and Blazewicz, J. (2015). RNAssess—A web server for quality assessment of RNA 3D structures, Nucleic Acids Research 43(W1): W502–W506.
• [32] Magnus, M., Antczak, M., Zok, T., Wiedemann, J., Lukasiak, P., Cao, Y., Bujnicki, J.M., Westhof, E., Szachniuk, M. and Miao, Z. (2020). RNA-Puzzles toolkit: A computational resource of RNA 3D structure benchmark datasets, structure manipulation, and evaluation tools, Nucleic Acids Research 48(2): 576–588.
• [33] Miao, Z. and Westhof, E. (2017). RNA structure: Advances and assessment of 3D structure prediction, Annual Review of Biophysics 46: 483–503.
• [34] Miskiewicz, J. and Szachniuk, M. (2018). Discovering structural motifs in miRNA precursors from the Viridiplantae kingdom, Molecules 23(6): 1367.
• [35] Morimura, H., Tanaka, S.-I., Ishitobi, H., Mikami, T., Kamachi, Y., Kondoh, H. and Inouye, Y. (2013). Nano-analysis of DNA conformation changes induced by transcription factor complex binding using plasmonic nanodimers, ACS Nano 7(12): 10733–10740.
• [36] Parisien, M., Cruz, J.A., Westhof, E. and Major, F. (2009). New metrics for comparing and assessing discrepancies between RNA 3D structures and models, RNA 15(10): 1875–1885.
• [37] Pasquali, S., Gan, H. and Schlick, T. (2005). Modular RNA architecture revealed by computational analysis of existing pseudoknots and ribosomal RNAs, Nucleic Acids Research 33(4): 1384–1398.
• [38] Pillsbury, M., Orland, H. and Zee, A. (2005). Steepest descent calculation of RNA pseudoknots, Physical Review E 72(1).
• [39] Popenda, L., Bielecki, L., Gdaniec, Z. and Adamiak, R.W. (2009). Structure and dynamics of adenosine bulged RNA duplex reveals formation of the dinucleotide platform in the C:G-A triple, Arkivoc 2009(3): 130–144.
• [40] Popenda, M., Miskiewicz, J., Sarzynska, J., Zok, T. and Szachniuk, M. (2020). Topology-based classification of tetrads and quadruplex structures, Bioinformatics 36(4): 1129–1134.
• [41] Pugalenthi, G., Suganthan, P.N., Sowdhamini, R. and Chakrabarti, S. (2007). SMotif: A server for structural motifs in proteins, Bioinformatics 23(5): 637–638.
• [42] Purzycka, K., Popenda, M., Szachniuk, M., Antczak, M., Lukasiak, P., Blazewicz, J. and Adamiak, R. (2015). Automated 3D RNA structure prediction using the RNAComposer method for riboswitches, in S.J. Chen and D.H. Burke Aguero (Eds), Methods in Enzymology, Vol. 553, Elsevier, San Diego, CA, pp. 3–34.
• [43] Radom, M., Rybarczyk, A., Szawulak, B., Andrzejewski, H., Chabelski, P., Kozak, A. and Formanowicz, P. (2017). Holmes: A graphical tool for development, simulation and analysis of Petri net based models of complex biological systems, Bioinformatics 33(23): 3822–3823.
• [44] Rebis, T., Lijewski, S., Nowicka, J., Popenda, L., Sobotta, L., Jurga, S., Mielcarek, J., Milczarek, G. and Goslinski, T. (2015). Electrochemical properties of metallated porphyrazines possessing isophthaloxybutylsulfanyl substituents: Application in the electrocatalytic oxidation of hydrazine, Electrochimica Acta 168: 216–224.
• [45] Reidys, C.M., Huang, F.W.D., Andersen, J.E., Penner, R.C., Stadler, P.F. and Nebel, M.E. (2011). Topology and prediction of RNA pseudoknots, Bioinformatics 27(8): 1076–1085.
• [46] Rietveld, K., Poelgeest, R.V., Pleij, C., Boom, J.V. and Bosch, L. (1982). The tRNA-like structure at the 3 terminus of turnip yellow mosaic virus RNA. Differences and similarities with canonical tRNA, Nucleic Acids Research 10(6): 1929–1946.
• [47] Rødland, E.A. (2006). Pseudoknots in RNA secondary structures: Representation, enumeration, and prevalence, Journal of Computational Biology 13(6): 1197–1213.
• [48] Rybarczyk, A., Hertz, A., Kasprzak, M. and Blazewicz, J. (2017). Tabu search for the RNA partial degradation problem, International Journal of Applied Mathematics and Computer Science 27(2): 401–415, DOI: 10.1515/amcs-2017-0028.
• [49] Saenger, W. (1984). Principles of Nucleic Acid Structure, Springer-Verlag, London.
• [50] Sarzynska, J. and Kulinski, T. (2005). Dynamics and stability of GCAA tetraloops with 2-aminopurine and purine substitutions, Journal of Biomolecular Structure and Dynamics 22(4): 425–439.
• [51] Schlick, T. (2018). Adventures with RNA graphs, Methods 143: 16–33.
• [52] Seetin, M. and Mathews, D. (2011). Automated RNA tertiary structure prediction from secondary structure and low-resolution restraints, Journal of Computational Chemistry 32(10): 2232–2244.
• [53] Shi, Y.-Z., Jin, L., Feng, C.-J., Tan, Y.-L. and Tan, Z.-J. (2018). Predicting 3D structure and stability of RNA pseudoknots in monovalent and divalent ion solutions, PLOS Computational Biology 14(6): e1006222.
• [54] Simon, M. (2005). Emergent Computation. Emphasizing Bioinformatics, Springer New York, New York, NY.
• [55] Slabinski, L., Jaroszewski, L., Rodrigues, A.P., Rychlewski, L., Wilson, I.A., Lesley, S.A. and Godzik, A. (2007). The challenge of protein structure determination-lessons from structural genomics, Protein Science 16(11): 2472–2482.
• [56] Staple, D.W. and Butcher, S.E. (2005). Pseudoknots: RNA structures with diverse functions, PLoS Biology 3(6): e213.
• [57] Sun, T.-t., Zhao, C. and Chen, S.-J. (2018). Predicting cotranscriptional folding kinetics for riboswitch, The Journal of Physical Chemistry B 122(30): 7484–7496.
• [58] Szachniuk, M. (2019). RNApolis: Computational platform for RNA structure analysis, Foundations of Computing and Decision Sciences 44(2): 241–257.
• [59] Szachniuk, M., Cola, M.C.D., Felici, G. and Blazewicz, J. (2014). The orderly colored longest path problem—A survey of applications and new algorithms, RAIRO—Operations Research 48(1): 25–51.
• [60] Szachniuk, M., Cola, M.C.D., Felici, G., de Werra, D. and Blazewicz, J. (2015). Optimal pathway reconstruction on 3D NMR maps, Discrete Applied Mathematics 182: 134–149.
• [61] Szostak, N., Royo, F., Rybarczyk, A., Szachniuk, M., Blazewicz, J., del Sol, A. and Falcon-Perez, J.M. (2014). Sorting signal targeting mRNA into hepatic extracellular vesicles, RNA Biology 11(7): 836–844.
• [62] Tarjan, R.E. and Trojanowski, A.E. (1977). Finding a maximum independent set, SIAM Journal on Computing 6(3): 537–546.
• [63] Vernizzi, G., Orland, H. and Zee, A. (2016). Classification and predictions of RNA pseudoknots based on topological invariants, Physical Review E 94(4).
• [64] Weber, G., Defterli, O., Gök, S.Z.A. and Kropat, E. (2011). Modeling, inference and optimization of regulatory networks based on time series data, European Journal of Operational Research 211(1): 1–14.
• [65] Weber, G., Kropat, E., Akteke-Öztürk, B. and Görgülü, Z. (2009). A survey on OR and mathematical methods applied on gene-environment networks, CEJOR 17(3): 315–341.
• [66] Wiedemann, J. and Milostan, M. (2017). StructAnalyzer—A tool for sequence vs. structure similarity analysis, Acta Biochimica Polonica 63(4): 753–757.
• [67] Wiedemann, J., Zok, T., Milostan, M. and Szachniuk, M. (2017). LCS-TA to identify similar fragments in RNA 3D structures, BMC Bioinformatics 18(1): 456.
• [68] Wojciechowski, P., Frohmberg, W., Kierzynka, M., Zurkowski, P. and Blazewicz, J. (2016). G-MAPSEQ—A new method for mapping reads to a reference genome, Foundations of Computing and Decision Sciences 41(2): 123–142.
• [69] Zemla, A. (2003). LGA: A method for finding 3D similarities in protein structures, Nucleic Acids Research 31(13): 3370–3374.
• [70] Zok, T., Antczak, M., Riedel, M., Nebel, D., Villmann, T., Lukasiak, P., Blazewicz, J. and Szachniuk, M. (2015). Building the library of RNA 3D nucleotide conformations using the clustering approach, International Journal of Applied Mathematics and Computer Science 25(3): 689–700, DOI: 10.1515/amcs-2015-0050.
• [71] Zok, T., Antczak, M., Zurkowski, M., Popenda, M., Blazewicz, J., Adamiak, R.W. and Szachniuk, M. (2018). RNApdbee 2.0: Multifunctional tool for RNA structure annotation, Nucleic Acids Research 46(W1): W30–W35.

Uwagi

PL

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).