A branch-and-cut algorithm for multiple sequence alignment

DOI10.1007/s10107-005-0659-3zbMath1085.90060OpenAlexW2135434753MaRDI QIDQ2583133

Alberto Caprara, Hans-Peter Lenhof, Ernst Althaus, Knut Reinert

Publication date: 13 January 2006

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-005-0659-3

zbMATH Keywords

heuristicbranch-and-cut approachmultiple sequence alignment problem

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items (4)

Mathematical programming in computational biology: an annotated bibliography ⋮ A Lagrangian relaxation approach for the multiple sequence alignment problem ⋮ Integer Linear Programming in Computational Biology ⋮ Exact Multiple Sequence Alignment by Synchronized Decision Diagrams

Uses Software

• LEDA
• SCIP
• SCIL
• Balibase
• T-coffee
• MUMMER

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Using separation algorithms to generate mixed integer model reformulations
• Potential function methods for approximately solving linear programming problems: theory and practice.
• Compact vs. exponential-size LP relaxations
• Compact optimization can outperform separation: a case study in structural proteomics
• Sequence comparison with mixed convex and concave costs
• The Multiple Sequence Alignment Problem in Biology
• Algorithms on Strings, Trees and Sequences
• A Polyhedral Approach to the Asymmetric Traveling Salesman Problem

This page was built for publication: A branch-and-cut algorithm for multiple sequence alignment