Artículos de revistas
Rearrangement Of Dna Fragments: A Branch-and-cut Algorithm
Registro en:
Discrete Applied Mathematics. , v. 116, n. 1-2, p. 161 - 177, 2002.
0166218X
10.1016/S0166-218X(00)00324-3
2-s2.0-84867932002
Autor
Ferreira C.E.
De Souza C.C.
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 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. 116 1-2 161 177 Crowder, H., Padberg, M.W., Solving large-scale symmetric traveling salesman problems to optimality (1980) Management Sci., 26, pp. 495-509 Garey, M.R., Johnson, D.S., (1979) Computer and Intractability - A Guide to the Theory of NP-Completeness, , Freeman New York Grötschel, M., Lovász, L., Schrijver, A., (1988) Geometric Algorithms and Combinatorial Optimization, , Springer Berlin Kececioglu, J.D., (1991) Exact and Approximation Algorithms for DNA Sequence Reconstruction, , Ph.D. Thesis, University of Arizona, Tucson Kececioglu, J.D., Myers, E.W., Combinatorial algorithms for DNA sequence assembly (1995) Algorithmica, 13, pp. 7-51 Meidanis, J., (1992) Algorithms for Problems in Computational Genetics, , Ph.D. Thesis, University of Wisconsin, Madison Meidanis, J., Setubal, J.C., (1997) Computational Molecular Biology, , PWS Publishing Company Boston Padberg, M.W., Grötschel, M., Polyhedral aspects of the travelling salesman problem II: Computations (1985) The Travelling Salesman Problem, , E.L. Lawler, J.K. Lenstra, A.H.G. Rinooy Kan, Wiley New York Siegel, A.F., Roach, J.C., Magness, C., Thayer, E., Van Den Engh, G., Optimization of restriction fragment DNA mapping (1998) Journal of Computational Biology, 5 (1), pp. 113-126