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 practical use of the A* algorithm for exact multiple sequence alignment.

M Lermen1, K Reinert

  • 1Max Planck Institut für Informatik, Im Stadtwald, D-66123 Saarbrücken, Germany.

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|January 12, 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

Design of a compartmentalized shotgun assembler for the human genome.

Bioinformatics (Oxford, England)·2001
Same author

The sequence of the human genome.

Science (New York, N.Y.)·2001
Same author

An iterative method for faster sum-of-pairs multiple sequence alignment.

Bioinformatics (Oxford, England)·2000
Same author

The genome sequence of Drosophila melanogaster.

Science (New York, N.Y.)·2000
Same author

An exact solution for the segment-to-segment multiple sequence alignment problem.

Bioinformatics (Oxford, England)·1999
Same author

A polyhedral approach to RNA sequence structure alignment.

Journal of computational biology : a journal of computational molecular cell biology·1998
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 enhances multiple sequence alignment (MSA) computation using the A* algorithm. New bounding strategies significantly speed up calculations and outperform existing methods by excluding more nodes.

Area of Science:

  • Computational Biology
  • Bioinformatics
  • Algorithm Optimization

Background:

  • Multiple sequence alignment (MSA) is a fundamental problem in computational biology.
  • Exact solutions for MSA are often achieved via dynamic programming, interpretable as shortest path computations on directed acyclic graphs.

Purpose of the Study:

  • To accelerate the computation of multiple sequence alignment using the A* algorithm.
  • To introduce novel bounding strategies for enhancing A* algorithm performance in MSA.

Main Methods:

  • Implementation of the A* algorithm (goal-directed unidirectional search) for MSA.
  • Development and integration of new lower and upper bounding strategies.
  • Comparison with existing methods like Carrillo-Lipman bounding.

Related Experiment Videos

Main Results:

  • The A* algorithm with new bounding strategies significantly speeds up MSA computations.
  • The proposed A* approach demonstrates superiority over the Carrillo-Lipman bounding method.
  • The enhanced A* algorithm effectively excludes more nodes from consideration during computation.

Conclusions:

  • The A* algorithm, enhanced with novel bounding strategies, offers a considerable speedup for multiple sequence alignment.
  • This optimized A* approach provides a more efficient alternative to existing bounding techniques in MSA.
  • The findings contribute to faster and more effective computational biology analyses.