R.M. Karp, I. Pe'er and R. Shamir
Abstract
Optical mapping is a novel technique for generating therestriction
map of a DNA molecule by observing many single, partially digested,
copies of it, using fluorescence microscopy. The real-life problem
is complicated by numerous factors: false positive and false negative
cut observations, inaccurate location measurements, unknown orientations
and faulty molecules. We present an algorithm for solving the
real-life problem. The algorithm combines continuous optimization
and combinatorial algorithms, applied to a non-uniform discretization
of the data. We present encouraging results on real experimental
data.