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