The enhanced double digest problem for DNA physical mapping

Ming Yang Kao*, Jared Samet, Wing Kin Sung

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


The double digest problem is a common NP-hard approach to constructing physical maps of DNA sequences. This paper presents a new approach called the enhanced double digest problem. Although this new problem is also NP-hard, it can be solved in linear time in certain theoretically interesting cases.

Original languageEnglish (US)
Pages (from-to)69-78
Number of pages10
JournalJournal of Combinatorial Optimization
Issue number1
StatePublished - Mar 2003


  • DNA physical mapping
  • Fast algorithms
  • Graph-theoretic techniques
  • NP-hardness

ASJC Scopus subject areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'The enhanced double digest problem for DNA physical mapping'. Together they form a unique fingerprint.

Cite this