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

Recent developments in linear-space alignment methods: a survey

K M Chao1, R C Hardison, W Miller

  • 1Department of Computer Science and Engineering, Pennsylvania State University, University Park 16802, USA.

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|January 1, 1994
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

Achievement of Target Gain Larger than Unity in an Inertial Fusion Experiment.

Physical review letters·2024
Same author

Lawson Criterion for Ignition Exceeded in an Inertial Fusion Experiment.

Physical review letters·2022
Same author

Letter from New York-Yellow Fever Prevented by Innoculation.

The Southern medical record·2022
Same author

Scintillation light detection in the 6-m drift-length ProtoDUNE Dual Phase liquid argon TPC.

The European physical journal. C, Particles and fields·2022
Same author

Prospects for beyond the Standard Model physics searches at the Deep Underground Neutrino Experiment: DUNE Collaboration.

The European physical journal. C, Particles and fields·2021
Same author

STAGdb: a 30K SNP genotyping array and Science Gateway for Acropora corals and their dinoflagellate symbionts.

Scientific reports·2020
Same journal

GMSA: A Graph Matching and Point Cloud Registration-Based Method for Spatial Transcriptomics Data Alignment.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Investigations on Multiple Protein Scaffold Filling.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Cell Type Prediction for Single-Cell RNA Sequencing Utilizing Unsupervised Domain Adaptation and Semi-Supervised Learning.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

PPIGAN: Prediction of Protein-Protein Interactions Using Generative Adversarial Networks.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Deep Structure-Enhanced Cell Clustering Model for Single-Cell RNA Sequencing Data.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Asymmetric Drug-Drug Interaction Prediction Based on Generative Adversarial Networks and Knowledge Graph.

Journal of computational biology : a journal of computational molecular cell biology·2026
See all related articles

Hirschberg's dynamic programming strategy enables linear space sequence alignment for DNA and proteins. This research extends the method for constrained, high-scoring, and multiple sequence alignments, proving useful for long gene sequences.

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Genomics

Background:

  • Sequence alignment is crucial for understanding biological relationships.
  • Traditional methods can be memory-intensive, especially for long sequences.
  • Dan Hirschberg's 1975 dynamic programming strategy offers a space-efficient alternative.

Purpose of the Study:

  • To review and extend Hirschberg's linear space sequence alignment algorithms.
  • To develop novel methods for constrained, threshold-based, and multiple sequence alignments.
  • To demonstrate the utility of these algorithms for analyzing large biological datasets.

Main Methods:

  • Adaptation of Hirschberg's dynamic programming strategy for linear space complexity.
  • Development of algorithms for constrained global alignment (L[i] to U[i]).

Related Experiment Videos

  • Methods for identifying high-scoring local alignments and k-best local alignments.
  • Implementation of a multisequence alignment tool for very long sequences.

    • Main Results:

    • Demonstrated linear space algorithms for global and local sequence alignment.
    • Introduced novel extensions for constrained and threshold-based alignments.
    • Presented two linear-space algorithms for computing k-best local alignments.
    • Developed and applied a multisequence alignment program to mammalian globin gene clusters.

    Conclusions:

    • Hirschberg's strategy provides highly space-efficient sequence alignment solutions.
    • The extended algorithms offer powerful new tools for bioinformatics research.
    • These methods are particularly effective for analyzing large-scale genomic data, such as long gene sequences.