The enhanced double digest problem for DNA physical mapping

Ming Yang Kao; Jared Samet; Wing Kin Sung

doi:10.1023/A:1021946523069

The enhanced double digest problem for DNA physical mapping

Ming Yang Kao^*, Jared Samet, Wing Kin Sung

^*Corresponding author for this work

Computer Science

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	69-78
Number of pages	10
Journal	Journal of Combinatorial Optimization
Volume	7
Issue number	1
DOIs	https://doi.org/10.1023/A:1021946523069
State	Published - Mar 2003

Funding

∗Research supported in part by NSF Grant 9531028.

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

Access to Document

10.1023/A:1021946523069

Cite this

@article{50317a6258dd43c1a79fa1ff9642a682,

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 in certain theoretically interesting cases.",

keywords = "DNA physical mapping, Fast algorithms, Graph-theoretic techniques, NP-hardness",

author = "Kao, {Ming Yang} and Jared Samet and Sung, {Wing Kin}",

note = "Funding Information: ∗Research supported in part by NSF Grant 9531028.",

year = "2003",

month = mar,

doi = "10.1023/A:1021946523069",

language = "English (US)",

volume = "7",

pages = "69--78",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "1",

}

TY - JOUR

T1 - The enhanced double digest problem for DNA physical mapping

AU - Kao, Ming Yang

AU - Samet, Jared

AU - Sung, Wing Kin

N1 - Funding Information: ∗Research supported in part by NSF Grant 9531028.

PY - 2003/3

Y1 - 2003/3

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 in certain theoretically interesting cases.

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 in certain theoretically interesting cases.

KW - DNA physical mapping

KW - Fast algorithms

KW - Graph-theoretic techniques

KW - NP-hardness

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

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

U2 - 10.1023/A:1021946523069

DO - 10.1023/A:1021946523069

M3 - Article

AN - SCOPUS:0037371316

SN - 1382-6905

VL - 7

SP - 69

EP - 78

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 1

ER -

The enhanced double digest problem for DNA physical mapping

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this