ABSTRACT
Partial Digest Problem, commonly addressed via its abbreviation “PDP,” came into existence long back in 1930, when it first appeared in the field of X-ray crystallography (Patterson, 1935). Later, various techniques belonging to different domains of computer science have been proposed to solve PDP, but all have their own pros and cons. In 1970, Hamilton Smith, an American microbiologist discovered the fact that enzymes cleave a particular Deoxyribonucleic Acid molecule at each occurrence of a distinct sequence (Jones et al., 2004). The locations of these cuts are commonly referred to as restriction sites. The restriction site mapping, which will be elaborated further in this chapter, is a salient application of PDP (Bellon, 1988; Stefik, 1978). A digest experiment in biology is a way of preparing the DNA for processing. Two of the widely known variants of the digest experiments are (i) Complete Digest and (ii) Partial Digest. The Complete Digest problem considers the distance between consecutive sites, whereas PDP observes the distance of 166each pair of restriction site. Gel electrophoresis technique helps find the distances between every pair of restriction site that acts as the building block for reconstruction of DNA. PDP has many applications in computational biology, like DNA cloning, DNA sequencing (Baker, 2011), and genome cloning (Dear, 2001).
