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

Fast pairwise structural RNA alignments by pruning of the dynamical programming matrix.

Jakob H Havgaard1, Elfar Torarinsson, Jan Gorodkin

  • 1Division of Genetics and Bioinformatics, University of Copenhagen, Frederiksberg, Denmark.

Plos Computational Biology
|October 17, 2007
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

Riboswitch-targeted improvement of lysine production in Bacillus and Priestia species.

NPJ science of food·2026
Same author

Characterization of the virus-host RNA-RNA interactome across important human pathogenic RNA viruses.

PLoS pathogens·2026
Same author

Exploring the regulatory potential of RNA structures in 202 cyanobacterial genomes.

Nucleic acids research·2026
Same author

Very high CO<sub>2</sub> concentrations inhibit photosynthesis and trigger transcriptomic stress responses in cyanobacteria.

NAR genomics and bioinformatics·2026
Same author

Associating cancer-related RNA structure disrupting SNPs in LincRNAs to function.

BMC genomics·2025
Same author

Extrachromosomal circular miRNA-gene amplifications contribute to the renal cancer phenotype.

Cell reports·2025
Same journal

Development of whole-limb skeletal patterning through the coordination of growth and self-organization models.

PLoS computational biology·2026
Same journal

The energetic cost of human standing balance and gait initiation over a range of natural postures.

PLoS computational biology·2026
Same journal

Combinatorial multiomic analysis from a pedigree of Sox10Dom Hirschsprung mice identifies multiple high confidence candidate modifiers of Enteric Nervous System development.

PLoS computational biology·2026
Same journal

Extracting host-specific developmental signatures from longitudinal microbiome data.

PLoS computational biology·2026
Same journal

Population sparseness determines strength of Hebbian plasticity for maximal memory lifetime in associative networks.

PLoS computational biology·2026
Same journal

Predictive coding explains asymmetric connectivity in the brain: A neural network study.

PLoS computational biology·2026
See all related articles

This study introduces a novel heuristic for identifying noncoding RNAs (ncRNAs) by pruning dynamic programming matrices, improving computational efficiency. The enhanced FOLDALIGN software offers a user-friendly tool for discovering new ncRNAs in mammalian genomes.

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Genomics

Background:

  • Noncoding RNAs (ncRNAs) are crucial in cellular functions, with many unknown ncRNAs potentially existing in mammalian genomes.
  • Current computational methods for ncRNA discovery rely on sequence comparison but suffer from high computational complexity.
  • Existing heuristics like pre-folding and pre-aligning have limitations, neglecting comparative information or relying on sequence similarity.

Purpose of the Study:

  • To present a novel heuristic, dynamic programming matrix pruning, for efficient ncRNA identification.
  • To introduce an improved FOLDALIGN algorithm implementation for pairwise RNA sequence alignment.
  • To enhance the computational efficiency and memory management of ncRNA searching tools.

Main Methods:

Related Experiment Videos

  • Implemented pruning of the dynamic programming matrix to dynamically constrain alignments based on scores.
  • Developed a new divide and conquer method to reduce memory usage during global alignment and local alignment backtracking.
  • Updated the FOLDALIGN algorithm with improved memory handling and an enhanced energy model.

    • Main Results:

    • The novel pruning heuristic significantly reduces time and memory requirements for RNA sequence alignment.
    • The divide and conquer method effectively limits memory consumption in alignment processes.
    • The enhanced FOLDALIGN software maintains high performance while offering dramatic improvements in computational efficiency.

    Conclusions:

    • The improved FOLDALIGN algorithm provides an efficient and user-friendly tool for molecular biologists to discover novel ncRNAs.
    • Dynamic programming matrix pruning offers a viable alternative heuristic for computational ncRNA identification.
    • The software package is available for download, facilitating further research in ncRNA discovery.