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 algorithms|
de Souza, CC
|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.|
|Editor:||Elsevier Science Bv|
|Appears in Collections:||Unicamp - Artigos e Outros Documentos|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.