Abstract
We propose an algorithm which efficiently constructs a physical map of DNA from a fingerprinted library of random clones. The algorithm clusters clones into contiguous regions using restriction enzyme digest data. Clones which contain overlapping genomic regions are detected and are grouped into an island in such a way that disjoint islands which can be linked by the clones are joined together automatically. This approach solves a common problem in fingerprinting { linking disjoint islands becomes more difficult and slow as mapping goes on. A map is produced in O(km2 n) time where k is the number of cleavage sites of a clone, m is the number of clones in a library, and n is the number of libraries. Our approach provides a general and efficient means for constructing long-range physical maps in large-scale genome mapping.