Send to

Choose Destination
See comment in PubMed Commons below
Int J Bioinform Res Appl. 2008;4(4):351-62.

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

Author information

  • 1Department of Mathematics, Iowa State University, Ames, Iowa 50011, USA.


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 slightly 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.

[PubMed - indexed for MEDLINE]

LinkOut - more resources

Full Text Sources

Other Literature Sources


PubMed Commons home

PubMed Commons

How to join PubMed Commons

    Supplemental Content

    Full text links

    Icon for Atypon
    Loading ...
    Write to the Help Desk