MAPPING CLONES WITH A GIVEN ORDERING OR INTERLEAVING

We study the problem of constructing a most compact physical map for a collection of clones whose ordering or interleaving on a DNA molecule are given. Each clone is a contiguous section of the DNA and is repre sented by its fingerprint obtained from biochemical experiments. In th is paper we consider two kinds of mapping: single complete digest mapp ing, in which the fingerprint of a clone is a multiset containing the sizes of the restriction fragments occurring in the clone, and mapping by hybridization of probes, in which the fingerprint of a clone is a multiset consisting of the short oligonucleotide probes occurring in t he clone. Our goal is to position the clones and restriction fragments (or probes) on the DNA consistently with the given ordering or interl eaving so that the total number of restriction fragments (resp. probes ) required on the DNA is minimized. We first formulate this as a const rained path cover problem on a multistage graph. Using this formulatio n, it is shown that finding a most compact map for clones with a given ordering is NP-hard. The approximability of the problem is then consi dered. We present a simple approximation algorithm with ratio 2. This is in fact the best possible as the above NP-hardness proof actually s hows that achieving ratio 2 - epsilon is impossible for any constant e psilon > 0, unless P = NP. We also give a polynomial-time approximatio n scheme when the multiplicity is bounded by one (i.e., when the multi sets are actually sets). The exact complexity of the problem in this s pecial case is presently unknown. Finally we consider the mapping prob lem when an interleaving is given which depicts how the clones overlap with each other on the DNA. In the case of restriction fragment data, it is shown that finding a consistent map is NP-complete even if the multiplicity is bounded by 3. This may suggest that information about the interleaving of clones does not necessarily make the problem compu tationally easier in single complete digest mapping. On the other hand , in the case of hybridization data, there is an efficient algorithm t o construct a most compact map when the interleaving of clones is give n.