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