Recognizing DNA graphs is difficult

Rudi Pendavingh; Petra Schuurman; Gerhard Woeginger

doi:10.1016/S0166-218X(02)00287-1

Recognizing DNA graphs is difficult

Rudi Pendavingh, Petra Schuurman, Gerhard Woeginger

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

12 Citations (Scopus)

140 Downloads (Pure)

Abstract

DNA graphs are the vertex induced subgraphs of De Bruijn graphs over a four letter alphabet. In this paper, we prove the NP-hardness of various recognition problems for subgraphs of De Bruijn graphs; in particular, the recognition of DNA graphs is shown to be NP-hard. As a consequence, two open questions from a recent paper by B a ewicz et al. (Discrete Appl. Math. 98, (1999) 1) are answered in the negative.

Original language	English
Pages (from-to)	85-94
Number of pages	10
Journal	Discrete applied mathematics
Volume	127
Issue number	1
DOIs	https://doi.org/10.1016/S0166-218X(02)00287-1
Publication status	Published - 2003

Keywords

Recognition algorithm
NP-hardness
Graph Theory
De Bruijn graph
DNA computing
DNA graphs
Computational Complexity

Access to Document

10.1016/S0166-218X(02)00287-1Licence: Other

Pendavingh03recognizingFinal published version, 117 KBLicence: Other

Cite this

@article{47aff9e894af41339f23ccff3bbf2b18,

title = "Recognizing DNA graphs is difficult",

abstract = "DNA graphs are the vertex induced subgraphs of De Bruijn graphs over a four letter alphabet. In this paper, we prove the NP-hardness of various recognition problems for subgraphs of De Bruijn graphs; in particular, the recognition of DNA graphs is shown to be NP-hard. As a consequence, two open questions from a recent paper by B a ewicz et al. (Discrete Appl. Math. 98, (1999) 1) are answered in the negative.",

keywords = "Recognition algorithm, NP-hardness, Graph Theory, De Bruijn graph, DNA computing, DNA graphs, Computational Complexity",

author = "Rudi Pendavingh and Petra Schuurman and Gerhard Woeginger",

year = "2003",

doi = "10.1016/S0166-218X(02)00287-1",

language = "English",

volume = "127",

pages = "85--94",

journal = "Discrete applied mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - Recognizing DNA graphs is difficult

AU - Pendavingh, Rudi

AU - Schuurman, Petra

AU - Woeginger, Gerhard

PY - 2003

Y1 - 2003

N2 - DNA graphs are the vertex induced subgraphs of De Bruijn graphs over a four letter alphabet. In this paper, we prove the NP-hardness of various recognition problems for subgraphs of De Bruijn graphs; in particular, the recognition of DNA graphs is shown to be NP-hard. As a consequence, two open questions from a recent paper by B a ewicz et al. (Discrete Appl. Math. 98, (1999) 1) are answered in the negative.

AB - DNA graphs are the vertex induced subgraphs of De Bruijn graphs over a four letter alphabet. In this paper, we prove the NP-hardness of various recognition problems for subgraphs of De Bruijn graphs; in particular, the recognition of DNA graphs is shown to be NP-hard. As a consequence, two open questions from a recent paper by B a ewicz et al. (Discrete Appl. Math. 98, (1999) 1) are answered in the negative.

KW - Recognition algorithm

KW - NP-hardness

KW - Graph Theory

KW - De Bruijn graph

KW - DNA computing

KW - DNA graphs

KW - Computational Complexity

U2 - 10.1016/S0166-218X(02)00287-1

DO - 10.1016/S0166-218X(02)00287-1

M3 - Article

SN - 0166-218X

VL - 127

SP - 85

EP - 94

JO - Discrete applied mathematics

JF - Discrete applied mathematics

IS - 1

ER -

Recognizing DNA graphs is difficult

Abstract

Keywords

Access to Document

Fingerprint

Cite this