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 hidden Markov model training

C Tarnas1, R Hughey

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

Bioinformatics (Oxford, England)
|July 31, 1998
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

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 author

What is the value added by human intervention in protein structure prediction?

Proteins·2002
Same author

Assignment of homology to genome sequences using a library of hidden Markov models that represent all proteins of known structure.

Journal of molecular biology·2001
Same author

Sequence analysis with the Kestrel SIMD parallel processor.

Pacific Symposium on Biocomputing. Pacific Symposium on Biocomputing·2001
Same author

Molecular fingerprinting on the SIMD parallel processor Kestrel.

Pacific Symposium on Biocomputing. Pacific Symposium on Biocomputing·2001
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

Checkpoint-based reduced space sequence alignment significantly improves memory efficiency for hidden Markov model training. This method enhances performance for large datasets in bioinformatics, applicable to dynamic programming tasks.

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Algorithm Development

Background:

  • Standard hidden Markov model (HMM) training, like Baum-Welch, is memory-intensive due to examining all paths.
  • This limitation prevents leveraging efficient linear-space sequence alignment algorithms.

Purpose of the Study:

  • To implement and evaluate checkpoint-based reduced space sequence alignment within the Sequence Alignment and Modeling (SAM) HMM package.
  • To address the memory and computational challenges of HMM training for large biological sequences.

Main Methods:

  • Implementation of a checkpoint algorithm for reduced space sequence alignment.
  • Performance evaluation focusing on memory usage and computational speed.

Main Results:

Related Experiment Videos

  • Memory usage reduced from O(mn) to O(m*sqrt(n)).
  • A minor slowdown of 10% for small datasets, but significant speed-ups for large datasets (e.g., m=n=2000).
  • Demonstrated effectiveness in preventing excessive paging on limited memory workstations.

Conclusions:

  • Checkpoint-based reduced space alignment is an effective strategy for memory-efficient HMM training.
  • The approach offers substantial performance gains for large-scale sequence alignment tasks.
  • Applicable to various dynamic programming algorithms beyond HMMs.