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 space-efficient algorithm for the constrained pairwise sequence alignment problem.

Dan He1, Abdullah N Arslan

  • 1Department of Computer Science, University of Vermont, Burlington, 05405, USA. dhe@cs.uvm.edu

Genome Informatics. International Conference on Genome Informatics
|August 12, 2006
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

Circadian gene ARNTL initiates circGUCY1A2 transcription to suppress non-small cell lung cancer progression via miR-200c-3p/PTEN signaling.

Journal of experimental & clinical cancer research : CR·2023
Same author

Src tyrosine kinase promotes cardiac remodeling induced by chronic sympathetic activation.

Bioscience reports·2023
Same author

Identifying prognostic markers in spatially heterogeneous breast cancer microenvironment.

Journal of translational medicine·2023
Same author

Water consumption of electric power system in China: from electricity generation to consumption.

Environmental science and pollution research international·2023
Same author

Neoadjuvant SBRT combined with immunotherapy in NSCLC: from mechanisms to therapy.

Frontiers in immunology·2023
Same author

Single-Cell RNA Sequencing and Transcriptome Analysis Revealed the Immune Microenvironment and Gene Markers of Acute Respiratory Distress Syndrome.

Journal of inflammation research·2023
Same journal

Linear regression models predicting strength of transcriptional activity of promoters.

Genome informatics. International Conference on Genome Informatics·2012
Same journal

Sign: large-scale gene network estimation environment for high performance computing.

Genome informatics. International Conference on Genome Informatics·2012
Same journal

Docking-calculation-based method for predicting protein-RNA interactions.

Genome informatics. International Conference on Genome Informatics·2012
Same journal

Mechanism of cell cycle disruption by multiple p53 pulses.

Genome informatics. International Conference on Genome Informatics·2012
Same journal

Database for crude drugs and Kampo medicine.

Genome informatics. International Conference on Genome Informatics·2012
Same journal

A dynamic programming algorithm to predict synthesis processes of tree-structured compounds with graph grammar.

Genome informatics. International Conference on Genome Informatics·2011
See all related articles

This study introduces a novel algorithm for constrained pairwise sequence alignment (CPSA) that significantly reduces memory usage to O(n) space. This efficient method also improves space requirements for constrained multiple sequence alignment (CMSA) algorithms.

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Genomics

Background:

  • The constrained pairwise sequence alignment (CPSA) problem involves aligning two sequences while respecting a given pattern constraint.
  • Traditional dynamic programming solutions for CPSA require O(rn) space for scoring and O(rnm) space for optimal alignment path reconstruction.
  • Existing divide-and-conquer algorithms reduce memory for optimal alignment to O(rn).

Purpose of the Study:

  • To develop a highly space-efficient algorithm for the constrained pairwise sequence alignment (CPSA) problem that also returns an optimal alignment.
  • To improve the space efficiency of algorithms for the generalized constrained multiple sequence alignment (CMSA) problem.

Main Methods:

  • Development of a novel, space-efficient dynamic programming algorithm for CPSA.

Related Experiment Videos

  • Empirical analysis using real protein sequences to evaluate practical space requirements.
  • Integration of the improved CPSA algorithm into progressive CMSA algorithms.

    • Main Results:

    • The proposed CPSA algorithm achieves an optimal alignment with practical space complexity of O(n).
    • The algorithm demonstrates significant space savings compared to naive and existing divide-and-conquer methods.
    • The improved CPSA algorithm enhances the space efficiency of progressive CMSA methods.

    Conclusions:

    • The presented algorithm offers a substantial advancement in space efficiency for solving the CPSA problem, enabling analysis of larger datasets.
    • This work provides a faster and more memory-conscious approach to sequence alignment with constraints.
    • The findings have implications for improving the scalability and performance of multiple sequence alignment techniques.