Some mathematical aspects of mapping DNA cosmids.
A number of experimental and mathematical problems must be solved before high resolution physical maps of mammalian chromosomes can be reliably determined. Such a map might consist of an ordered set of nonsequenced, overlapping DNA fragments 20,000-40,000 bases long, produced by digestion of a chromosome, using two restriction enzymes. Map construction requires assigning a signature to each fragment that differentiates it unambiguously from every other fragment, and then devising a computationally efficient algorithm that will provide a unique ordering of the fragments. In the first part of this paper we present a polynomial time algorithm that yields a unique map, and is largely independent of the method for assigning signatures. In the next section we analyze the distribution of lengths of restriction digest fragments and discuss the implications for the algorithm, including the expected number of map gaps. Finally, we discuss a specific method for assigning signatures proposed by Hans Lehrach, based on which of a panel of probes binds to a given fragment. In particular we examine the effects of fragment length heterogeneity on the theoretical optimum length and number of probes, and the extent to which false signatures might be obtained by nonspecific binding. We conclude that the Lehrach strategy is effective provided the number of probes is greater than or equal to 150, but that each fragment will need testing with at most 25 probes.