Calculating shared fragments for the single digest problem

A partial restriction map can be computed by using single digest fragments from a set of clones that are known to be in a contig. If there is no error or uncertainty in the data, so that the set of unique restriction fragments can be calculated exactly, then the restriction map can be assembled using a polynomial-time algorithm based on the consecutive 1´s property. However, there are typically both error and uncertainty in the data. The data being used are from the chromosome 16 mapping project at Los Alamos National Laboratory. The authors have developed an algorithm that consists of two steps: (1) calculate the set of unique restriction fragments and (2) assemble the fragments such that the set of fragments for each clone is contiguous. The problem of solving the first step when there are error and uncertainty in the data is addressed.