We introduce a new combinatorial formulation of chromosome physical-mapping by the sampling-without-replacement protocol.In this protocol, which is simple, inexpensive, and has been used to successfully map several organisms, equal-length clones are hybridized against a subset of the clones called probes, which are designed to form a maximal nonoverlapping clone-subset.The output of the protocol is the clone-probe hybridization matrix H.The problem of finding a maximum-likelihood reconstruction of the order of the probes along the chromosome in the presence of false positive and negative hybridization error is equivalent to finding the minimum number of entries of H to change to zeros so that the resulting matrix has at most 2 ones per row, and the consecutive-ones property across rows.This combinatorial problem, which we call 2-Consecutive-Ones Mapping, has a concise integer linear-prograniming formulation, to which we apply techniques from polyhedral combinatorics.The formulation is unique in that it does not explicitly represent the probe permutation, and in contrast to prior linear-programming approaches, the number of variables is small: in practice, linear in the number of clones.We derive a large class of facet-defining inequalities for the 2-consecutive-ones polytope that we call the augmented k- degree inequalities, and we show that the basic k-degree class can be efficiently separated using bipartite matchings.Computational results with an implementation of the resulting branch-and-cut algorithm applied to both simulated and real data from the complete genome of Aspergillus nidulans show that we can solve many problems to provable optimality and find maps of higher quality than previously possible.

A fundamental problem in computational biology is the construction of physical maps of chromosomes from hybridiz;c tion experiments between unique probes and clones of chromosome fragments in the presence of error.Alizadeh, Karp, Weisser and Zweig (AKWZ94] first considered a maximumlikelihood model of the problem that is equivalent to finding an o&ring of the probes that minimizes a weighted sum of errors, and developed several effective heuristics.We show that by exploiting information about the endprobes of clones, this model can be formulated as a weighted Betweenness Problem.Thii affords the signiicant advautage of allowing the well-developed tools of integer lmearprogramming aud branch-and-cut algorithms to be brought to bear on physical mapping, enabling us for the first time to solve small mapping instances to optima&y even in the presence of high error.We also show that by combining the optimal solution of many small overlapping Betweenness Problems, one can effectively screen errors from larger instances, and solve the edited instance to optimality as a Hamming-Distance Traveling Salesman Problem.This suggests a new combined approach to physical map construction.