Document Open Access Logo

Automatic Exploration of the Natural Variability of RNA Non-Canonical Geometric Patterns with a Parameterized Sampling Technique

Authors Théo Boury , Yann Ponty , Vladimir Reinharz

PDF
Thumbnail PDF

File

LIPIcs.WABI.2023.20.pdf
  • Filesize: 2.73 MB
  • 22 pages

Document Identifiers

Author Details

Théo Boury
  • Computer Science Department, Ecole Normale Supérieure de Lyon, France
Yann Ponty
  • Laboratoire d'Informatique de l'Ecole Polytechnique (CNRS/LIX, UMR 7161), Institut Polytechnique de Paris, France
Vladimir Reinharz
  • Department of Computer Science, Université du Québec à Montréal, Canada

Funding

  • Ponty, Yann: PaRNAssum project from the French Agence Nationale de la Recherche (ANR-19-CE45-0023)
  • Reinharz, Vladimir: NSERC RGPIN-2020-05795, FRQS CBJ1

Cite As Get BibTex

Théo Boury, Yann Ponty, and Vladimir Reinharz. Automatic Exploration of the Natural Variability of RNA Non-Canonical Geometric Patterns with a Parameterized Sampling Technique. In 23rd International Workshop on Algorithms in Bioinformatics (WABI 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 273, pp. 20:1-20:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.WABI.2023.20

Abstract

Motivation. Recurrent substructures in RNA, known as 3D motifs, consist of networks of base pair interactions and are critical to understanding the relationship between structure and function. Their structure is naturally expressed as a graph which has led to many graph-based algorithms to automatically catalog identical motifs found in 3D structures. Yet, due to the complexity of the problem, state-of-the-art methods are often optimized to find exact matches, limiting the search to a subset of potential solutions, or do not allow explicit control over the desired variability.

Results. We developed FuzzTree, a method able to efficiently sample approximate instances of an RNA motif, abstracted as a subgraph within a target RNA structure. It is the first method that allows explicit control over (1) the admissible geometric variability in the interactions; (2) the number of missing edges; and (3) the introduction of discontinuities in the backbone given close distances in the 3D structure. Our tool relies on a multidimensional Boltzmann sampling, having complexity parameterized by the treewidth of the requested motif. We applied our method to the well-known internal loop Kink-Turn motif, which can be divided into 12 subgroups. Given only the graph representing the main Kink-Turn subgroup, FuzzTree retrieved over 3/4 of all kink-turns. We also highlighted two occurrences of new sampled patterns. Our tool is available as free software and can be customized for different parameters and types of graphs.

Subject Classification

ACM Subject Classification
  • Applied computing → Molecular structural biology
Keywords
  • Subgraph Isomorphism
  • 3D RNA
  • Parameterized Complexity
  • Tree Decomposition
  • Boltzmann sampling
  • Neighborhood metrics
  • Kink-Turn family

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844-856, July 1995. URL: https://doi.org/10.1145/210332.210337.
  2. Olivier Bodini and Yann Ponty. Multi-dimensional Boltzmann Sampling of Languages. Discrete Mathematics & Theoretical Computer Science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), January 2010. URL: https://doi.org/10.46298/dmtcs.2793.
  3. Hans L. Bodlaender and Arie M. C. A. Koster. Combinatorial optimization on graphs of bounded treewidth. The Computer Journal, 51(3):255-269, 2008. URL: https://doi.org/10.1093/comjnl/bxm037.
  4. Vincenzo Carletti, Pasquale Foggia, Alessia Saggese, and Mario Vento. Introducing vf3: A new algorithm for subgraph isomorphism. In Pasquale Foggia, Cheng-Lin Liu, and Mario Vento, editors, Graph-Based Representations in Pattern Recognition, pages 128-139, Cham, 2017. Springer International Publishing. Google Scholar
  5. Thomas R Cech and Joan A Steitz. The noncoding RNA revolution - Trashing old rules to forge new ones. Cell, 157(1):77-94, 2014. Google Scholar
  6. G Chojnowski, T Waleń, and JM Bujnicki. RNA Bricks - A database of RNA 3D motifs and their interactions. Nucleic Acids Research, 42, 2013. URL: https://doi.org/10.1093/nar/gkt1084.
  7. Luigi Cordella, Pasquale Foggia, Carlo Sansone, and Mario Vento. A (sub)graph isomorphism algorithm for matching large graphs. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 26:1367-1372, November 2004. URL: https://doi.org/10.1109/TPAMI.2004.75.
  8. José Almeida Cruz and Eric Westhof. The dynamic landscapes of RNA architecture. Cell, 136(4):604-609, 2009. Google Scholar
  9. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2016. Google Scholar
  10. Rhiju Das, Rachael C Kretsch, Adam J Simpkin, Thomas Mulvaney, Phillip Pham, Ramya Rangan, Fan Bu, Ronan Keegan, Maya Topf, Daniel Rigden, et al. Assessment of three-dimensional RNA structure prediction in CASP15. bioRxiv, pages 2023-04, 2023. Google Scholar
  11. Sven Findeiß, Christoph Flamm, and Yann Ponty. Rational Design of RiboNucleic Acids (Dagstuhl Seminar 22381). Dagstuhl Reports, 12(9):121-149, 2023. URL: https://doi.org/10.4230/DagRep.12.9.121.
  12. Nagoor Gani. 63. isomorphism on fuzzy graphs. International Journal of Computational and Mathematical Sciences, Vol. 2:200-206, January 2008. URL: https://doi.org/10.13140/2.1.1873.9847.
  13. M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  14. Aric Hagberg, Pieter Swart, and Daniel S Chult. Exploring network structure, dynamics, and function using NetworkX. Technical report, Los Alamos National Lab.(LANL), Los Alamos, NM (United States), 2008. Google Scholar
  15. S. Hammer, W. Wang, S. Will, and Y. Ponty. Fixed-parameter tractable sampling for rna design with multiple target structures. BMC Bioinformatics, 2019. Google Scholar
  16. Lin Huang and David MJ Lilley. The kink turn, a key architectural element in RNA structure. Journal of molecular biology, 428(5):790-801, 2016. Google Scholar
  17. Alpár Jüttner and Péter Madarasi. Vf2++ - An improved subgraph isomorphism algorithm. Discrete Applied Mathematics, 242:69-81, 2018. Computational Advances in Combinatorial Optimization. URL: https://doi.org/10.1016/j.dam.2018.02.018.
  18. Arijit Khan, Nan Li, Xifeng Yan, Ziyu Guan, Supriyo Chakraborty, and Shu Tao. Neighborhood based fast graph search in large networks. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, SIGMOD '11, pages 901-912, New York, NY, USA, 2011. Association for Computing Machinery. URL: https://doi.org/10.1145/1989323.1989418.
  19. Daniel J Klein, T Martin Schmeing, Peter B Moore, and Thomas A Steitz. The kink-turn: a new RNA secondary structure motif. The EMBO journal, 20(15):4214-4221, 2001. Google Scholar
  20. Neocles B Leontis, Aurelie Lescoute, and Eric Westhof. The building blocks and motifs of RNA architecture. Current Opinion in Structural Biology, 16(3):279-287, 2006. Nucleic acids/Sequences and topology. URL: https://doi.org/10.1016/j.sbi.2006.05.009.
  21. Neocles B Leontis and Eric Westhof. Geometric nomenclature and classification of RNA base pairs. Rna, 7(4):499-512, 2001. Google Scholar
  22. Bin Li, Shurong Liu, Wujian Zheng, Anrui Liu, Peng Yu, Di Wu, Jie Zhou, Ping Zhang, Chang Liu, Qiao Lin, et al. RIP-PEN-seq identifies a class of kink-turn RNAs as splicing regulators. Nature Biotechnology, pages 1-13, 2023. Google Scholar
  23. Dániel Marx and Michal Pilipczuk. Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask). In Ernst W. Mayr and Natacha Portier, editors, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), volume 25 of Leibniz International Proceedings in Informatics (LIPIcs), pages 542-553, Dagstuhl, Germany, 2014. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.STACS.2014.542.
  24. Carlos Oliver, Vincent Mallet, Pericles Philippopoulos, William L Hamilton, and Jérôme Waldispühl. Vernal: a tool for mining fuzzy network motifs in RNA. Bioinformatics, 38(4):970-976, November 2021. URL: https://doi.org/10.1093/bioinformatics/btab768.
  25. Aymeric Perchant and Isabelle Bloch. Fuzzy morphisms between graphs. Fuzzy Sets and Systems, 128(2):149-168, 2002. URL: https://doi.org/10.1016/S0165-0114(01)00131-2.
  26. Anton I. Petrov, Craig L. Zirbel, and Neocles B. Leontis. Automated classification of rna 3d motifs and the rna 3d motif atlas. RNA, 2013. Google Scholar
  27. Vladimir Reinharz, Antoine Soulé, Eric Westhof, Jérôme Waldispühl, and Alain Denise. Mining for recurrent long-range interactions in RNA structures reveals embedded hierarchies in network families. Nucleic Acids Research, 46(8):3841-3851, March 2018. URL: https://doi.org/10.1093/nar/gky197.
  28. Philippe Rinaudo, Yann Ponty, Dominique Barth, and Alain Denise. Tree decomposition and parameterized algorithms for rna structure-sequence alignment including tertiary interactions and pseudoknots. In Ben Raphael and Jijun Tang, editors, Algorithms in Bioinformatics, pages 149-164, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. Google Scholar
  29. Michael Sarver, Craig L Zirbel, Jesse Stombaugh, Ali Mokdad, and Neocles B Leontis. FR3D: finding local and composite recurrent structural motifs in RNA 3D structures. Journal of mathematical biology, 56:215-252, 2008. Google Scholar
  30. Antoine Soulé, Vladimir Reinharz, Roman Sarrazin-Gendron, Alain Denise, and Jérôme Waldispühl. Finding recurrent RNA structural networks with fast maximal common subgraphs of edge-colored graphs. PLoS computational biology, 17(5):e1008990, 2021. Google Scholar
  31. Jesse Stombaugh, Craig L. Zirbel, Eric Westhof, and Neocles B. Leontis. Frequency and isostericity of RNA base pairs. Nucleic Acids Research, 37(7):2294-2312, February 2009. URL: https://doi.org/10.1093/nar/gkp011.
  32. Bernhard C Thiel, Irene K Beckmann, Peter Kerpedjiev, and Ivo L Hofacker. 3D based on 2D: Calculating helix angles and stacking patterns using forgi 2.0, an RNA Python library centered on secondary structure elements. F1000Research, 8, 2019. Google Scholar
  33. Hua-Ting Yao, Yann Ponty, and Sebastian Will. Developing complex rna design applications in the infrared framework. RNA Folding - Methods and Protocols, 2022. Google Scholar
  34. M. Zahran, C. Sevim Bayrak, S. Elmetwaly, and T. Schlick. RAG-3D: a search tool for RNA 3D substructures. Nucleic acids research. Nucleic Acids Research, 43(19):9474-9488, 2015. URL: https://doi.org/10.1093/nar/gkv823.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact