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

Local multiple sequence alignment using dead-end elimination.

A V Lukashin1, J J Rosa

  • 1Biogen, Inc., Cambridge, MA 02142, USA.

Bioinformatics (Oxford, England)
|April 1, 2000
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

Analysis of temporal gene expression profiles: clustering by simulated annealing and determining the optimal number of clusters.

Bioinformatics (Oxford, England)·2001
Same author

GeneMark.hmm: new solutions for gene finding.

Nucleic acids research·1998
Same author

Cortical dynamic tuning: the role of intrinsic connections, as revealed by modeling.

Current opinion in neurobiology·1996
Same author

A simulated actuator driven by motor cortical signals.

Neuroreport·1996
Same author

Neural computations underlying the exertion of force: a model.

Biological cybernetics·1996
Same author

Modeling motor cortical operations by an attractor network of stochastic neurons.

Biological cybernetics·1996
Same journal

Cross-Domain Transfer Learning from Peptides to Metabolites Using a Multi-Property Fine-Tuned LLM.

Bioinformatics (Oxford, England)·2026
Same journal

Biomedical Concept Recognition with Error-aware Negative-enhanced Ranking Framework.

Bioinformatics (Oxford, England)·2026
Same journal

TEDLH: Domain HMMs for sensitive detection of remote homologues.

Bioinformatics (Oxford, England)·2026
Same journal

PLNFGL: Joint Estimation of Multi-Condition Gene Networks from Single-cell RNA-seq Data.

Bioinformatics (Oxford, England)·2026
Same journal

MCFST: Spatial domain identification method based on multi-view graph convolutional network and graph fusion network.

Bioinformatics (Oxford, England)·2026
Same journal

SpaBiT: Enhancing Spatial Transcriptomics Resolution via Bidirectional Attention Transformers.

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

This study introduces a novel algorithm for local multiple sequence alignment, significantly improving efficiency. The method rapidly identifies optimal alignments for protein families, avoiding exhaustive searches.

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Genomics

Background:

  • Local multiple sequence alignment is crucial for identifying conserved functional regions in protein families.
  • Existing methods for rigorous local multiple alignment can be computationally intensive, limiting their application.

Purpose of the Study:

  • To develop an efficient, polynomial-time algorithm for solving the local multiple alignment problem.
  • To provide a computationally feasible method for finding globally optimal local alignments of protein sequences.

Main Methods:

  • The algorithm employs a dead-end elimination procedure to avoid exhaustive search.
  • Rejection criteria are derived within the sum-of-pairs scoring system to eliminate inconsistent segments.
  • Iterative application of criteria reduces combinatorial possibilities, leading to convergence.

Related Experiment Videos

Main Results:

  • The algorithm achieves computational feasibility, with complexity growing polynomially (quadratically and cubically) with sequence length.
  • It rapidly reduces search space by eliminating segments provably inconsistent with the optimal alignment.
  • The method converges to a unique globally optimal solution in most cases, validated on known protein families.

Conclusions:

  • The presented algorithm offers a computationally efficient and rigorous solution for local multiple sequence alignment.
  • This advancement facilitates the analysis of protein families and the identification of functionally important regions.