J. Blazewicz, M. Kasprzak,
"Combinatorial optimization in DNA mapping - a computational thread of the
Simplified Partial Digest Problem",
RAIRO - Operations Research 39 (2005) 227-241.
Download full text
Abstract:
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(n log n)-time
algorithm is given, where n is a number of restriction sites.
Back to the List of publications
10 Apr 2006