Constraint checking for restriction site mapping

Introduces an algorithm for the restriction site mapping problem, based on Pratt´s separation theory. The algorithm accepts data from single and double digests of a DNA molecule, in which every fragment is given a range of possible lengths depending on experimental errors. As fragments are being assembled into potential maps of the original molecule, a sound and complete constraint checker is applied which extracts the maximum amount of information from fragment lengths. A fast checking algorithm for two enzymes is presented, and an extension of Floyd´s algorithm for the all-pairs shortest paths problem is adopted for multi-enzyme cases. Existing methods for checking fragment lengths are either weaker subset or special cases of the authors´ methods.<>