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 Experiment Videos

LinearFold: linear-time approximate RNA folding by 5'-to-3' dynamic programming and beam search.

Liang Huang1,2, He Zhang2, Dezhong Deng1

  • 1School of Electrical Engineering and Computer Science, Oregon State University, Corvallis, OR, USA.

Bioinformatics (Oxford, England)
|September 13, 2019
PubMed
Summary

Related Concept Videos

You might also read

Related Articles

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

Sort by
Same author

Activation of the Aryl Hydrocarbon Receptor-Cytochrome P450 1A1 Axis Mediates the Selective Cytotoxicity of 2‑Phenyl-Imidazo[1,2‑<i>a</i>]Pyridine Derivatives in Triple-Negative Breast Cancer Cells.

ACS pharmacology & translational science·2026
Same author

Probabilistic RNA designability via interpretable ensemble approximation and dynamic decomposition.

Bioinformatics (Oxford, England)·2026
Same author

Computational Resources for Molecular Biology 2026.

Journal of molecular biology·2026
Same author

Reparameterization of the Amber RNA Force Field Non-Bonded Terms.

bioRxiv : the preprint server for biology·2026
Same author

Nearest Neighbor Parameters for Estimating the Folding Stability of RNA Including Pseudouridine.

bioRxiv : the preprint server for biology·2026
Same author

RNA Folding Nearest Neighbor Parameters Including the Modification 1-Methyl-Pseudouridine.

bioRxiv : the preprint server for biology·2026

We developed a new RNA folding algorithm that runs in linear time and space, significantly improving speed and accuracy for genome-wide applications. This novel approach enhances predictions for long RNA sequences and distant base pairs.

Area of Science:

  • Computational biology
  • Bioinformatics
  • Genomics

Background:

  • Predicting ribonucleic acid (RNA) secondary structure is crucial for various biological applications.
  • Current dynamic programming algorithms for RNA folding have cubic time complexity, limiting their scalability for genome-wide analyses.

Purpose of the Study:

  • To develop a novel, efficient algorithm for RNA secondary structure prediction.
  • To achieve linear time and space complexity for RNA folding while maintaining high accuracy.

Main Methods:

  • Introduced an alternative dynamic programming algorithm for RNA folding.
  • Adapted techniques from incremental parsing for context-free grammars.
  • Implemented a beam pruning heuristic for linear time and space efficiency.

Related Experiment Videos

Main Results:

  • Achieved O(n) time and O(n) space complexity for RNA folding, a significant improvement over existing O(n^3) methods.
  • The algorithm produces high-quality approximations of optimal RNA structures without imposing output constraints.
  • Demonstrated superior accuracy compared to existing models, particularly for long RNA sequences (e.g., 16S and 23S Ribosomal RNAs) and long-range base pairs.

Conclusions:

  • The novel linear-time RNA folding algorithm offers a scalable and accurate solution for large-scale genomic applications.
  • This approach overcomes the limitations of traditional dynamic programming methods, enabling more comprehensive RNA structure analysis.
  • The developed algorithm and its implementation (LinearFold) are publicly available for research use.