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

Optimizing reduced-space sequence analysis.

R Wheeler1, R Hughey

  • 1Department of Computer Engineering, Jack Baskin School of Engineering, University of California, Santa Cruz, CA 95064, USA.

Bioinformatics (Oxford, England)
|February 13, 2001
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

The evolution of informed consent.

The British journal of surgery·2017
Same author

Testicular atrophy following paediatric primary orchidopexy: A prospective study.

Journal of pediatric urology·2016
Same author

When might an operative complication be regarded as acceptable? Part 2: Judicial factors that influence the finding of fault during surgical litigation.

Annals of the Royal College of Surgeons of England·2015
Same author

When might an operative complication be regarded as acceptable? Part 1: Surgical factors that influence courts when finding fault during litigation.

Annals of the Royal College of Surgeons of England·2015
Same author

Adults who refuse blood transfusion in emergency, urgent and elective circumstances.

Annals of the Royal College of Surgeons of England·2014
Same author

Candour for surgeons: the absence of spin.

Annals of the Royal College of Surgeons of England·2014
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
Same journal

CSCN: Inference of Cell-Specific Causal Networks Using Single-Cell RNA-Seq Data.

Bioinformatics (Oxford, England)·2026
Same journal

Sparse CCA-Based Mediation Analysis with High-Dimensional Exposures and Mediators.

Bioinformatics (Oxford, England)·2026
Same journal

Enhancing Cross-Context Generalization in Drug Perturbation Prediction with a Multimodal Conditional Diffusion Framework.

Bioinformatics (Oxford, England)·2026
Same journal

Primer Design through Submodular Function Estimation.

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

This study optimizes the checkpoint algorithm for sequence alignment and hidden Markov model (HMM) training. Improved algorithms offer significant computational speedups, enhancing HMM training efficiency.

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Algorithm Optimization

Background:

  • Dynamic programming is fundamental for sequence comparison, alignment, and hidden Markov model (HMM) training, typically requiring O(mn) time and space.
  • The checkpoint algorithm offers a space-efficient alternative for sequence comparison and HMM training, with a diagonal version achieving O(m+n) space for single-best-path alignment.

Purpose of the Study:

  • To enhance the performance of the checkpoint algorithm for sequence comparison and HMM training.
  • To analyze optimal checkpoint placement for improved computational efficiency.

Main Methods:

  • Analysis of optimal checkpoint placement within the checkpoint algorithm.
  • Modification of the SAM hidden Markov modeling package to incorporate the improved row checkpoint algorithm.

Related Experiment Videos

Main Results:

  • The improved row checkpoint algorithm reduces computation by up to 50%.
  • The improved diagonal checkpoint algorithm reduces computational steps by up to 35%.
  • The modified SAM package shows up to 33% faster all-paths and 56% faster single-best-path HMM training.

Conclusions:

  • Optimized checkpoint placement significantly improves the efficiency of sequence alignment and HMM training algorithms.
  • The enhanced checkpoint algorithm provides substantial speedups, particularly beneficial for large-scale biological sequence analysis.