Devise a brute force algorithm for the DDP and suggest a branch-and-bound approach to improve its performance. Another technique used to build restriction maps leads to the Probed Partial Digest...

Devise a brute force algorithm for the DDP and suggest a branch-and-bound approach to improve its performance.

Another technique used to build restriction maps leads to the Probed Partial Digest problem (PPDP). In this method DNA is partially digested with a restriction enzyme, thus generating a collection of DNA fragments between every two cutting sites. After this, a labeled probe that attaches to the DNA between two cutting sites is hybridized to the partially digested DNA, and the sizes of fragments to which the probe hybridizes are measured. In contrast to the PDP, where the input consists of all partial fragments, the input for the PPDP consists of all partial fragments that contain a given point (this point corresponds to the position of the labeled probe). The problem is to reconstruct the positions of the sites from the multiset of measured lengths.  In the PPDP, we assume that the labeled probe is hybridized at position 0 and that A is the set of restriction sites with negative coordinates while B is the set of restriction sites with positive coordinates. The probed partial digest experiment provides the multiset {b−a : a ∈ A, b ∈ B} and the problem is to find A and B given this set.