Combinatorial optimization in DNA mapping – a computational thread of the Simplified Partial Digest Problem

In the paper, the problem of the genome mapping of DNA molecules is presented. In particular, the new approach – the Simplified Partial Digest Problem (SPDP), is analyzed. This approach, although easy in laboratory implementation and robust with respect to measurement errors, when formulated in terms of a combinatorial search problem, is proved to be strongly NP-hard for the general error-free case. For a subproblem of the SPDP, a simple O(nlogn)-time algorithm is given, where n is a number of restriction sites.