### Ordering Clone Libraries in
Computational Biology

**Alan Michael Frieze **
Dept. of Mathematics,
Carnegie Mellon University,
Pittsburgh PA 15213

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.

Program

DIMACS Homepage

Contacting the Center

Document last modified on March 28, 2000.