Artículos de revistas
Rearrangement of DNA fragments: a branch-and-cut algorithms
Registro en:
Discrete Applied Mathematics. Elsevier Science Bv, v. 116, n. 41671, n. 161, n. 177, 2002.
0166-218X
WOS:000173568800010
10.1016/S0166-218X(00)00324-3
Autor
Ferreira, CE
de Souza, CC
Wakabayashi, Y
Institución
Resumen
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. 116 41671 161 177