On the complexity of the DNA Simplified Partial Digest Problem

Blazewicz, J. and Kasprzak, M.

    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.
Cite as: Blazewicz, J. and Kasprzak, M. (2006). On the complexity of the DNA Simplified Partial Digest Problem. In Proc. Twelfth Computing: The Australasian Theory Symposium (CATS2006), Hobart, Australia. CRPIT, 51. Gudmundsson, J. and Jay, B., Eds. ACS. 93-100.
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS