A BRANCH-AND-CUT APPROACH TO PHYSICAL MAPPING OF CHROMOSOMES BY UNIQUE END-PROBES

A fundamental problem in computational biology is the construction of physical maps of chromosomes from hybridization experiments between un ique probes and clones of chromosome fragments in the presence of erro r, Alizadeh, Karp, Weisser and Zweig (Algorithmica 13:1/2, 52-76, 1995 ) first considered a maximum-likelihood model of the problem that is e quivalent to finding an ordering of the probes that minimizes a weight ed sum of errors and developed several effective heuristics. We show t hat by exploiting information about the end-probes of clones, this mod el can be formulated as a Weighted Betweenness Problem, This affords t he significant advantage of allowing the well-developed tools of integ er linear-programming and branch-and-cut algorithms to be brought to b ear on physical mapping, enabling us for the first time to solve small mapping instances to optimality even in the presence of high error, W e also show that by combining the optimal solution of many small overl apping Betweenness Problems, one can effectively screen errors from la rger instances and solve the edited instance to optimality as a Hammin g-Distance Traveling Salesman Problem, This suggests a new approach, a Betweenness-Traveling Salesman hybrid, for constructing physical maps .