Finding recurrent RNA structural networks with fast maximal common subgraphs of edge-colored graphs
Antoine Soulé1,2, Vladimir Reinharz3, Roman Sarrazin-Gendron1
1School of Computer Science, McGill University, Montréal, Canada.
Plos Computational Biology
|May 28, 2021
Summary
This study introduces an efficient graph algorithm to identify recurring RNA structural motifs. The method significantly speeds up the discovery of large, shared substructures across diverse RNA molecules, aiding in understanding RNA architecture.
Area of Science:
- Computational Biology
- Structural Biology
- Bioinformatics
Background:
- RNA tertiary structure is vital for non-coding molecular functions.
- Current models accurately capture stems but struggle with non-canonical loops and distant interactions.
- Existing methods for identifying 3D RNA modules are computationally intensive, limiting studies to local elements.
Purpose of the Study:
- To develop an efficient algorithm for identifying RNA structural modules.
- To enable large-scale systematic analysis of recurrent RNA patterns.
- To generalize and accelerate the study of RNA 3D architecture.
Main Methods:
- Representing RNA structures as edge-colored graphs.
- Developing an efficient algorithm to compute maximal isomorphisms in these graphs.
- Extending the algorithm into a framework for identifying RNA modules.
Main Results:
- The new algorithm identifies common RNA modules spanning over 2 secondary structure elements (SSEs) in hours, a task previously taking weeks.
- The framework successfully computed maximal modules between entire RNA structures in a large dataset.
- Identified large shared substructures spanning hundreds of nucleotides and base pairs in bacterial ribosomes.
Conclusions:
- The developed algorithm offers a computationally efficient approach to RNA module identification.
- This framework significantly advances the scale and speed of RNA 3D structure analysis.
- The findings highlight conserved, large-scale structural similarities across different bacterial ribosomes.
Related Concept Videos
01:24Sequence Networks of Rotating Machines
218
A Y-connected synchronous generator, grounded through a neutral impedance, is designed to produce balanced internal phase voltages with only positive-sequence components. The generator's sequence networks include a source voltage that is exclusively in the positive-sequence network. The sequence components of line-to-ground voltages at the generator terminals illustrate this configuration.
Zero-sequence current induces a voltage drop across the generator's neutral impedance and other...
Zero-sequence current induces a voltage drop across the generator's neutral impedance and other...
218
01:19RNA Structure
5.8K
The basic structure of RNA consists of a string of ribonucleotides attached by phosphodiester bonds. Although most RNA is single-stranded, it can form complex secondary and tertiary structures. Such structures play essential roles in the regulation of transcription and translation.
Different Types of RNA Have the Same Basic Structure
There are three main types of ribonucleic acid (RNA) involved in protein synthesis: messenger RNA (mRNA), transfer RNA (tRNA), and ribosomal RNA (rRNA). All three...
Different Types of RNA Have the Same Basic Structure
There are three main types of ribonucleic acid (RNA) involved in protein synthesis: messenger RNA (mRNA), transfer RNA (tRNA), and ribosomal RNA (rRNA). All three...
5.8K
01:23RNA Structure
76.2K
Overview
The basic structure of RNA consists of a five-carbon sugar and one of four nitrogenous bases. Although most RNA is single-stranded, it can form complex secondary and tertiary structures. Such structures play essential roles in the regulation of transcription and translation.
Different Types of RNA Have the Same Basic Structure
There are three main types of ribonucleic acid (RNA): messenger RNA (mRNA), transfer RNA (tRNA), and ribosomal RNA (rRNA). All three RNA types consist of a...
The basic structure of RNA consists of a five-carbon sugar and one of four nitrogenous bases. Although most RNA is single-stranded, it can form complex secondary and tertiary structures. Such structures play essential roles in the regulation of transcription and translation.
Different Types of RNA Have the Same Basic Structure
There are three main types of ribonucleic acid (RNA): messenger RNA (mRNA), transfer RNA (tRNA), and ribosomal RNA (rRNA). All three RNA types consist of a...
76.2K
02:26Protein Networks
4.2K
An organism can have thousands of different proteins, and these proteins must cooperate to ensure the health of an organism. Proteins bind to other proteins and form complexes to carry out their functions. Many proteins interact with multiple other proteins creating a complex network of protein interactions.
These interactions can be represented through maps depicting protein-protein interaction networks, represented as nodes and edges. Nodes are circles that are representative of a protein,...
These interactions can be represented through maps depicting protein-protein interaction networks, represented as nodes and edges. Nodes are circles that are representative of a protein,...
4.2K
02:26Protein Networks
2.5K
2.5K
03:21RNA-seq
10.8K
RNA sequencing, or RNA-Seq, is a high-throughput sequencing technology used to study the transcriptome of a cell. Transcriptomics helps to interpret the functional elements of a genome and identify the molecular constituents of an organism. Additionally, it also helps in understanding the development of an organism and the occurrence of diseases.
Before the discovery of RNA-seq, microarray-based methods and Sanger sequencing were used for transcriptome analysis. However, while...
Before the discovery of RNA-seq, microarray-based methods and Sanger sequencing were used for transcriptome analysis. However, while...
10.8K