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

Reduced space sequence alignment

J A Grice1, R Hughey, D Speck

  • 1University of California, Santa Cruz 95064, USA.

Computer Applications in the Biosciences : CABIOS
|February 1, 1997
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

Methods of analysis for 2-dodecylcyclobutanone and studies to support its role as a unique marker of food irradiation.

Food chemistry·2013
Same author

[Specific aspects of vaccine manufacturing].

Annales pharmaceutiques francaises·2009
Same author

Energy function-based approaches to graph coloring.

IEEE transactions on neural networks·2008
Same author

Plasma fibronectin levels and coronary artery disease.

Journal of thrombosis and haemostasis : JTH·2007
Same journal

DCA: an efficient implementation of the divide-and-conquer approach to simultaneous multiple sequence alignment.

Computer applications in the biosciences : CABIOS·1998
Same journal

Two applications to facilitate the viewing of database search result files on the Macintosh.

Computer applications in the biosciences : CABIOS·1998
Same journal

BioWish: a molecular biology command extension to Tcl/Tk.

Computer applications in the biosciences : CABIOS·1998
Same journal

The Sequence Alerting Server--a new WEB server.

Computer applications in the biosciences : CABIOS·1998
Same journal

A software tool for the analysis of mass spectrometric disulfide mapping experiments.

Computer applications in the biosciences : CABIOS·1998
Same journal

SAMBA: hardware accelerator for biological sequence comparison.

Computer applications in the biosciences : CABIOS·1998
See all related articles

New sequence alignment algorithms reduce memory usage significantly. These methods offer a practical alternative to existing approaches, improving efficiency for complex biological sequence analysis.

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Algorithm Design

Background:

  • Sequence alignment is fundamental in bioinformatics for comparing biological sequences.
  • Standard algorithms require substantial memory (O(n^2)) or are limited in parallelization.
  • Hirschberg's algorithm reduces space but can be slow.

Purpose of the Study:

  • To develop novel sequence alignment methods with reduced memory footprints.
  • To create algorithms suitable for both serial and parallel computing environments.
  • To enable efficient training of linear hidden Markov models.

Main Methods:

  • A family of algorithms is presented for sequence alignment with reduced memory.
  • These methods achieve space complexity of O(n^1.5) with a tunable slowdown factor (L).

Related Experiment Videos

  • A specific algorithm matches Hirschberg's space-time complexity but offers practical speedups.

    • Main Results:

    • The proposed algorithms reduce memory requirements from O(n^2) to O(n^1.5).
    • They are well-suited for parallel implementation and avoid data-dependent repartitioning.
    • The O(n^1.5)-space algorithm demonstrates a 15-40% speed improvement over Hirschberg's method.

    Conclusions:

    • This work introduces memory-efficient sequence alignment algorithms.
    • The new methods provide a trade-off between space reduction and computational time.
    • These algorithms enhance the feasibility of large-scale sequence analysis and model training.