Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/80602
Type: Artigo de periódico
Title: Rearrangement of DNA fragments: a branch-and-cut algorithms
Author: Ferreira, CE
de Souza, CC
Wakabayashi, Y
Abstract: We consider a problem called minimum k-contig problem (MkCP), whose specialization to an alphabet with four symbols can be seen as a problem that arises in the process of arranging DNA fragments to reconstruct a molecule. We present a graph theoretical formulation of MkCP and mention some extensions. We show this problem to be NP-hard for every k greater than or equal to 1 (for an alphabet that is not of fixed cardinality). A 0/1 integer linear programming formulation of the problem is given and some results of a branch-and-cut algorithm based on this formulation are discussed. (C) 2002 Elsevier Science B.V. All rights reserved.
Subject: integer programming
computational biology
branch-and-cut
polyhedral combinatorics
Country: Holanda
Editor: Elsevier Science Bv
Rights: fechado
Identifier DOI: 10.1016/S0166-218X(00)00324-3
Date Issue: 2002
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
WOS000173568800010.pdf153.47 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.