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 nonuniform discretization of the data. We present encouraging results on real experimental data and on simulated data.
Karp
R M
RM
Department of Electrical Engineering and Computer Science, University of California, Berkeley, CA 94720-1776, USA. karp@cs.berkeley.edu
Pe'er
I
I
Shamir
R
R
D000465:Algorithms; D003198:Computer Simulation; D004247:DNA / Q000235:genetics; D008856:Microscopy, Fluorescence; D055095:Optics and Photonics; D015183:Restriction Mapping / Q000379:methods* / Q000706:statistics & numerical data
D004247:DNA