Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Concept Videos

Protein Folding Quality Check in the RER01:29

Protein Folding Quality Check in the RER

4.9K
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...
4.9K
RNA Structure01:23

RNA Structure

78.6K
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...
78.6K
RNA Structure01:19

RNA Structure

6.7K
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...
6.7K
RNA Stability01:53

RNA Stability

35.5K
Intact DNA strands can be found in fossils, while scientists sometimes struggle to keep RNA intact under laboratory conditions. The structural variations between RNA and DNA underlie the differences in their stability and longevity. Because DNA is double-stranded, it is inherently more stable. The single-stranded structure of RNA is less stable but also more flexible and can form weak internal bonds. Additionally, most RNAs in the cell are relatively short, while DNA can be up to 250 million...
35.5K
Protein Folding01:25

Protein Folding

10.8K
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...
10.8K
Protein Folding01:22

Protein Folding

125.6K
Overview
125.6K

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Inferring binding specificities of human transcription factors with the wisdom of crowds.

bioRxiv : the preprint server for biology·2025
Same author

Cross-platform motif discovery and benchmarking to explore binding specificities of poorly studied human transcription factors.

Communications biology·2025
Same author

Codes across (life)sciences.

Bio Systems·2025
Same author

Biologically relevant integration of transcriptomics profiles from cancer cell lines, patient-derived xenografts, and clinical tumors using deep learning.

Science advances·2025
Same author

Extensive binding of uncharacterized human transcription factors to genomic dark matter.

bioRxiv : the preprint server for biology·2024
Same author

Cross-platform DNA motif discovery and benchmarking to explore binding specificities of poorly studied human transcription factors.

bioRxiv : the preprint server for biology·2024
Same journal

CNV-ECOD: A copy number variation detection method based on ECOD algorithm using next-generation sequencing data.

Journal of bioinformatics and computational biology·2026
Same journal

ReinVar: A model-free paradigm-based reinforcement learning approach to detect copy number variation.

Journal of bioinformatics and computational biology·2026
Same journal

When pipelines run but coordinates fail: A simple spatial specificity check for false locality in post-GWAS analysis.

Journal of bioinformatics and computational biology·2026
Same journal

Comparative benchmarking of template-based, evolutionary-diffusion, and generative language models for IsPETase structure prediction.

Journal of bioinformatics and computational biology·2026
Same journal

Trap spaces as labelled ideals of SCC posets: A structural-functional theory of reachability in asynchronous boolean networks.

Journal of bioinformatics and computational biology·2026
Same journal

Erratum - DDINet: Drug-drug interaction prediction network based on multi-molecular fingerprint features and multi-head attention centered weighted autoencoder.

Journal of bioinformatics and computational biology·2026
See all related articles

Related Experiment Video

Updated: Dec 31, 2025

Probing RNA Structure with Dimethyl Sulfate Mutational Profiling with Sequencing In Vitro and in Cells
10:34

Probing RNA Structure with Dimethyl Sulfate Mutational Profiling with Sequencing In Vitro and in Cells

Published on: December 9, 2022

5.0K

Practicality and time complexity of a sparsified RNA folding algorithm.

Slavica Dimitrieva1, Philipp Bucher

  • 1Swiss Institute of Bioinformatics and Swiss Institute for Experimental Cancer Research, Swiss Federal Institute of Technology, Lausanne, 1015, Switzerland. slavica.dimitrieva@epfl.ch

Journal of Bioinformatics and Computational Biology
|July 20, 2012
PubMed
Summary
This summary is machine-generated.

RNA folding programs, while simplified, do not achieve O(n(2)) time complexity as claimed. However, this sparsification technique still offers significant speed improvements for RNA folding and base pairing optimization.

More Related Videos

Practical Aspects of Sample Preparation and Setup of 1H R1ρ Relaxation Dispersion Experiments of RNA
08:17

Practical Aspects of Sample Preparation and Setup of 1H R1ρ Relaxation Dispersion Experiments of RNA

Published on: July 9, 2021

5.1K
RNA Secondary Structure Prediction Using High-throughput SHAPE
13:42

RNA Secondary Structure Prediction Using High-throughput SHAPE

Published on: May 31, 2013

32.1K

Related Experiment Videos

Last Updated: Dec 31, 2025

Probing RNA Structure with Dimethyl Sulfate Mutational Profiling with Sequencing In Vitro and in Cells
10:34

Probing RNA Structure with Dimethyl Sulfate Mutational Profiling with Sequencing In Vitro and in Cells

Published on: December 9, 2022

5.0K
Practical Aspects of Sample Preparation and Setup of 1H R1ρ Relaxation Dispersion Experiments of RNA
08:17

Practical Aspects of Sample Preparation and Setup of 1H R1ρ Relaxation Dispersion Experiments of RNA

Published on: July 9, 2021

5.1K
RNA Secondary Structure Prediction Using High-throughput SHAPE
13:42

RNA Secondary Structure Prediction Using High-throughput SHAPE

Published on: May 31, 2013

32.1K

Area of Science:

  • Computational Biology
  • Bioinformatics
  • Molecular Biology

Background:

  • RNA folding programs commonly use Zuker's algorithm (O(n^3)) for minimum free energy structure prediction.
  • Recent claims suggested RNA folding could achieve O(n^2) average time complexity via sparsification.
  • This was based on the assumption that RNA folding follows the 'polymer-zeta property'.

Purpose of the Study:

  • To investigate the actual time complexity of sparsified RNA folding algorithms.
  • To develop and analyze a simple, applicable sparsification technique for existing RNA folding programs.
  • To assess the impact of sparsification on both energy minimization and base pairing optimization.

Main Methods:

  • Developed a simple sparsification technique applicable to existing RNA folding programs without new data structures.
  • Implemented the technique in the Vienna RNAfold program, creating sibRNAfold.
  • Conducted extensive runtime analysis using synthetic random sequences for energy minimization and base pairing maximization.

Main Results:

  • Contrary to previous claims, sparsified RNA folding for energy minimization retains an asymptotic time complexity of O(n^3).
  • The 'polymer-zeta property' was not observed in RNA folding, contradicting earlier assumptions.
  • A basic sparsified algorithm achieved a 15- to 50-fold speedup in RNA folding.
  • Sparsification had a variable effect on base pairing optimization, with complexity ranging from O(n^2) to O(n^3) depending on base composition.

Conclusions:

  • The asymptotic time complexity of standard sparsified RNA folding remains O(n^3), not O(n^2).
  • Despite not meeting theoretical O(n^2) claims, sparsification offers practical speed gains for RNA folding.
  • The effectiveness of sparsification varies between energy minimization and base pairing optimization tasks.