On the complexity of the DNA simplified partial digest problem
Jacek Błażewicz, Marta Kasprzak · Computing: The Australasian Theory Symposium · 2006
The problem to be addressed is one of the genome mapping of DNA molecules. The new approach -- the Simplified Partial Digest Problem (SPDP), is analyzed. This approach is easy in laboratory implementation and robust with respect to measurement errors. In the paper, it is formulated in terms of a combinatorial search problem and proved to be strongly NP-hard for the general error-free case. For a subproblem of the SPDP, a simple O(n log n)-time algorithm is given, where n is a number of restriction sites.