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 algorithm for multiple sequence alignment with constraints.

Chin Lung Lu1, Yen Pin Huang

  • 1Department of Biological Science and Technology, National Chiao Tung University Hsinchu 300, Taiwan, Republic of China. cllu@mail.nctu.edu.tw

Bioinformatics (Oxford, England)
|September 18, 2004
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

LinearCDSfold: a tool for co-optimizing secondary structure stability and codon usage in coding sequence design.

Bioinformatics advances·2026
Same author

A More Efficient Dynamic Programming Algorithm for Designing a Coding Sequence by Jointly Optimizing Its Structural Stability and Codon Usage.

IEEE transactions on computational biology and bioinformatics·2025
Same author

An Integer Linear Programming Approach for Scaffolding Based on Exemplar Breakpoint Distance.

Journal of computational biology : a journal of computational molecular cell biology·2022
Same author

Multi-CSAR: a web server for scaffolding contigs using multiple reference genomes.

Nucleic acids research·2022
Same author

Clover: a clustering-oriented de novo assembler for Illumina sequences.

BMC bioinformatics·2020
Same author

Multi-CSAR: a multiple reference-based contig scaffolder using algebraic rearrangements.

BMC systems biology·2019
Same journal

KASSPer: Kinase Active Site Structure Prediction using Protein and Ligand Language Models and Its Application to Virtual Screening.

Bioinformatics (Oxford, England)·2026
Same journal

IDR searcher: a search engine solution for public image resources.

Bioinformatics (Oxford, England)·2026
Same journal

KCFtools: Rapid alignment-free method for introgression screening and GWAS using k-mer profiles.

Bioinformatics (Oxford, England)·2026
Same journal

Meta2DB: Curated shotgun metagenomic feature sets and metadata for health state prediction.

Bioinformatics (Oxford, England)·2026
Same journal

conMItion: an R package adjusting confounding factors for associations in multi-omics.

Bioinformatics (Oxford, England)·2026
Same journal

SpaMFG: a Spatial Multi-omics Integration Method based on Feature Grouping.

Bioinformatics (Oxford, England)·2026
See all related articles

A new memory-efficient algorithm for constrained sequence alignment reduces memory usage from O(gamma*n^2) to O(alpha*n), enabling the alignment of longer biological sequences. This advance facilitates more comprehensive analysis in bioinformatics.

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Genomics

Background:

  • Constrained sequence alignment incorporates biological knowledge into sequence alignment.
  • Current progressive alignment methods require significant memory (O(gamma*n^2)), limiting analysis to short sequences.
  • Existing dynamic programming algorithms for optimal constrained alignment are memory-intensive.

Purpose of the Study:

  • To develop a memory-efficient algorithm for computing optimal constrained sequence alignments.
  • To overcome the memory limitations of existing dynamic programming approaches.
  • To create a practical tool for memory-efficient multiple sequence alignment with constraints.

Main Methods:

  • Implemented a divide-and-conquer approach to design a novel algorithm for constrained sequence alignment.

Related Experiment Videos

  • Reduced memory complexity from quadratic to linearithmic with respect to sequence length.
  • Developed a new tool based on the memory-efficient algorithm for multiple sequence alignment.

    • Main Results:

    • The new algorithm achieves O(alpha*n) space complexity, significantly reducing memory requirements.
    • Memory efficiency is achieved at the cost of a minor increase in CPU time.
    • A memory-efficient tool for multiple sequence alignment with constraints has been developed.

    Conclusions:

    • The divide-and-conquer approach offers a memory-efficient solution for constrained sequence alignment.
    • This method enables the alignment of longer sequences, expanding the scope of bioinformatics analyses.
    • The developed tool provides a practical solution for memory-constrained multiple sequence alignment tasks.