Double digest revisited: Complexity and Approximability in the Presence of Noisy Data

Mark Cieliebak, Stephan Eidenbenz, Gerhard Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)

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 a 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 APX-completeness for most of these variations. In a third part, we investigate these variations with the additional restriction that conincident 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.
Original languageEnglish
Title of host publicationComputing and Combinatorics
Subtitle of host publication9th Annual International Conference, COCOON 2003 Big Sky, MT, USA, July 25–28, 2003 Proceedings
EditorsTandy Warnow, Binhai Zhu
PublisherSpringer
Pages519-527
ISBN (Electronic)978-3-540-45071-9
ISBN (Print)978-3-540-40534-4
DOIs
Publication statusPublished - 2003
Event9th Annual International Conference on Computing and Combinatorics, COCOON 2003 - Big Sky, United States
Duration: 25 Jul 200328 Jul 2003
Conference number: 9

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume2697
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference9th Annual International Conference on Computing and Combinatorics, COCOON 2003
Abbreviated titleCOCOON
CountryUnited States
CityBig Sky
Period25/07/0328/07/03

Keywords

  • METIS-213323

Fingerprint

Dive into the research topics of 'Double digest revisited: Complexity and Approximability in the Presence of Noisy Data'. Together they form a unique fingerprint.

Cite this