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

Picking alignments from (Steiner) trees.

Fumei Lam1, Marina Alexandersson, Lior Pachter

  • 1Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA.

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|August 26, 2003
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

TCIA Radiology Image Processing for AI and Radiomics.

medRxiv : the preprint server for health sciences·2026
Same author

Transcriptomic responses to endurance exercise training in rats.

BMC genomic data·2026
Same author

Systems genetics reveals ITIH5 as a key mediator of adipocyte-Endothelial crosstalk.

Molecular metabolism·2026
Same author

The Rayleigh Quotient and Contrastive Principal Component Analysis II.

bioRxiv : the preprint server for biology·2026
Same author

Hybrid crosses reveal a cell-type-specific landscape of mouse regulatory variation.

bioRxiv : the preprint server for biology·2026
Same author

The impact of package selection and versioning on single-cell RNA-seq analysis.

Cell systems·2026
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

This study introduces a novel method for aligning long biological sequences, addressing computational time and parameter challenges. The approach efficiently reduces search spaces for probabilistic models, improving DNA sequence alignment accuracy.

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Genomics

Background:

  • Needleman-Wunsch alignment faces challenges with long biological sequences, including computational complexity and parameter selection.
  • Existing methods like banding and chaining reduce running time but don't fully address parameter issues.
  • Probabilistic models, including those used in Needleman-Wunsch, struggle to capture the block-like structure of conserved and nonconserved regions in biological sequences.

Purpose of the Study:

  • To develop an efficient method for designing search spaces in pair hidden Markov models (PHMMs) for biological sequence alignment.
  • To address the limitations of existing alignment techniques in handling the complexities of biological sequence data.
  • To improve the accuracy and efficiency of DNA sequence alignment.

Main Methods:

Related Experiment Videos

  • Developed a novel approach leveraging sequence features to optimize search spaces for PHMMs.
  • Formulated an optimization problem solved using a 2-approximation algorithm.
  • Utilized Manhattan networks, related to Steiner trees, as a theoretical basis for the algorithm.
  • Applied the method to DNA sequence alignment.

Main Results:

  • Successfully reduced the Viterbi algorithm search space for PHMM alignment by three orders of magnitude.
  • Demonstrated practical application in DNA sequence alignment.
  • Provided a theoretical framework based on Manhattan networks and approximation algorithms.

Conclusions:

  • The proposed method offers an efficient solution for designing search spaces in PHMM-based sequence alignment.
  • This approach effectively addresses key challenges in aligning long biological sequences, particularly DNA.
  • The technique significantly enhances the computational efficiency of alignment algorithms.