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

6 Citations (Scopus)

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
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

Fingerprint

DNA sequences
NP-complete problem
DNA Sequence
Linear Time
Restriction

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Kao, M. Y., Samet, J., & Sung, W. K. (2000). The enhanced double digest problem for dna physical mapping. In 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
Kao, Ming Yang ; Samet, Jared ; Sung, Wing Kin. / The enhanced double digest problem for dna physical mapping. Algorithm Theory - SWAT 2000 - 7th Scandinavian Workshop on Algorithm Theory, 2000, Proceedings. Springer Verlag, 2000. pp. 383-392 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{51f4a124f8494584b6f3d5e240d0c6d7,
title = "The enhanced double digest problem for dna physical mapping",
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.",
keywords = "DNA physical mapping, Fast algorithms, Graph-theoretic techniques, NP-hardness",
author = "Kao, {Ming Yang} and Jared Samet and Sung, {Wing Kin}",
year = "2000",
month = "1",
day = "1",
doi = "10.1007/3-540-44985-X",
language = "English (US)",
isbn = "3540676902",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "383--392",
booktitle = "Algorithm Theory - SWAT 2000 - 7th Scandinavian Workshop on Algorithm Theory, 2000, Proceedings",
address = "Germany",

}

Kao, MY, Samet, J & Sung, WK 2000, The enhanced double digest problem for dna physical mapping. in Algorithm Theory - SWAT 2000 - 7th Scandinavian Workshop on Algorithm Theory, 2000, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1851, Springer Verlag, pp. 383-392, 7th Scandinavian Workshop on Algorithm Theory, SWAT 2000, Bergen, Norway, 7/5/00. https://doi.org/10.1007/3-540-44985-X

The enhanced double digest problem for dna physical mapping. / Kao, Ming Yang; Samet, Jared; Sung, Wing Kin.

Algorithm Theory - SWAT 2000 - 7th Scandinavian Workshop on Algorithm Theory, 2000, Proceedings. Springer Verlag, 2000. p. 383-392 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1851).

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

TY - GEN

T1 - The enhanced double digest problem for dna physical mapping

AU - Kao, Ming Yang

AU - Samet, Jared

AU - Sung, Wing Kin

PY - 2000/1/1

Y1 - 2000/1/1

N2 - 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.

AB - 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.

KW - DNA physical mapping

KW - Fast algorithms

KW - Graph-theoretic techniques

KW - NP-hardness

UR - http://www.scopus.com/inward/record.url?scp=84956864939&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84956864939&partnerID=8YFLogxK

U2 - 10.1007/3-540-44985-X

DO - 10.1007/3-540-44985-X

M3 - Conference contribution

AN - SCOPUS:84956864939

SN - 3540676902

SN - 9783540676904

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 383

EP - 392

BT - Algorithm Theory - SWAT 2000 - 7th Scandinavian Workshop on Algorithm Theory, 2000, Proceedings

PB - Springer Verlag

ER -

Kao MY, Samet J, Sung WK. The enhanced double digest problem for dna physical mapping. In Algorithm Theory - SWAT 2000 - 7th Scandinavian Workshop on Algorithm Theory, 2000, Proceedings. Springer Verlag. 2000. p. 383-392. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-44985-X