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

A memory-efficient dynamic programming algorithm for optimal alignment of a sequence to an RNA secondary structure.

Sean R Eddy1

  • 1Howard Hughes Medical Institute & Department of Genetics, Washington University School of Medicine, Saint Louis, Missouri 63110 USA. eddy@genetics.wustl.edu

BMC Bioinformatics
|July 4, 2002
PubMed
Summary
This summary is machine-generated.

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

HMMER web server: 2026 update.

Nucleic acids research·2026
Same author

Induction of menstruation in mice reveals the regulation of menstrual shedding.

bioRxiv : the preprint server for biology·2025
Same author

Presence of group II introns in phage genomes.

Nucleic acids research·2025
Same author

Prevalence of Group II Introns in Phage Genomes.

bioRxiv : the preprint server for biology·2025
Same author

Cellular evolution of the hypothalamic preoptic area of behaviorally divergent deer mice.

eLife·2025
Same author

Cellular evolution of the hypothalamic preoptic area of behaviorally divergent deer mice.

bioRxiv : the preprint server for biology·2024
Same journal

OpenIMC: an open-source platform for analyzing single-cell and spatial proteomics by imaging mass cytometry.

BMC bioinformatics·2026
Same journal

NAP: an open source pipeline for cross-domain microbiome profiling using Nanopore sequencing-derived amplicon data.

BMC bioinformatics·2026
Same journal

SurvGME: an R package for survival analysis with graphical and measurement error models.

BMC bioinformatics·2026
Same journal

SimMapNet: a Bayesian framework for gene regulatory network inference using gene ontology similarities as external hint.

BMC bioinformatics·2026
Same journal

Dual channel drug-drug interactions extraction based on cross attention.

BMC bioinformatics·2026
Same journal

FeSseqdb: a curated sequence-level database and interpretable machine learning framework for identifying iron-sulfur proteins.

BMC bioinformatics·2026
See all related articles

A new algorithm significantly reduces memory for RNA sequence alignment using covariance models (CMs). This advance enables large-scale structural alignment of RNAs, previously limited by high memory demands.

Area of Science:

  • Computational Biology
  • Bioinformatics
  • Molecular Biology

Background:

  • Covariance models (CMs) are probabilistic models for RNA secondary structure.
  • Standard alignment algorithms for CMs require O(N3) memory, limiting their use to small RNAs.
  • This memory constraint hinders large-scale RNA structural analysis.

Purpose of the Study:

  • To develop a memory-efficient algorithm for aligning RNA sequences with covariance models.
  • To overcome the memory limitations of existing dynamic programming approaches.
  • To enable the structural alignment of larger RNA molecules.

Main Methods:

  • A divide and conquer strategy was employed, inspired by memory-efficient algorithms for linear sequence alignment.
  • The approach adapts dynamic programming techniques for improved memory complexity.

Related Experiment Videos

  • The modified algorithm achieves a memory complexity of O(N2 log N).

    • Main Results:

    • The novel alignment algorithm reduces memory requirements from O(N3) to O(N2 log N).
    • This memory efficiency allows for the alignment of large RNA sequences.
    • A significant reduction in memory usage was demonstrated for ribosomal RNA structural alignments.

    Conclusions:

    • The developed algorithm drastically reduces memory needs for RNA structural alignment.
    • Optimal ribosomal RNA alignments that previously required 150 GB now need under 270 MB.
    • This advancement makes large-scale RNA structural analysis more computationally feasible.