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|
De Souza C.C.
|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.|
|Appears in Collections:||Unicamp - Artigos e Outros Documentos|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.