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

Faster algorithms for optimal multiple sequence alignment based on pairwise comparisons.

Yonatan Bilu1, Pankaj K Agarwal, Rachel Kolodny

  • 1Department of Molecular Genetics, Weizmann Institute of Science, Rehovot, Israel. yonatan.bilu@weizmann.ac.il

IEEE/ACM Transactions on Computational Biology and Bioinformatics
|November 7, 2006
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

Maternal postpartum depression risk differentially affects infant development across sociocultural groups.

BMC psychology·2026
Same author

Modeling the Language of Codons with Artificial Intelligence.

Annual review of biomedical data science·2026
Same author

Systematic structure-based analysis of RET variants in MEN2A and Hirschsprung's disease, and the paradoxical co-occurrence of both conditions.

Disease models & mechanisms·2026
Same author

Data driven versus standard practice policies for personalized antidepressant treatment: a retrospective cohort study of electronic health records.

BMC psychiatry·2026
Same author

Interpretable prediction of zinc ion location in proteins with ZincSight.

Protein science : a publication of the Protein Society·2025
Same author

Differentiating Transient From Persistent Developmental Delays in a Nationwide Infant Cohort.

JAMA network open·2025
Same journal

circ2DGNN: circRNA-Disease Association Prediction via Transformer-Based Graph Neural Network.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

Hierarchical Hypergraph Learning in Association- Weighted Heterogeneous Network for miRNA- Disease Association Identification.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

Discriminative Domain Adaption Network for Simultaneously Removing Batch Effects and Annotating Cell Types in Single-Cell RNA-Seq.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

MLW-BFECF: A Multi-Weighted Dynamic Cascade Forest Based on Bilinear Feature Extraction for Predicting the Stage of Kidney Renal Clear Cell Carcinoma on Multi-Modal Gene Data.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

An End-to-End Knowledge Graph Fused Graph Neural Network for Accurate Protein-Protein Interactions Prediction.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

Generative Biomedical Event Extraction With Constrained Decoding Strategy.

IEEE/ACM transactions on computational biology and bioinformatics·2024
See all related articles

This study enhances multiple sequence alignment (MSA) by optimizing dynamic programming for predefined segments. Techniques significantly reduce computation time for optimal alignments, improving efficiency in computational biology.

Area of Science:

  • Computational molecular biology
  • Bioinformatics algorithms

Background:

  • Multiple Sequence Alignment (MSA) is crucial in computational biology.
  • Standard dynamic programming for MSA has exponential running time complexity.
  • Heuristics are often used due to computational costs.

Purpose of the Study:

  • To develop efficient techniques for optimal MSA with restricted matching segments.
  • To improve the running time of dynamic programming algorithms for MSA.

Main Methods:

  • Developed techniques to optimize dynamic programming for segment-based alignment.
  • Proved sufficiency of aligning predefined sequence segments instead of individual letters.
  • Identified "shortcuts" to expedite the dynamic programming scheme.
  • Explored transitive matching assumptions to restrict the search space.

Related Experiment Videos

Main Results:

  • Achieved optimal solutions for MSA within predefined segments.
  • Reduced input size by aligning segments, improving running time.
  • Empirical studies show 4 to 12 orders of magnitude speedup over basic dynamic programming.
  • Further improvements by restricting search space under transitivity assumption.

Conclusions:

  • The proposed techniques offer significant computational efficiency for optimal MSA.
  • Aligning segments and using shortcuts drastically reduces runtime.
  • The methods provide a practical approach to complex MSA problems in bioinformatics.