{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T06:15:26Z","timestamp":1772172926675,"version":"3.50.1"},"update-to":[{"DOI":"10.1371\/journal.pcbi.1008990","type":"new_version","label":"New version","source":"publisher","updated":{"date-parts":[[2021,6,10]],"date-time":"2021-06-10T00:00:00Z","timestamp":1623283200000}}],"reference-count":41,"publisher":"Public Library of Science (PLoS)","issue":"5","license":[{"start":{"date-parts":[[2021,5,28]],"date-time":"2021-05-28T00:00:00Z","timestamp":1622160000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["RGPIN-2015-03786"],"award-info":[{"award-number":["RGPIN-2015-03786"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["RGPAS 477873-15"],"award-info":[{"award-number":["RGPAS 477873-15"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["RGPIN-2020-05874"],"award-info":[{"award-number":["RGPIN-2020-05874"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Genome Canada [BCB 2015]"},{"DOI":"10.13039\/501100000024","name":"Canadian Institutes of Health Research","doi-asserted-by":"publisher","award":["BOP-149429"],"award-info":[{"award-number":["BOP-149429"]}],"id":[{"id":"10.13039\/501100000024","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003151","name":"Fonds de Recherche du Qu\u00e9bec - Nature et Technologies","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003151","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100010446","name":"Institute for Basic Science","doi-asserted-by":"crossref","award":["IBS-R020"],"award-info":[{"award-number":["IBS-R020"]}],"id":[{"id":"10.13039\/501100010446","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"crossref","award":["RGPIN-2020-05795"],"award-info":[{"award-number":["RGPIN-2020-05795"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["www.ploscompbiol.org"],"crossmark-restriction":false},"short-container-title":["PLoS Comput Biol"],"abstract":"<jats:p>\n                    RNA tertiary structure is crucial to its many non-coding molecular functions. RNA architecture is shaped by its secondary structure composed of stems, stacked canonical base pairs, enclosing loops. While stems are precisely captured by free-energy models, loops composed of non-canonical base pairs are not. Nor are distant interactions linking together those secondary structure elements (SSEs). Databases of conserved 3D geometries (a.k.a. modules) not captured by energetic models are leveraged for structure prediction and design, but the computational complexity has limited their study to local elements, loops. Representing the RNA structure as a graph has recently allowed to expend this work to pairs of SSEs, uncovering a hierarchical organization of these 3D modules, at great computational cost. Systematically capturing recurrent patterns on a large scale is a main challenge in the study of RNA structures. In this paper, we present an efficient algorithm to compute maximal isomorphisms in edge colored graphs. We extend this algorithm to a framework well suited to identify RNA modules, and fast enough to considerably generalize previous approaches. To exhibit the versatility of our framework, we first reproduce results identifying all common modules spanning more than 2 SSEs, in a few hours instead of weeks. The efficiency of our new algorithm is demonstrated by computing the maximal modules between any pair of entire RNA in the non-redundant corpus of known RNA 3D structures. We observe that the biggest modules our method uncovers compose large shared sub-structure spanning hundreds of nucleotides and base pairs between the ribosomes of\n                    <jats:italic>Thermus thermophilus<\/jats:italic>\n                    ,\n                    <jats:italic>Escherichia Coli<\/jats:italic>\n                    , and\n                    <jats:italic>Pseudomonas aeruginosa<\/jats:italic>\n                    .\n                  <\/jats:p>","DOI":"10.1371\/journal.pcbi.1008990","type":"journal-article","created":{"date-parts":[[2021,5,28]],"date-time":"2021-05-28T15:55:44Z","timestamp":1622217344000},"page":"e1008990","update-policy":"https:\/\/doi.org\/10.1371\/journal.pcbi.corrections_policy","source":"Crossref","is-referenced-by-count":12,"title":["Finding recurrent RNA structural networks with fast maximal common subgraphs of edge-colored graphs"],"prefix":"10.1371","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4810-4821","authenticated-orcid":true,"given":"Antoine","family":"Soul\u00e9","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8481-1094","authenticated-orcid":true,"given":"Vladimir","family":"Reinharz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0291-547X","authenticated-orcid":true,"given":"Roman","family":"Sarrazin-Gendron","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4484-4996","authenticated-orcid":true,"given":"Alain","family":"Denise","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2561-7117","authenticated-orcid":true,"given":"J\u00e9r\u00f4me","family":"Waldisp\u00fchl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"340","published-online":{"date-parts":[[2021,5,28]]},"reference":[{"issue":"9","key":"pcbi.1008990.ref001","doi-asserted-by":"crossref","first-page":"961","DOI":"10.1016\/S0300-9084(02)01463-3","article-title":"Motif prediction in ribosomal RNAs Lessons and prospects for automated motif prediction in homologous RNA molecules","volume":"84","author":"NB Leontis","year":"2002","journal-title":"Biochimie"},{"issue":"8","key":"pcbi.1008990.ref002","doi-asserted-by":"crossref","first-page":"993","DOI":"10.1016\/j.biochi.2006.05.018","article-title":"The A-minor motifs in the decoding recognition process","volume":"88","author":"A Lescoute","year":"2006","journal-title":"Biochimie"},{"issue":"22","key":"pcbi.1008990.ref003","doi-asserted-by":"crossref","first-page":"6587","DOI":"10.1093\/nar\/gkl963","article-title":"The interaction networks of structured RNAs","volume":"34","author":"A Lescoute","year":"2006","journal-title":"Nucleic Acids Research"},{"issue":"8","key":"pcbi.1008990.ref004","doi-asserted-by":"crossref","first-page":"2395","DOI":"10.1093\/nar\/gki535","article-title":"Recurrent structural RNA motifs, isostericity matrices and sequence alignments","volume":"33","author":"A Lescoute","year":"2005","journal-title":"Nucleic Acids Research"},{"issue":"10","key":"pcbi.1008990.ref005","doi-asserted-by":"crossref","first-page":"1327","DOI":"10.1261\/rna.039438.113","article-title":"Automated classification of RNA 3D motifs and the RNA 3D Motif Atlas","volume":"19","author":"AI Petrov","year":"2013","journal-title":"RNA"},{"issue":"3","key":"pcbi.1008990.ref006","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1016\/S0959-440X(03)00076-9","article-title":"Analysis of RNA motifs","volume":"13","author":"NB Leontis","year":"2003","journal-title":"Current opinion in structural biology"},{"issue":"12","key":"pcbi.1008990.ref007","doi-asserted-by":"crossref","first-page":"i207","DOI":"10.1093\/bioinformatics\/bts226","article-title":"Towards 3D structure prediction of large RNA molecules: an integer programming framework to insert local 3D motifs in RNA secondary structure","volume":"28","author":"V Reinharz","year":"2012","journal-title":"Bioinformatics"},{"issue":"4","key":"pcbi.1008990.ref008","doi-asserted-by":"crossref","first-page":"R78","DOI":"10.1016\/S1359-0278(96)00037-5","article-title":"RNA tectonics: towards RNA design","volume":"1","author":"E Westhof","year":"1996","journal-title":"Fold Des"},{"issue":"11","key":"pcbi.1008990.ref009","doi-asserted-by":"crossref","first-page":"e104","DOI":"10.1093\/nar\/gkw217","article-title":"Combining structure probing data on RNA mutants with evolutionary information reveals RNA-binding interfaces","volume":"44","author":"V Reinharz","year":"2016","journal-title":"Nucleic Acids Research"},{"issue":"4","key":"pcbi.1008990.ref010","doi-asserted-by":"crossref","first-page":"e29","DOI":"10.1093\/nar\/gkn1044","article-title":"Finding 3D motifs in ribosomal RNA structures","volume":"37","author":"A Apostolico","year":"2009","journal-title":"Nucleic Acids Research"},{"issue":"12","key":"pcbi.1008990.ref011","doi-asserted-by":"crossref","first-page":"2489","DOI":"10.1261\/rna.1061108","article-title":"Automated motif extraction and classification in RNA tertiary structures","volume":"14","author":"M Djelloul","year":"2008","journal-title":"RNA"},{"issue":"16","key":"pcbi.1008990.ref012","doi-asserted-by":"crossref","first-page":"4755","DOI":"10.1093\/nar\/gkg682","article-title":"RNA structure comparison, motif search and discovery using a reduced representation of RNA conformational space","volume":"31","author":"CM Duarte","year":"2003","journal-title":"Nucleic Acids Research"},{"issue":"5","key":"pcbi.1008990.ref013","doi-asserted-by":"crossref","first-page":"919","DOI":"10.1006\/jmbi.2001.4626","article-title":"Quantitative analysis of nucleic acid three-dimensional structures","volume":"308","author":"P Gendron","year":"2001","journal-title":"Journal of molecular biology"},{"issue":"8","key":"pcbi.1008990.ref014","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1023\/B:JCAM.0000004603.15856.32","article-title":"Representation, searching and discovery of patterns of bases in complex RNA structures","volume":"17","author":"AM Harrison","year":"2003","journal-title":"Journal of computer-aided molecular design"},{"issue":"4","key":"pcbi.1008990.ref015","doi-asserted-by":"crossref","first-page":"412","DOI":"10.1261\/rna.7104605","article-title":"The application of cluster analysis in the intercomparison of loop structures in RNA","volume":"11","author":"HC Huang","year":"2005","journal-title":"RNA"},{"issue":"suppl_2","key":"pcbi.1008990.ref016","doi-asserted-by":"crossref","first-page":"W50","DOI":"10.1093\/nar\/gkr249","article-title":"WebFR3D\u2014a server for finding, aligning and analyzing recurrent RNA 3D motifs","volume":"39","author":"AI Petrov","year":"2011","journal-title":"Nucleic acids research"},{"issue":"11","key":"pcbi.1008990.ref017","doi-asserted-by":"crossref","first-page":"3512","DOI":"10.1093\/nar\/gkq074","article-title":"Arrangement of 3D structural motifs in ribosomal RNA","volume":"38","author":"K Sargsyan","year":"2010","journal-title":"Nucleic Acids Research"},{"issue":"1","key":"pcbi.1008990.ref018","first-page":"215","article-title":"FR3D: finding local and composite recurrent structural motifs in RNA 3D structures","volume":"56","author":"M Sarver","year":"2008","journal-title":"Journal of mathematical biology"},{"issue":"22","key":"pcbi.1008990.ref019","doi-asserted-by":"crossref","first-page":"6650","DOI":"10.1093\/nar\/gkh1002","article-title":"The identification of novel RNA structural motifs using COMPADRES: an automated approach to structural discovery","volume":"32","author":"LM Wadley","year":"2004","journal-title":"Nucleic Acids Research"},{"issue":"18","key":"pcbi.1008990.ref020","doi-asserted-by":"crossref","first-page":"e176","DOI":"10.1093\/nar\/gkq672","article-title":"RNAMotifScan: automatic identification of RNA structural motifs using secondary structural alignment","volume":"38","author":"C Zhong","year":"2010","journal-title":"Nucleic Acids Research"},{"issue":"6","key":"pcbi.1008990.ref021","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1038\/nmeth.1603","article-title":"Sequence-based identification of 3D structural modules in RNA with RMDetect","volume":"8","author":"JA Cruz","year":"2011","journal-title":"Nature methods"},{"issue":"D1","key":"pcbi.1008990.ref022","doi-asserted-by":"crossref","first-page":"D266","DOI":"10.1093\/nar\/gkv1186","article-title":"InterRNA: a database of base interactions in RNA structures","volume":"44","author":"SD Appasamy","year":"2015","journal-title":"Nucleic acids research"},{"issue":"4","key":"pcbi.1008990.ref023","doi-asserted-by":"crossref","first-page":"1384","DOI":"10.1093\/nar\/gki267","article-title":"Modular RNA architecture revealed by computational analysis of existing pseudoknots and ribosomal RNAs","volume":"33","author":"S Pasquali","year":"2005","journal-title":"Nucleic acids research"},{"issue":"3","key":"pcbi.1008990.ref024","doi-asserted-by":"crossref","first-page":"107438","DOI":"10.1016\/j.jsb.2019.107438","article-title":"Inverse folding with RNA-As-Graphs produces a large pool of candidate sequences with target topologies","volume":"209","author":"S Jain","year":"2020","journal-title":"Journal of structural biology"},{"issue":"D1","key":"pcbi.1008990.ref025","doi-asserted-by":"crossref","first-page":"D123","DOI":"10.1093\/nar\/gkt1084","article-title":"RNA Bricks\u2014a database of RNA 3D motifs and their interactions","volume":"42","author":"G Chojnowski","year":"2014","journal-title":"Nucleic Acids Research"},{"issue":"9","key":"pcbi.1008990.ref026","doi-asserted-by":"crossref","first-page":"4899","DOI":"10.1073\/pnas.081082398","article-title":"RNA tertiary interactions in the large ribosomal subunit: the A-minor motif","volume":"98","author":"P Nissen","year":"2001","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"12","key":"pcbi.1008990.ref027","doi-asserted-by":"crossref","first-page":"2465","DOI":"10.1261\/rna.1249208","article-title":"Annotation of tertiary interactions in RNA structures reveals variations and correlations","volume":"14","author":"Y Xin","year":"2008","journal-title":"RNA"},{"issue":"8","key":"pcbi.1008990.ref028","doi-asserted-by":"crossref","first-page":"3841","DOI":"10.1093\/nar\/gky197","article-title":"Mining for recurrent long-range interactions in RNA structures reveals embedded hierarchies in network families","volume":"46","author":"V Reinharz","year":"2018","journal-title":"Nucleic Acids Research"},{"key":"pcbi.1008990.ref029","unstructured":"Petrov A. RNA 3D Motifs: Identification, Clustering, and Analysis [Ph.D. dissertation]. Bowling Green State University; 2012."},{"issue":"4","key":"pcbi.1008990.ref030","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1017\/S1355838201002515","article-title":"Geometric nomenclature and classification of RNA base pairs","volume":"7","author":"NB Leontis","year":"2001","journal-title":"RNA"},{"issue":"3","key":"pcbi.1008990.ref031","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1261\/rna.881308","article-title":"From knotted to nested RNA structures: a variety of computational methods for pseudoknot removal","volume":"14","author":"S Smit","year":"2008","journal-title":"RNA"},{"issue":"8","key":"pcbi.1008990.ref032","doi-asserted-by":"crossref","first-page":"R171","DOI":"10.1186\/gb-2007-8-8-r171","article-title":"PyCogent: a toolkit for making sense from sequence","volume":"8","author":"R Knight","year":"2007","journal-title":"Genome Biology"},{"issue":"7183","key":"pcbi.1008990.ref033","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1038\/nature06684","article-title":"The MC-Fold and MC-Sym pipeline infers RNA structure from sequence data","volume":"452","author":"M Parisien","year":"2008","journal-title":"Nature"},{"issue":"15","key":"pcbi.1008990.ref034","doi-asserted-by":"crossref","first-page":"7504","DOI":"10.1093\/nar\/gkv651","article-title":"Identifying novel sequence variants of RNA 3D motifs","volume":"43","author":"CL Zirbel","year":"2015","journal-title":"Nucleic acids research"},{"key":"pcbi.1008990.ref035","first-page":"834762","article-title":"Stochastic Sampling of Structural Contexts Improves the Scalability and Accuracy of RNA 3D Modules Identification","author":"R Sarrazin-Gendron","year":"2019","journal-title":"bioRxiv"},{"issue":"11","key":"pcbi.1008990.ref036","doi-asserted-by":"crossref","first-page":"2575","DOI":"10.1093\/nar\/30.11.2575","article-title":"Tracing the evolution of RNA structure in ribosomes","volume":"30","author":"G Caetano-Anoll\u00e9s","year":"2002","journal-title":"Nucleic Acids Res"},{"issue":"7232","key":"pcbi.1008990.ref037","doi-asserted-by":"crossref","first-page":"977","DOI":"10.1038\/nature07749","article-title":"A hierarchical model for evolution of 23S ribosomal RNA","volume":"457","author":"K Bokov","year":"2009","journal-title":"Nature"},{"issue":"28","key":"pcbi.1008990.ref038","doi-asserted-by":"crossref","first-page":"10251","DOI":"10.1073\/pnas.1407205111","article-title":"Evolution of the ribosome at atomic resolution","volume":"111","author":"AS Petrov","year":"2014","journal-title":"Proc Natl Acad Sci U S A"},{"issue":"2","key":"pcbi.1008990.ref039","doi-asserted-by":"crossref","first-page":"e1006801","DOI":"10.1371\/journal.ppat.1006801","article-title":"RNA 3-dimensional structural motifs as a critical constraint of viroid RNA evolution","volume":"14","author":"Y Wang","year":"2018","journal-title":"PLoS Pathog"},{"issue":"3","key":"pcbi.1008990.ref040","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1002\/bip.10525","article-title":"Structural motifs in ribosomal RNAs: implications for RNA design and genomics","volume":"73","author":"J Zorn","year":"2004","journal-title":"Biopolymers"},{"issue":"12","key":"pcbi.1008990.ref041","doi-asserted-by":"crossref","first-page":"1534","DOI":"10.1093\/bioinformatics\/btl113","article-title":"GenRGenS: software for generating random genomic sequences and structures","volume":"22","author":"Y Ponty","year":"2006","journal-title":"Bioinformatics"}],"updated-by":[{"DOI":"10.1371\/journal.pcbi.1008990","type":"new_version","label":"New version","source":"publisher","updated":{"date-parts":[[2021,6,10]],"date-time":"2021-06-10T00:00:00Z","timestamp":1623283200000}}],"container-title":["PLOS Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1008990","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,10]],"date-time":"2021-06-10T20:08:32Z","timestamp":1623355712000},"score":1,"resource":{"primary":{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1008990"}},"subtitle":[],"editor":[{"given":"Tamar","family":"Schlick","sequence":"first","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2021,5,28]]},"references-count":41,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2021,5,28]]}},"URL":"https:\/\/doi.org\/10.1371\/journal.pcbi.1008990","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2020.02.02.930453","asserted-by":"object"}]},"ISSN":["1553-7358"],"issn-type":[{"value":"1553-7358","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,28]]}}}