De Bruijn graphs and DNA graphs

Rudi Pendavingh; Petra Schuurman; Gerhard J. Woeginger

doi:10.1007/3-540-45477-2_27

De Bruijn graphs and DNA graphs

Rudi Pendavingh, Petra Schuurman, Gerhard J. Woeginger

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Downloads (Pure)

Abstract

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; DNA graphs are the vertex induced subgraphs of De Bruijn graphs over a four letter alphabet. As a consequence, two open questions from a recent paper by Blazewicz, Hertz, Kobler & de Werra [Discrete Applied Mathematics 98, 1999] are answered in the negative.

Original language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science - 27th International Workshop, WG 2001, Proceedings
Editors	A. Brandstädt, V.B. Le
Place of Publication	Berlin
Publisher	Springer
Pages	296-305
Number of pages	10
ISBN (Print)	3540427074, 9783540427070
DOIs	https://doi.org/10.1007/3-540-45477-2_27
Publication status	Published - 1 Jan 2001
Event	27th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2001 - Boltenhagen, Germany Duration: 14 Jun 2001 → 16 Jun 2001

Publication series

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

Conference

Conference	27th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2001
Country/Territory	Germany
City	Boltenhagen
Period	14/06/01 → 16/06/01

Keywords

Computational complexity
De bruijn graph
DNA computing
DNA graphs
Graph theory
NP-hardness
Recognition algorithm

Access to Document

10.1007/3-540-45477-2_27

Cite this

Pendavingh, R., Schuurman, P., & Woeginger, G. J. (2001). De Bruijn graphs and DNA graphs. In A. Brandstädt, & V. B. Le (Eds.), Graph-Theoretic Concepts in Computer Science - 27th International Workshop, WG 2001, Proceedings (pp. 296-305). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2204). Springer. https://doi.org/10.1007/3-540-45477-2_27

Pendavingh, Rudi ; Schuurman, Petra ; Woeginger, Gerhard J. / De Bruijn graphs and DNA graphs. Graph-Theoretic Concepts in Computer Science - 27th International Workshop, WG 2001, Proceedings. editor / A. Brandstädt ; V.B. Le. Berlin : Springer, 2001. pp. 296-305 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{623f2864bf044bb18c78917ae21d82af,

title = "De Bruijn graphs and DNA graphs",

abstract = "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; DNA graphs are the vertex induced subgraphs of De Bruijn graphs over a four letter alphabet. As a consequence, two open questions from a recent paper by Blazewicz, Hertz, Kobler & de Werra [Discrete Applied Mathematics 98, 1999] are answered in the negative.",

keywords = "Computational complexity, De bruijn graph, DNA computing, DNA graphs, Graph theory, NP-hardness, Recognition algorithm",

author = "Rudi Pendavingh and Petra Schuurman and Woeginger, {Gerhard J.}",

year = "2001",

month = jan,

day = "1",

doi = "10.1007/3-540-45477-2_27",

language = "English",

isbn = "3540427074",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "296--305",

editor = "A. Brandst{\"a}dt and V.B. Le",

booktitle = "Graph-Theoretic Concepts in Computer Science - 27th International Workshop, WG 2001, Proceedings",

address = "Germany",

note = "27th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2001 ; Conference date: 14-06-2001 Through 16-06-2001",

}

Pendavingh, R, Schuurman, P & Woeginger, GJ 2001, De Bruijn graphs and DNA graphs. in A Brandstädt & VB Le (eds), Graph-Theoretic Concepts in Computer Science - 27th International Workshop, WG 2001, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2204, Springer, Berlin, pp. 296-305, 27th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2001, Boltenhagen, Germany, 14/06/01. https://doi.org/10.1007/3-540-45477-2_27

De Bruijn graphs and DNA graphs. / Pendavingh, Rudi; Schuurman, Petra; Woeginger, Gerhard J.
Graph-Theoretic Concepts in Computer Science - 27th International Workshop, WG 2001, Proceedings. ed. / A. Brandstädt; V.B. Le. Berlin: Springer, 2001. p. 296-305 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2204).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - De Bruijn graphs and DNA graphs

AU - Pendavingh, Rudi

AU - Schuurman, Petra

AU - Woeginger, Gerhard J.

PY - 2001/1/1

Y1 - 2001/1/1

N2 - 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; DNA graphs are the vertex induced subgraphs of De Bruijn graphs over a four letter alphabet. As a consequence, two open questions from a recent paper by Blazewicz, Hertz, Kobler & de Werra [Discrete Applied Mathematics 98, 1999] are answered in the negative.

AB - 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; DNA graphs are the vertex induced subgraphs of De Bruijn graphs over a four letter alphabet. As a consequence, two open questions from a recent paper by Blazewicz, Hertz, Kobler & de Werra [Discrete Applied Mathematics 98, 1999] are answered in the negative.

KW - Computational complexity

KW - De bruijn graph

KW - DNA computing

KW - DNA graphs

KW - Graph theory

KW - NP-hardness

KW - Recognition algorithm

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

U2 - 10.1007/3-540-45477-2_27

DO - 10.1007/3-540-45477-2_27

M3 - Conference contribution

SN - 3540427074

SN - 9783540427070

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

SP - 296

EP - 305

BT - Graph-Theoretic Concepts in Computer Science - 27th International Workshop, WG 2001, Proceedings

A2 - Brandstädt, A.

A2 - Le, V.B.

PB - Springer

CY - Berlin

T2 - 27th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2001

Y2 - 14 June 2001 through 16 June 2001

ER -

Pendavingh R, Schuurman P, Woeginger GJ. De Bruijn graphs and DNA graphs. In Brandstädt A, Le VB, editors, Graph-Theoretic Concepts in Computer Science - 27th International Workshop, WG 2001, Proceedings. Berlin: Springer. 2001. p. 296-305. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-45477-2_27

De Bruijn graphs and DNA graphs

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this