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

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

RNA Structure

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

RNA Structure

29.7K
29.7K
RNA Structure01:19

RNA Structure

8.1K
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...
8.1K
Protein Folding01:25

Protein Folding

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

Protein Folding

129.8K
Overview
129.8K

You might also read

Related Articles

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

Sort by
Same author

A Resolution of the Static Formulation Question for the Problem of Computing the History Bound.

IEEE/ACM transactions on computational biology and bioinformatics·2016
Same author

Faster algorithms for RNA-folding using the Four-Russians method.

Algorithms for molecular biology : AMB·2014
Same author

Constructing perfect phylogenies and proper triangulations for three-state characters.

Algorithms for molecular biology : AMB·2012
Same author

Extensions and improvements to the chordal graph approach to the multistate perfect phylogeny problem.

IEEE/ACM transactions on computational biology and bioinformatics·2011
Same author

Untangling tanglegrams: comparing trees by their drawings.

IEEE/ACM transactions on computational biology and bioinformatics·2010
Same author

The Multi-State Perfect Phylogeny Problem with missing and removable data: solutions via integer-programming and chordal graph theory.

Journal of computational biology : a journal of computational molecular cell biology·2010
Same journal

Haplotype-aware long-read error correction.

Algorithms for molecular biology : AMB·2026
Same journal

Extension of partial atom-to-atom maps: uniqueness and algorithms.

Algorithms for molecular biology : AMB·2026
Same journal

Lossless pangenome indexing using tag arrays.

Algorithms for molecular biology : AMB·2026
Same journal

Dolphyin: a combinatorial algorithm for identifying 1-Dollo phylogenies in cancer.

Algorithms for molecular biology : AMB·2026
Same journal

Probing transcription factor subsets in gene regulatory networks.

Algorithms for molecular biology : AMB·2026
Same journal

Comparing the ability of embedding methods on metabolic hypergraphs for capturing taxonomy-based features.

Algorithms for molecular biology : AMB·2026
See all related articles

Related Experiment Video

Updated: Mar 16, 2026

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.4K

An improved Four-Russians method and sparsified Four-Russians algorithm for RNA folding.

Yelena Frid1, Dan Gusfield1

  • 1Department of Computer Science, UC Davis, One Shields Avenue, Davis, CA USA.

Algorithms for Molecular Biology : AMB
|August 9, 2016
PubMed
Summary
This summary is machine-generated.

This study introduces a Sparse Four-Russians framework to accelerate RNA secondary structure prediction. The new method offers significant speedups, outperforming existing approaches for RNA folding problems.

Keywords:
Four-RussiansRNA foldingRNA secondary structureSecondary structure predictionSingle sequence foldingSparsification

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.3K
Optical Tweezers to Study RNA-Protein Interactions in Translation Regulation
12:26

Optical Tweezers to Study RNA-Protein Interactions in Translation Regulation

Published on: February 12, 2022

6.0K

Related Experiment Videos

Last Updated: Mar 16, 2026

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.4K
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.3K
Optical Tweezers to Study RNA-Protein Interactions in Translation Regulation
12:26

Optical Tweezers to Study RNA-Protein Interactions in Translation Regulation

Published on: February 12, 2022

6.0K

Area of Science:

  • Computational Biology
  • Bioinformatics
  • Algorithm Analysis

Background:

  • The RNA secondary structure prediction problem, also known as single sequence folding (SSF), was initially solved using a dynamic programming method.
  • Recent advancements have focused on speeding up SSF prediction through methodologies like Valiant, Four-Russians, and Sparsification.
  • Sparsification leverages input properties such as the number of subsequences (Z) and base-pairs (L) to achieve O(LZ) running time.

Purpose of the Study:

  • To explore and develop algorithmic speedups for RNA secondary structure prediction.
  • To enhance the Four-Russians algorithm for faster computation.
  • To combine Sparsification and Four-Russians methods for improved performance.

Main Methods:

  • Reformulated the Four-Russians algorithm with an on-demand lookup table for SSF.
  • Developed a framework integrating Sparsification with the on-demand Four-Russians method.
  • Created an on-demand parallel algorithm for Four-Russians, achieving O(n^2) time complexity.

Main Results:

  • The combined Sparse Four-Russians framework achieves a worst-case running time of O(n^2).
  • An on-demand parallel algorithm yields an asymptotic speedup of O(n^2/log n).
  • Empirical testing demonstrated speedups on base-pair maximization and biologically informative scoring schemes.

Conclusions:

  • The on-demand formulation enhances efficiency by reducing extraneous computation.
  • This approach effectively utilizes sparsity properties for faster RNA folding predictions.
  • The Sparse Four-Russians framework consistently provides speedups, outperforming individual methods in empirical tests.