Mapping DNA by stochastic relaxation (Q1099802)

With the widely-rumored advent of a human genome project, the problem of DNA mapping has received more attention. Consider two or more enzymes specific for a different DNA subsequence, and a particular strand of DNA. Given the lengths of DNA produced by single and multiple enzyme cuts, ``the mapping problem'' is the reconstruction of the order of the different enzyme cut sites along the DNA. This paper gives an annealing (stochastic relaxation) algorithm which performs the mapping. The theory of subadditive processes shows that the double digest problem admits an exponentially increasing number of solutions as a function of sequence length. By reducing the partition problem to a special case of the double digest problem, the double digest problem is also shown to be in the class of NP complete problems which are conjectured to have no polynomial time solution. Problems related to circular DNA and inexact experimental measurements are also discussed.