Physical mapping of chromosomes: A combinatorial problem in molecular biology

Our purpose is to reconstruct the relative placement of the clones along the DNA molecule; this information is lost in the construction of the clone library. In this article we restrict ourselves to the noiseless case, in which the data are free of experimental error. We also restrict ourselves to hybridization data. However, many of our algorithmic techniques can be extended to incorporate noise and restriction fragment data. Our experiments seem to hint at the following phenomenon. For small values of m, there is simply not enough information in the data to reveal the placement of clones, and therefore, all algorithms are expected to perform poorly. For very large m, the argument of section 6 shows that even the most simple-minded method such as the greedy algorithm is likely to find the true permutation. However, it seems that there is a range of values for m, depending on the underlying placement, where the result of the c⁺+c^- objective is superior to those of the greedy or the traveling salesman heuristics.