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

Multiple sequence alignment with arbitrary gap costs: computing an optimal solution using polyhedral combinatorics.

Ernst Althaus1, Alberto Caprara, Hans-Peter Lenhof

  • 1International Computer Science Institute, Berkeley, CA 94704-1198, USA. althaus@icsi.berkeley.edu

Bioinformatics (Oxford, England)
|October 19, 2002
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

Sequence to structure insights into Lassa virus population-level biophysical properties and glycoprotein structure catalogue.

Npj viruses·2026
Same author

Lassa virus live tracking and lineage assignment: how nextstrain can enhance surveillance and public health in Africa and beyond.

Emerging microbes & infections·2026
Same author

DREAM-Stellar: parallel and space efficient exact local alignment.

BMC bioinformatics·2026
Same author

Engineering rank queries on bit vectors and strings.

Algorithms for molecular biology : AMB·2025
Same author

ganon2: up-to-date and scalable metagenomics analysis.

NAR genomics and bioinformatics·2025
Same author

How to predict effective drug combinations - moving beyond synergy scores.

iScience·2025
Same journal

conMItion: an R package adjusting confounding factors for associations in multi-omics.

Bioinformatics (Oxford, England)·2026
Same journal

SpaMFG: a Spatial Multi-omics Integration Method based on Feature Grouping.

Bioinformatics (Oxford, England)·2026
Same journal

CSCN: Inference of Cell-Specific Causal Networks Using Single-Cell RNA-Seq Data.

Bioinformatics (Oxford, England)·2026
Same journal

Sparse CCA-Based Mediation Analysis with High-Dimensional Exposures and Mediators.

Bioinformatics (Oxford, England)·2026
Same journal

Enhancing Cross-Context Generalization in Drug Perturbation Prediction with a Multimodal Conditional Diffusion Framework.

Bioinformatics (Oxford, England)·2026
Same journal

Primer Design through Submodular Function Estimation.

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

We present a novel integer linear program (ILP) for multiple sequence alignment with arbitrary gap costs. Our branch-and-cut algorithm effectively solves this ILP, achieving top-tier alignment quality and performance.

Area of Science:

  • Computational molecular biology
  • Bioinformatics
  • Algorithm development

Background:

  • Multiple sequence alignment (MSA) is a fundamental challenge in computational biology.
  • Existing MSA methods often involve NP-hard problems and struggle with arbitrary gap costs.

Purpose of the Study:

  • To introduce a general formulation for MSA using integer linear programming (ILP).
  • To develop an efficient algorithm for solving the ILP formulation to optimality.

Main Methods:

  • Formulation of MSA as an integer linear program (ILP) with arbitrary gap costs.
  • Development and application of a branch-and-cut algorithm to solve the ILP.
  • Performance evaluation using the BAliBase database for alignment quality and runtime.

Related Experiment Videos

Main Results:

  • The proposed ILP formulation provides a general approach for MSA.
  • The branch-and-cut algorithm effectively solves the ILP to optimality.
  • The implemented method demonstrates competitive performance and high-quality alignments compared to existing tools.

Conclusions:

  • The ILP-based approach offers a robust and scalable solution for multiple sequence alignment.
  • This method advances the field of computational molecular biology by providing an optimal and efficient alignment strategy.