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

Abstract

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
Volume7
Issue number1
DOIs
StatePublished - Mar 2003

Keywords

  • 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

Fingerprint

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

Cite this