Related Experiment Video
Updated: Apr 4, 2026

Probing RNA Structure with Dimethyl Sulfate Mutational Profiling with Sequencing In Vitro and in Cells
Published on: December 9, 2022
Local Exact Pattern Matching for Non-Fixed RNA Structures
Abstract:
Detecting local common sequence-structure regions of RNAs is a biologically important problem. Detecting such regions allows biologists to identify functionally relevant similarities between the inspected molecules. We developed dynamic programming algorithms for finding common structure-sequence patterns between two RNAs. The RNAs are given by their sequence and a set of potential base pairs with associated probabilities. In contrast to prior work on local pattern matching of RNAs, we support the breaking of arcs. This allows us to add flexibility over matching only fixed structures; potentially matching only a similar subset of specified base pairs. We present an O(n(3)) algorithm for local exact pattern matching between two nested RNAs, and an O(n(3) log n) algorithm for one nested RNA and one bounded-unlimited RNA. In addition, an algorithm for approximate pattern matching is introduced that for two given nested RNAs and a number k, finds the maximal local pattern matching score between the two RNAs with at most k mismatches in O(n(3)k(2)) time. Finally, we present an O(n(3)) algorithm for finding the most similar subforest between two nested RNAs.
Related Concept Videos
RNA Structure
RNA Structure
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...
RNA Structure
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...
Nucleic Acid Structure
DNA Structure
DNA...
RNA-seq
Before the discovery of RNA-seq, microarray-based methods and Sanger sequencing were used for transcriptome analysis. However, while...
Ribosomal RNA Synthesis
Ribosome biogenesis begins with the synthesis of 5S and 45S pre-rRNAs by distinct RNA polymerases. The primary transcripts are extensively processed and modified before they are bound and folded by ribosomal proteins and assembly factors,...

