Can I read A Branch-and-cut Approach to Physical Mapping with End-probes on EtoBox?

A Branch-and-cut Approach to Physical Mapping with End-probes by Christof, Thomas ;Jünger, Michael ;Kececioglu, John ;Mutzel, Petra ;Reinelt, Gerhard is a scholarly article available to read on EtoBox.

What is A Branch-and-cut Approach to Physical Mapping with End-probes about?

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. ## K

Author

Christof, Thomas ;Jünger, Michael ;Kececioglu, John ;Mutzel, Petra ;Reinelt, Gerhard

Publisher

ACM Press

Published

1997

Language

EN