Please use this identifier to cite or link to this item:
Type: Artigo de periódico
Title: Rearrangement Of Dna Fragments: A Branch-and-cut Algorithm
Author: Ferreira C.E.
De Souza C.C.
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 ke;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. © 2002 Elsevier Science B.V.
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 
2-s2.0-84867932002.pdf153.47 kBAdobe PDFView/Open

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