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; jblazewicz@cs.put.poznan.pl
² Institute of Bioorganic Chemistry, Polish Academy of Sciences, Poznan, Poland; marta@cs.put.poznan.pl

Received: 22 June 2005
Accepted: 28 October 2005

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(nlogn)-time algorithm is given, where n is a number of restriction sites.