dc.creatorFerreira, CE
dc.creatorde Souza, CC
dc.creatorWakabayashi, Y
dc.date2002
dc.date42005
dc.date2014-11-18T16:02:58Z
dc.date2015-11-26T16:56:34Z
dc.date2014-11-18T16:02:58Z
dc.date2015-11-26T16:56:34Z
dc.date.accessioned2018-03-28T23:44:00Z
dc.date.available2018-03-28T23:44:00Z
dc.identifierDiscrete Applied Mathematics. Elsevier Science Bv, v. 116, n. 41671, n. 161, n. 177, 2002.
dc.identifier0166-218X
dc.identifierWOS:000173568800010
dc.identifier10.1016/S0166-218X(00)00324-3
dc.identifierhttp://www.repositorio.unicamp.br/jspui/handle/REPOSIP/80602
dc.identifierhttp://www.repositorio.unicamp.br/handle/REPOSIP/80602
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/80602
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1277413
dc.descriptionWe 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.
dc.description116
dc.description41671
dc.description161
dc.description177
dc.languageen
dc.publisherElsevier Science Bv
dc.publisherAmsterdam
dc.publisherHolanda
dc.relationDiscrete Applied Mathematics
dc.relationDiscret Appl. Math.
dc.rightsfechado
dc.rightshttp://www.elsevier.com/about/open-access/open-access-policies/article-posting-policy
dc.sourceWeb of Science
dc.subjectinteger programming
dc.subjectcomputational biology
dc.subjectbranch-and-cut
dc.subjectpolyhedral combinatorics
dc.titleRearrangement of DNA fragments: a branch-and-cut algorithms
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución