Mapping DNA by stochastic relaxation

The multiple digest mapping problem arising in molecular biology can be stated roughly as follows. A linear or circular segment of DNA is cut at all occurrences of a specific short pattern by restriction enzymes. By using restriction enzymes singly and in combination it is required to construct a map showing the location of cleavage sites. In this paper we first consider the efficacy of a simulated annealing algorithm towards the solution to the multiple digest problem. Second, the double digest problem, the simplest version of the multiple digest problem with only two restriction enzymes used, is shown to admit an exponentially increasing number of solutions as a function of the length of the segment under a particular probability model. Next, the double digest problem is shown to lie in the class of NP complete problems which are conjectured to have no polynomial time solution. Last, the construction of circular maps is considered and the problem of measurement error is discussed.