Related Experiment Video
Updated: May 22, 2026
10:34
Probing RNA Structure with Dimethyl Sulfate Mutational Profiling with Sequencing In Vitro and in Cells
Published on: December 9, 2022
Cache-efficient and vectorized parallel dynamic programming for RNA folding.
Mateusz Gruzewski1, Marek Palkowski1
1West Pomeranian University of Technology in Szczecin, Szczecin, Poland.
Plos One
|May 20, 2026
Summary
This study presents an efficient OpenMP implementation of the Nussinov RNA folding algorithm, achieving significant speedups on multi-core processors. The optimized code serves as a template for dynamic programming, outperforming existing methods.
Area of Science:
- Computational Biology
- High-Performance Computing
- Algorithm Optimization
Background:
- The Nussinov algorithm is a key dynamic programming method for RNA secondary structure prediction.
- Existing implementations often struggle with performance on modern parallel architectures.
- Non-serial polyadic dynamic programming (NPDP) poses challenges for efficient parallelization.
Purpose of the Study:
- To develop an efficient and concise OpenMP implementation of the Nussinov RNA folding algorithm.
- To create a template for optimizing related dynamic programming applications.
- To enhance data locality and computational efficiency on multi-core processors.
Main Methods:
- Analysis of manual implementations to separate computational patterns.
- Structuring computations analogously to matrix multiplication for data locality.
- Leveraging cache-aware tiling, parallelism, and explicit vectorization (Advanced Vector Extensions - AVX).
- Utilizing Presburger arithmetic and the polyhedral model for semi-automatic data locality extraction.
Main Results:
- Achieved performance significantly exceeding automatically generated and manually tuned implementations.
- Execution times up to two orders of magnitude faster than polyhedral code.
- Outperformed array transposition (30x faster) and tiled sparsified Four Russians (5x faster) variants.
- CPU implementations showed comparable performance to GPU counterparts.
Conclusions:
- The proposed OpenMP implementation offers substantial performance gains for the Nussinov algorithm.
- The approach demonstrates the effectiveness of cache-aware tiling, parallelism, and vectorization on modern CPUs.
- Advanced Vector Extensions (AVX) are crucial for exploiting multi-core processor capabilities, especially AMD Epyc.
- The implementation serves as a valuable template for optimizing NPDP algorithms.
Related Concept Videos
01:29Protein Folding Quality Check in the RER
ER is the primary site for the maturation and folding of soluble and transmembrane secretory proteins. The calnexin cycle is a specific chaperone system that folds and assesses the confirmation of N-glycosylated proteins before they can exit the ER lumen. The primary players of this quality check pipeline are the lectins, ER-resident chaperones, and a glucosyl transferase enzyme. In case the calnexin system in the lumen fails to salvage a misfolded protein, it is transported to the cytoplasm...
01:22Protein Folding
Overview
01:25Protein Folding
Proteins are chains of amino acids linked together by peptide bonds. Upon synthesis, a protein folds into a three-dimensional conformation, critical to its biological function. Interactions between its constituent amino acids guide protein folding, and hence the protein structure is primarily dependent on its amino acid sequence.
Protein Structure Is Critical to Its Biological Function
Proteins perform a wide range of biological functions such as catalyzing chemical reactions, providing...
Protein Structure Is Critical to Its Biological Function
Proteins perform a wide range of biological functions such as catalyzing chemical reactions, providing...
01:22Protein Folding
Overview
01:19RNA Structure
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...
01:23RNA Structure
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...