AN ALGORITHM FOR ANALYZING PROBED PARTIAL DIGESTION EXPERIMENTS

A partial digestion of DNA (e.g. cosmid, Lambda, YAC, chromosome) is p erformed and the lengths of theses fragments which hybridize to a labe led probe are measured using gel electrophoresis. We give an efficient algorithm that takes as input this experimental data and proposes one or more candidate solutions. Each solution designates the location of each restriction sire and specifies the endpoints of each fragment. ( Further experiments can then be designed to select the correct solutio n from this small set of candidates.) The algorithm works well even wh en the experiment gives inexact values for the lengths.