Title: Solving large double digestion problems for DNA restriction mapping by using branch-and-bound integer linear programming

Authors: Z. Wu, Y. Zhang

Addresses: Department of Mathematics, Iowa State University, Ames, Iowa 50011, USA. ' Department of Computational and Applied Mathematics, Houston, Texas 77005, USA

Abstract: The double digestion problem for DNA restriction mapping has been proved to be NP-complete and intractable if the numbers of the DNA fragments become large. Several approaches to the problem have been tested and proved to be effective only for small problems. In this paper, we formulate the problem as a mixed-integer linear program (MIP) by following (Waterman, 1995) in a sightly different form. With this formulation and using state-of-the-art integer programming techniques, we can solve randomly generated problems whose search space sizes are many-magnitude larger than previously reported testing sizes.

Keywords: DNA restriction mapping; double digestion problem; mixed integer linear programming; MILP; bioinformatics; genomic sequencing.

DOI: 10.1504/IJBRA.2008.021173

International Journal of Bioinformatics Research and Applications, 2008 Vol.4 No.4, pp.351 - 362

Published online: 08 Nov 2008 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article