3D RNA Graph Representation Methods for Classification of RNA Molecules Using Graph Kernel and Graph Neural Network Methods

Year 2023, Volume: 28 Issue: 3, 919 - 934, 29.12.2023

Enes Algül

https://doi.org/10.53433/yyufbed.1256154

Abstract

Ribonucleic acids (RNAs) are nucleic acid types with 1D/2D/3D structural shapes and are essential for sustaining life. These structural shapes of the RNAs are highly correlated with their functions. While the primary and secondary structures of RNA have been extensively studied, the tertiary structure has received relatively less attention. In this article, we present novel approaches for representing 3D RNA structures as graph data, employing geometric measurements such as Base position, Square root velocity function (SRVF), Arc length, and Curvature. Then, we utilise kernel methods and neural network methods to predict RNA functions. Our findings demonstrate the effectiveness of these methodologies in unraveling the functional attributes of RNA molecules, thus enriching our understanding of their complex biological significance.

Keywords

3D RNA Graph Representations, Geometric Measurements, Graph Classifications, Graph Kernels, Graph Neural Networks

Graf Çekirdek ve Graf Sinir Ağı Yöntemlerini Kullanarak RNA Moleküllerini Sınıflandırılmak İçin 3D RNA Graf Temsili Yöntemleri

Abstract

Ribonükleik asitler (RNA'lar), 1B/2B/3B yapısal şekillere sahip nükleik asit türleri olup, yaşamı sürdürmek için hayati öneme sahiptirler. RNA'ların bu yapısal şekilleri, fonksiyonlarıyla yüksek derecede ilişkilidir. RNA'nın birincil ve ikincil yapıları kapsamlı bir şekilde incelenirken, üçüncül yapı nispeten daha az dikkat çekmiştir. Bu makalede, Baz konumu, Karekök hız fonksiyonu (SRVF), Yay uzunluğu ve Eğrilik gibi geometrik ölçümler kullanarak 3B RNA yapılarını grafik verileri olarak temsil etmeye yönelik yeni yaklaşımlar sunuyoruz. Daha sonra, çekirdek (kernel) yöntemleri ve sinir ağı (neural network) yöntemleri kullanarak RNA fonksiyonlarını tahmin ediyoruz. Bulgularımız, bu metodolojilerin RNA moleküllerinin fonksiyonel özelliklerini çözmedeki etkinliğini gösteriyor ve böylece onların karmaşık biyolojik önemine dair anlayışımızı zenginleştiriyor.

Keywords

3B RNA Graf Temsilleri, Geometrik Ölçümler, Graf Çekirdekleri, Graf Sınıflandırmaları, Graf Sinir Ağları

References

• Algul, E., & Wilson, R. C. (2019). A Database and Evaluation for Classification of RNA Molecules Using Graph Methods. In D. Conte, J.Y. Ramel & P. Foggia (Eds.), Graph-Based Representations in Pattern Recognition: 12th IAPR-TC-15 International Workshop, GbRPR 2019. Lecture Notes in Computer Science, vol. 11510 (pp. 78-87). Springer, Cham. doi:10.1007/978-3-030-20081-7_8
• Balcerak, A., Trebinska-Stryjewska, A., Konopinski, R., Wakula, M., & Grzybowska, E. A. (2019). RNA–protein interactions: disorder, moonlighting and junk contribute to eukaryotic complexity. Open Biology, 9(6), 190096. doi:10.1098/rsob.190096
• Borgwardt, K. M., & Kriegel, H. P. (2005). Shortest-path kernels on graphs. Fifth IEEE International Conference on Data Mining (ICDM'05), Houston, TX, USA. doi:10.1109/ICDM.2005.132
• Carrasco-Hernandez, R., Jácome, R., López Vidal, Y., & Ponce de León, S. (2017). Are RNA viruses candidate agents for the next global pandemic? A review. ILAR Journal, 58(3), 343-358. doi:10.1093/ilar/ilx026
• Chen, L., Calin, G. A., & Zhang, S. (2012). Novel insights of structure-based modeling for RNA-targeted drug discovery. Journal of Chemical Information and Modeling, 52(10), 2741-2753. doi:10.1021/ci300320t
• Chen, Z., Li, X., & Bruna, J. (2017). Supervised community detection with line graph neural networks. arXiv preprint arXiv:1705.08415. doi:10.48550/arXiv.1705.08415
• Chojnowski, G., Waleń, T., & Bujnicki, J. M. (2013). RNA Bricks-a database of RNA 3D motifs and their interactions. Nucleic Acids Research, 42(D1), D123-D131. doi:10.1093/nar/gkt1084
• Dai, H., Dai, B., & Song, L. (2016). Discriminative embeddings of latent variable models for structured data. Proceedings of International Conference on Machine Learning, PMLR, 48, 2702-2711.
• Darty, K., Denise, A., & Ponty, Y. (2009). VARNA: Interactive drawing and editing of the RNA secondary structure. Bioinformatics, 25(15), 1974-1975. doi:10.1093/bioinformatics/btp250
• de Vries, G. K. D. (2013). A fast approximation of the Weisfeiler-Lehman graph kernel for RDF data. In H. Blockeel, K. Kersting, S. Nijssen, F. Železný, (Eds.) Machine Learning and Knowledge Discovery in Databases. ECML PKDD 2013. Lecture Notes in Computer Science(), vol. 8188. Berlin, Germany: Springer. doi:10.1007/978-3-642-40988-2_39
• Ding, Y. (2006). Statistical and Bayesian approaches to RNA secondary structure prediction. RNA, 12(3), 323-331. doi:10.1261%2Frna.2274106
• Du, S. S., Hou, K., Póczos, B., Salakhutdinov, R., Wang, R., & Xu, K. (2019). Graph neural tangent kernel: Fusing graph neural networks with graph kernels. Advances in Neural Information Processing Systems, 32, ArXiv, abs/1905.13192. doi:10.48550/arXiv.1905.13192
• Gao, H., & Ji, S. (2019). Graph U-Nets. Proceedings of the 36th International Conference on Machine Learning, PMLR, 97, 2083-2092.
• Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., & Dahl, G. E. (2017). Neural message passing for quantum chemistry. Proceedings of the 34th International Conference on Machine Learning, PMLR, 70, 1263-1272.
• Giscard, P.-L., & Wilson, R. C. (2017). The all-paths and cycles graph kernel. arXiv preprint arXiv:1708.01410. doi:10.48550/arXiv.1708.01410
• Hajiaghayi, M., Condon, A., & Hoos, H. H. (2012). Analysis of energy-based algorithms for RNA secondary structure prediction. BMC Bioinformatics, 13(1), 22. doi:10.1186/1471-2105-13-22
• Hermansson, L., Johansson, F. D., & Watanabe, O. (2015). Generalized shortest path kernel on graphs. In Discovery Science,18th International Conference, DS 2015, Banf, AB, Canada.
• Huang, H.-Y., & Lin, C.-J. (2016). Linear and kernel classification: When to use which? Proceedings of the 2016 SIAM International Conference on Data Mining, 216-224. doi:10.1137/1.9781611974348.25
• Kang, U., Tong, H., & Sun, J. (2012). Fast random walk graph kernel. Proceedings of the 2012 SIAM International Conference on Data Mining, 828-838. doi:10.1137/1.9781611972825.71
• Kerpedjiev, P., Höner zu Siederdissen, C., & Hofacker, I. L. (2015). Predicting RNA 3D structure using a coarse-grain helix-centered model. RNA, 21, 1110-1121. doi:10.1261%2Frna.047522.114
• Kim, N., Zahran, M., & Schlick, T. (2015). Computational prediction of riboswitch tertiary structures including pseudoknots by RAGTOP: a hierarchical graph sampling approach. Methods in Enzymology, 553, 115-135. doi:10.1016/bs.mie.2014.10.054
• Kipf, T. N., & Welling, M. (2017). Semi-supervised classification with graph convolutional networks. arXiv:1609.02907. doi:10.48550/arXiv.1609.02907
• Klosterman, P. S., Tamura, M., Holbrook, S. R., & Brenner, S. E. (2002). SCOR: A structural classification of RNA database. Nucleic Acids Research, 30(1), 392-394. doi:10.1093/nar/30.1.392
• Kriege, N. M, Giscard, P-L., & Wilson, R. C. (2016). On valid optimal assignment kernels and applications to graph classification. In D. D. Lee, U. von Luxburg, R. Garnett, M. Sugiyama, & I. Guyon (Eds.), Advances in Neural Information Processing Systems 29 (NIPS 2016) (pp. 1623-1631). Curran Associates Inc.
• Kriege, N. M., Johansson, F. D., & Morris, C. (2020). A survey on graph kernels. Applied Network Science, 5(1), 1-42. doi:10.1007/s41109-019-0195-3
• Laborde, J., Srivastava, A., & Zhang, J. (2011). Structure-based RNA function prediction using elastic shape analysis. IEEE International Conference on Bioinformatics and Biomedicine, 16-21. doi:10.1109/BIBM.2011.119
• Laborde, J., Robinson, D., Srivastava, A., Klassen, E., & Zhang, J. (2013). RNA global alignment in the joint sequence–structure space using elastic shape analysis. Nucleic Acids Research, 41(11), e114. doi:10.1093/nar/gkt187
• Laing, C., Jung, S., Kim, N., Elmetwaly, S., Zahran, M., & Schlick, T. (2013). Predicting helical topologies in RNA junctions as tree graphs. PLoS ONE, 8(8), e71947. doi:10.1371/journal.pone.0071947
• Lau, M., & Ferré-D’Amaré, A. (2016). Many activities, one structure: Functional plasticity of ribozyme folds. Molecules, 21(11), 1570. doi:10.3390/molecules21111570
• Liu, W., Srivastava, A., & Zhang, J. (2010). Protein structure alignment using elastic shape analysis. Proceedings of the First ACM International Conference on Bioinformatics and Computational Biology, 62-70. doi:10.1145/1854776.1854790
• Magnus, M., Kappel, K., Das, R., & Bujnicki, J. M. (2019). RNA 3D structure prediction guided by independent folding of homologous sequences. BMC Bioinformatics, 20(1), 512. doi:10.1186/s12859-019-3120-y
• Miao, Z., & Westhof, E. (2017). RNA structure: Advances and assessment of 3D structure prediction. Annual Review of Biophysics, 46(1), 483-503. doi:10.1146/annurev-biophys-070816-034125
• Mjaavatten, A. (2020). Curvature of a 1D curve in a 2D or 3D space. MATLAB Central File Exchange. https://www.mathworks.com/matlabcentral/fileexchange/69452-curvature-of-a-1d-curve-in-a-2d-or-3d-space Access date: 20 March 2023.
• Needleman, S. B., & Wunsch, C. D. (1970). A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 48(3), 443-453. doi:10.1016/0022-2836(70)90057-4
• Neumann, M., Garnett, R., Bauckhage, C., & Kersting, K. (2015). Propagation kernels: efficient graph kernels from propagated information. Machine Learning, 102, 209-245. doi:10.1007/s10994-015-5517-9
• Nova, D., & Estévez, P. A. (2013). A review of learning vector quantization classifiers. Neural Computing and Applications, 25(3-4), 511-524. doi:10.1007/s00521-013-1535-3
• Oliver, C., Mallet, V., Philippopoulos, P., Hamilton, W. L., & Waldispühl, J. (2022). Vernal: a tool for mining fuzzy network motifs in RNA. Bioinformatics, 38(4), 970-976. doi:10.1093/bioinformatics/btab768
• Pande, V., & Nilsson, L. (2008). Insights into structure, dynamics and hydration of locked nucleic acid (LNA) strand-based duplexes from molecular dynamics simulations. Nucleic Acids Research, 36(5), 1508-1516. doi:10.1093/nar/gkm1182
• Petrov, A. I., Zirbel, C. L., & Leontis, N. B. (2013). Automated classification of RNA 3D motifs and the RNA 3D Motif Atlas. RNA, 19(10), 1327-1340. doi:10.1261%2Frna.039438.113
• Purzycka, K. J., Adamiak, R. W., Blazewicz, J., Popenda, M., Szachniuk, M., Antczak, M., & Lukasiak, P. (2015). Automated 3D RNA structure prediction using the RNAComposer method for Riboswitches1. Methods in Enzymology, 553, 3-34. doi:10.1016/bs.mie.2014.10.050
• Reinharz, V., Soulé, A., Westhof, E., Waldispühl, J., & Denise, A. (2018). Mining for recurrent long-range interactions in RNA structures reveals embedded hierarchies in network families. Nucleic Acids Research, 46(8), 3841-3851. doi:10.1093/nar/gky197
• Ren, Y., Bai, J. & Zhang, J. (2021). Label contrastive coding based graph neural network for graph classification. Database Systems for Advanced Applications, 123-140. doi:10.1007/978-3-030-73194-6_10
• Ribeiro, L., Saverese, P., & Figueiredo, D. (2017). struc2vec: Learning node representations from structural identity. Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 385-394. doi:10.1145/3097983.3098061
• Schneider, P., Biehl, M., & Hammer, B. (2009). Distance learning in discriminative vector quantization. Neural Computation, 21(10), 2942-2969. doi:10.1162/neco.2009.10-08-892
• Shervashidze, N., Schweitzer, P., Van Leeuwen, E. J., Mehlhorn, K., & Borgwardt, K. M. (2011). Weisfeiler-Lehman graph kernels. Journal of Machine Learning Research, 12, 2539-2561.
• Verbeek, P., & Vliet, L.V. (1993). Curvature and bending energy in digitized 2D and 3D images. In 8th Scandinavian Conference on Image Analysis, Tromso, Norway.
• Wilson, R. C., & Algul, E. (2018). Categorization of RNA Molecules Using Graph Methods. In: X. Bai, E. Hancock, T. Ho, R. Wilson, B. Biggio, & A. Robles-Kelly (Eds) Structural, Syntactic, and Statistical Pattern Recognition. S+SSPR 2018. Lecture Notes in Computer Science, vol 11004 (pp. 439-448). Springer, Cham. doi:10.1007/978-3-319-97785-0_42
• x3dna.org. (n.d.). 3dna: a suite of software programs for the analysis, rebuilding and visualization of 3-dimensional nucleic acid structures. http://x3dna.org/ Access date: 20 March 2023.
• Xu, K., Li, C., Tian, Y., Sonobe, T., Kawarabayashi, K., & Jegelka, S. (2018). Representation learning on graphs with jumping knowledge networks. Proceedings of the 35th International Conference on Machine Learning, PMLR, 80, 5453-5462.
• Xu, K., Hu, W., Leskovec, J., & Jegelka, S. (2019). How powerful are graph neural networks? arXiv preprint, 1810.00826. doi:10.48550/arXiv.1810.00826
• Yang, H., Jossinet, F., Leontis, N., Chen, L., Westbrook, J., Berman, H., & Westhof, E. (2003). Tools for the automatic identification and classification of RNA base pairs. Nucleic Acids Research, 31(13), 3450-3460. doi:10.1093/nar/gkg529
• Zahran, M., Sevim Bayrak, C., Elmetwaly, S., & Schlick, T. (2015). RAG-3D: a search tool for RNA 3D substructures. Nucleic Acids Research, 43(19), 9474-9488. doi:10.1093/nar/gkv823
• Zhang, M., & Chen, Y. (2018). Link prediction based on graph neural networks. Advances in Neural Information Processing Systems, Curran Associates, Inc.
• Zhang, M., Cui, Z., Neumann, M., & Chen, Y. (2018). An end-to-end deep learning architecture for graph classification. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1), 4438-4445. doi:10.1609/aaai.v32i1.11782
• Zhang, S., Tong, H., Xu, J., & Maciejewski, R. (2019a). Graph convolutional networks: a comprehensive review. Computational Social Networks, 6(1), 11. doi:10.1186/s40649-019-0069-y
• Zhang, Z., Bu, J., Ester, M., Zhang, J., Yao, C., Yu, Z., & Wang, C. (2019b). Hierarchical graph pooling with structure learning. arXiv:1911.05954. doi:10.48550/arXiv.1911.05954
• Zhao, T., Zhang, X., & Wang, S. (2021). GraphSMOTE: Imbalanced node classification on graphs with graph neural networks. Proceedings of the 14th ACM International Conference on Web Search and Data Mining, 833-841. doi:10.1145/3437963.3441720