Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/101869
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.
Editor: 
Rights: fechado
Identifier DOI: 10.1016/S0166-218X(00)00324-3
Address: http://www.scopus.com/inward/record.url?eid=2-s2.0-84867932002&partnerID=40&md5=8e0e67c9b0c97adbe144fece6c27d4de
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.