An algorithm combining discrete and continuous methods for optical mapping.
Optical mapping is a novel technique for generating the restriction 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.
Karp
R M
RM
Department of Computer Science & Engineering, University of Washington, Seattle 98195-2350, USA. karp@cs.washington.edu
Pe'er
I
I
Shamir
R
R
D000465:Algorithms; D016013:Likelihood Functions; D008856:Microscopy, Fluorescence / Q000379:methods; D015233:Models, Statistical; D011336:Probability; D015183:Restriction Mapping / Q000379:methods*