A branch-and-cut algorithm for multiple sequence alignment

DOI10.1007/S10107-005-0659-3MaRDI QIDQ2583133zbMATH OpenOpenAlexFDO

Authors Ernst Althaus, Alberto Caprara, Hans-Peter Lenhof, 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

branch-and-cut approachheuristicmultiple sequence alignment problem

Mathematics Subject Classification ID

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

Recommendations

• An optimization approach to multiple sequence alignment
• Approximation algorithms for multiple sequence alignment
• scientific article; zbMATH DE number 5171932
• A New Dynamic Programming Algorithm for Multiple Sequence Alignment
• Approximation algorithms for multiple sequence alignment under a fixed evolutionary tree
• scientific article; zbMATH DE number 2243390
• A fast algorithm for the constrained multiple sequence alignment problem

Cites work

• A Polyhedral Approach to the Asymmetric Traveling Salesman Problem
• Algorithms on Strings, Trees and Sequences
• Compact optimization can outperform separation: a case study in structural proteomics
• Compact vs. exponential-size LP relaxations
• scientific article; zbMATH DE number 432797 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Potential function methods for approximately solving linear programming problems: theory and practice.
• Sequence comparison with mixed convex and concave costs
• The Multiple Sequence Alignment Problem in Biology
• Using separation algorithms to generate mixed integer model reformulations

Cited in

(6)

• A Lagrangian relaxation approach for the multiple sequence alignment problem
• Approximation algorithms for multiple sequence alignment under a fixed evolutionary tree
• Mathematical programming in computational biology: an annotated bibliography
• scientific article; zbMATH DE number 1615272 (Why is no real title available?)
• Integer Linear Programming in Computational Biology
• Exact Multiple Sequence Alignment by Synchronized Decision Diagrams

Describes a project that uses

Uses Software

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2583133)