We consider a branch-and-cut approach for solving the multiple sequence alignment problem, which is a central problem in computational biology. We propose a general model for this problem in which arbitrary gap costs are allowed. An interesting aspect of our approach is that the three (exponentially large) classes of natural valid inequalities that we consider turn out to be both facet-defining for the convex hull of integer solutions and separable in polynomial time. Both the proofs that these classes of valid inequalities are facet-defining and the description of the separation algorithms are far from trivial. Experimental results on several benchmark instances show that our method outperforms the best tools developed so far, in that it produces alignments that are better from a biological point of view. A noteworthy outcome of the results is the effectiveness of using branch-and-cut with only a carefully-selected subset of the variables as a heuristic.

A branch-and-cut algorithm for multiple sequence alignment / E. Althaus; A. Caprara; H-P. Lenhof; K. Reinert. - In: MATHEMATICAL PROGRAMMING. - ISSN 0025-5610. - STAMPA. - 105:(2006), pp. 387-425. [10.1007/s10107-005-0659-3]

A branch-and-cut algorithm for multiple sequence alignment

CAPRARA, ALBERTO;
2006

Abstract

We consider a branch-and-cut approach for solving the multiple sequence alignment problem, which is a central problem in computational biology. We propose a general model for this problem in which arbitrary gap costs are allowed. An interesting aspect of our approach is that the three (exponentially large) classes of natural valid inequalities that we consider turn out to be both facet-defining for the convex hull of integer solutions and separable in polynomial time. Both the proofs that these classes of valid inequalities are facet-defining and the description of the separation algorithms are far from trivial. Experimental results on several benchmark instances show that our method outperforms the best tools developed so far, in that it produces alignments that are better from a biological point of view. A noteworthy outcome of the results is the effectiveness of using branch-and-cut with only a carefully-selected subset of the variables as a heuristic.
2006
A branch-and-cut algorithm for multiple sequence alignment / E. Althaus; A. Caprara; H-P. Lenhof; K. Reinert. - In: MATHEMATICAL PROGRAMMING. - ISSN 0025-5610. - STAMPA. - 105:(2006), pp. 387-425. [10.1007/s10107-005-0659-3]
E. Althaus; A. Caprara; H-P. Lenhof; K. Reinert
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/25770
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 14
social impact