Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


A branch-and-cut approach to physical mapping with end-probes

Christof, Thomas and Jünger, Michael and Kececioglou, John D. and Mutzel, Petra and Reinelt, Gerhard

MPI-I-96-1-027. November 1996, 10 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
A fundamental problem in computational biology is the
construction of physical maps of chromosomes from hybridization
experiments between unique probes and clones of chromosome fragments
in the presence of error.
Alizadeh, Karp, Weisser and Zweig~\cite{AKWZ94} first considered a
maximum-likelihood model of the problem that is equivalent to finding
an ordering of the probes that minimizes a weighted sum of errors,
and developed several effective heuristics. We show that by exploiting
information about the end-probes of clones, this model can be formulated
as a weighted Betweenness Problem.
This affords the significant advantage of allowing the well-developed tools
of integer linear-programming and branch-and-cut algorithms to be brought
to bear on physical mapping, enabling us for the first time to solve
small mapping instances to optimality 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.

References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-96-1-027.ps247 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView

URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Christof, Thomas and J{\"u}nger, Michael and Kececioglou, John D. and Mutzel, Petra and Reinelt, Gerhard},
  TITLE = {A branch-and-cut approach to physical mapping with end-probes},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-96-1-027},
  MONTH = {November},
  YEAR = {1996},
  ISSN = {0946-011X},