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 'spine' for the library. We give a fairly precise characterization for this number."