The enhanced double digest problem for dna physical mapping

Ming Yang Kao, Jared Samet, Wing Kin Sung

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 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 under a certain restriction, which is satisfied reasonably frequently.

Original languageEnglish (US)
Title of host publicationAlgorithm Theory - SWAT 2000 - 7th Scandinavian Workshop on Algorithm Theory, 2000, Proceedings
EditorsMagnús M. Halldórsson
PublisherSpringer Verlag
Pages383-392
Number of pages10
ISBN (Print)3540676902, 9783540676904
DOIs
StatePublished - Jan 1 2000
Event7th Scandinavian Workshop on Algorithm Theory, SWAT 2000 - Bergen, Norway
Duration: Jul 5 2000Jul 7 2000

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1851
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other7th Scandinavian Workshop on Algorithm Theory, SWAT 2000
CountryNorway
CityBergen
Period7/5/007/7/00

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

  • Cite this

    Kao, M. Y., Samet, J., & Sung, W. K. (2000). The enhanced double digest problem for dna physical mapping. In M. M. Halldórsson (Ed.), Algorithm Theory - SWAT 2000 - 7th Scandinavian Workshop on Algorithm Theory, 2000, Proceedings (pp. 383-392). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1851). Springer Verlag. https://doi.org/10.1007/3-540-44985-X