Combinatorial optimization in DNA mapping — a computational thread of the Simplified Partial Digest Problem
Institute of Computing Science, Poznan University of
Technology, Piotrowo 3A, 60–965 Poznan, Poland; email@example.com
2 Institute of Bioorganic Chemistry, Polish Academy of Sciences, Poznan, Poland; firstname.lastname@example.org
Accepted: 28 October 2005
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.
Key words: Combinatorial optimization / DNA restriction mapping / partial digest / computational complexity.
© EDP Sciences, 2006