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

The Treeterbi and Parallel Treeterbi algorithms: efficient, optimal decoding for ordinary, generalized and pair HMMs.

Evan Keibler1, Manimozhiyan Arumugam, Michael R Brent

  • 1Laboratory for Computational Genomics, Campus Box 1045, Washington University, St. Louis, MO 63130, USA.

Bioinformatics (Oxford, England)
|January 24, 2007
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

Finding Significant Hits in Networks: a network-based tool for analyzing gene-level P-values to identify significant genes missed by standard methods.

Briefings in bioinformatics·2026
Same author

UBIQUITOUS FUNCTIONAL SYNERGY PARTIALLY EXPLAINS WHY MOST TRANSCRIPTION FACTOR BINDING IS NON-FUNCTIONAL.

bioRxiv : the preprint server for biology·2026
Same author

Mapping the transcriptional regulatory network of a fungal pathogen by exploiting transcription factor perturbation.

mBio·2025
Same author

Combining Motifs, CRE Activity, And Gene Expression Data Using ML Greatly Improves the Accuracy of Tissue-Specific TF Network Maps.

bioRxiv : the preprint server for biology·2025
Same author

The postbiotic ReFerm® versus standard nutritional support in advanced alcohol-related liver disease (GALA-POSTBIO): a randomized controlled phase 2 trial.

Nature communications·2025
Same author

Microbial signatures in oral sites of patients with primary Sjögren's syndrome: Association with salivary gland hypofunction.

Journal of microbiology (Seoul, Korea)·2025

New Treeterbi algorithms offer optimal decoding for long sequences using hidden Markov models (HMMs) with bounded memory. This advance improves gene prediction accuracy and efficiency in bioinformatics.

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Genomics

Background:

  • Hidden Markov models (HMMs) are widely used but standard Viterbi decoding requires excessive memory for long sequences.
  • Existing memory-saving methods compromise optimality or increase computation time.
  • Efficient decoding is crucial for large-scale genomic analysis.

Purpose of the Study:

  • To develop novel, memory-efficient algorithms for optimal decoding with generalized HMMs.
  • To implement and evaluate these algorithms in gene prediction and sequence alignment systems.
  • To address the memory limitations of standard Viterbi decoding.

Main Methods:

  • Developed two novel decoding algorithms: Treeterbi and Parallel Treeterbi.
  • Implemented Treeterbi within the TWINSCAN/N-SCAN gene-prediction system and Pairagon aligner.

Related Experiment Videos

  • Parallel Treeterbi utilizes multiple processors for distributed optimal decoding.

    • Main Results:

    • Treeterbi achieves optimal decoding of arbitrarily long sequences in bounded memory without increased running time.
    • Parallel Treeterbi significantly reduces decoding latency across multiple processors.
    • N-SCAN with Treeterbi improved accuracy in decoding human chromosomes compared to heuristic methods.

    Conclusions:

    • Treeterbi and Parallel Treeterbi provide efficient and optimal solutions for HMM decoding.
    • These algorithms enhance the performance and accuracy of gene prediction and sequence alignment tools.
    • The TWINSCAN/N-SCAN/PAIRAGON software package is publicly available for research.