title: Complexity and approximability of double digest.
abstract: We revisit the DOUBLE DIGEST problem, which occurs in sequencing of large DNA strings and consists of reconstructing the relative positions of cut sites from two different enzymes. We first show that DOUBLE DIGEST is strongly NP-complete, improving upon previous results that only showed weak NP-completeness. Even the (experimentally more meaningful) variation in which we disallow coincident cut sites turns out to be strongly NP-complete. In the second part, we model errors in data as they occur in real-life experiments: we propose several optimization variations of DOUBLE DIGEST that model partial cleavage errors. We then show that most of these variations are hard to approximate. In the third part, we investigate variations with the additional restriction that coincident cut sites are disallowed, and we show that it is NP-hard to even find feasible solutions in this case, thus making it impossible to guarantee any approximation ratio at all.
authors.affiliation: Institute of Theoretical Computer Science, ETH Zurich, 8092 Zurich, Switzerland. cieliebak@inf.ethz.ch
authors.forename: Mark
authors.initials: M
authors.lastname: Cieliebak
authors.forename: Stephan
authors.initials: S
authors.lastname: Eidenbenz
authors.forename: Gerhard J
authors.initials: GJ
authors.lastname: Woeginger
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D003198:Computer Simulation; D004262:DNA Restriction Enzymes / Q000737:chemistry* / Q000235:genetics; D005819:Genetic Markers / Q000235:genetics; D008956:Models, Chemical; D008957:Models, Genetic; D015233:Models, Statistical; D008969:Molecular Sequence Data; D015183:Restriction Mapping / Q000379:methods*; D016415:Sequence Alignment; D017422:Sequence Analysis, DNA / Q000379:methods*
chemical_list: D005819:Genetic Markers; D004262:DNA Restriction Enzymes