title: Ordering clone libraries in computational biology.
abstract: We consider a probabilistic model, due to Lander and Waterman and to Alizadeh, Karp, Newberg and Weisser, for the physical mapping of DNA molecules. Within this model, we answer precisely a question of Alizadeh et al. concerning the minimum number of probes required to reconstruct the entire ordering of a given clone library with high probability. We also examine the related problem of determining the least number of probes required to construct a "tiling" for the library. We give a fairly precise characterization for this number.
mesh_terms: D002874:Chromosome Mapping; D003001:Cloning, Molecular; D004247:DNA / Q000737:chemistry* / Q000235:genetics*; D015723:Gene Library; D008433:Mathematics; D008957:Models, Genetic; D011336:Probability
chemical_list: D004247:DNA