(Problem 4.9, page 119-121 of Jones & Pevzner) Double Digest mapping is a restriction mapping technique that is even simpler (experimentally) than a partial digest but uses two different restriction enzymes. In this approach, biologists digest DNA in such a way that only fragments between consecutive sites are formed (see Fig. 4.10). One way to construct a double digest map is to measure the fragment lengths (but not the order) from a complete digestion of the DNA by each of the two enzymes singly, and then by the two enzymes applied together. The problem of determining the positions of the cuts from fragment length data is known as the Double Digest problem, or DDP. Figure 4.10 shows DNA cut by two restriction enzymes, A (shown by a circle) and B (shown by a square). Through gel electrophoresis experiments with these two restriction enzymes, a biologist can obtain information about the sizes of the restriction fragments generated by each individually. However, there are many orderings (maps) corresponding to these fragment lengths. To find out which of the maps is the correct one, biologists cleave DNA by both enzymes at the same time; this procedure is known as a double digest. The two maps presented in figure 4.10 produce the same single digests A and B but different double digests A+B. The double digest that fits experimental data corresponds to the correct map. The Double Digest problem is to find a physical map, given three sets of fragment lengths: A, B, and A + B. Devise a brute force algorithm for the DDP and suggest a branch-and-bound approach to improve its performance.

10 11 14 16 17 11 12 15 17 3 Figure 4.10 Restriction map of two restriction enzymes. When the digest is per- formed with each restriction enzyme separately and then with both enzymes com bined, you may be able to reconstruct the original restriction map. The single digests 1,2, 4,5, 6} and {1, 3, 3,3, 8) as well as the double digest {1,1,1,1,2,2,2, 3,5} allow one to uniquely reconstruct the restriction map (a). There are many other restriction maps that yield the same single digests, but produce a different double digest (b) 10 11 14 16 17 11 12 15 17 3 Figure 4.10 Restriction map of two restriction enzymes. When the digest is per- formed with each restriction enzyme separately and then with both enzymes com bined, you may be able to reconstruct the original restriction map. The single digests 1,2, 4,5, 6} and {1, 3, 3,3, 8) as well as the double digest {1,1,1,1,2,2,2, 3,5} allow one to uniquely reconstruct the restriction map (a). There are many other restriction maps that yield the same single digests, but produce a different double digest (b)