De Bruijn graphs and DNA graphs

Rudi Pendavingh; Petra Schuurman; Gerhard Woeginger

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

De Bruijn graphs and DNA graphs

Rudi Pendavingh, Petra Schuurman, Gerhard Woeginger

Discrete Mathematics and Mathematical Programming

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

10 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 Błażewicz, 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
Subtitle of host publication	27th International Workshop, WG 2001 Boltenhagen, Germany, June 14–16, 2001 Proceedings
Editors	Andreas Brandstädt, Van Bang Le
Publisher	Springer
Pages	296-305
ISBN (Electronic)	978-3-540-45477-9
ISBN (Print)	978-3-540-42707-0
DOIs	https://doi.org/10.1007/3-540-45477-2_27
Publication status	Published - 2001
Event	27th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2001 - Boltenhagen, Germany Duration: 14 Jun 2001 → 16 Jun 2001 Conference number: 27

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	2204
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

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

Keywords

METIS-203193

Access to Document

10.1007/3-540-45477-2_27

Cite this

Pendavingh, R., Schuurman, P., & Woeginger, G. (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 Boltenhagen, Germany, June 14–16, 2001 Proceedings (pp. 296-305). (Lecture Notes in Computer Science; Vol. 2204). Springer. https://doi.org/10.1007/3-540-45477-2_27

@inproceedings{4b9d60ac672a4042b2091ec7d840a530,

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 B{\l}a{\.z}ewicz, Hertz, Kobler \& de Werra [Discrete Applied Mathematics 98, 1999] are answered in the negative.",

keywords = "METIS-203193",

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

year = "2001",

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

language = "English",

isbn = "978-3-540-42707-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "296--305",

editor = "Andreas Brandst{\"a}dt and Le, \{Van Bang\}",

booktitle = "Graph-Theoretic Concepts in Computer Science",

address = "Germany",

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

}

Pendavingh, R, Schuurman, P & Woeginger, G 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 Boltenhagen, Germany, June 14–16, 2001 Proceedings. Lecture Notes in Computer Science, vol. 2204, Springer, 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.
Graph-Theoretic Concepts in Computer Science: 27th International Workshop, WG 2001 Boltenhagen, Germany, June 14–16, 2001 Proceedings. ed. / Andreas Brandstädt; Van Bang Le. Springer, 2001. p. 296-305 (Lecture Notes in Computer Science; 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

N1 - Conference code: 27

PY - 2001

Y1 - 2001

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 Błażewicz, 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 Błażewicz, Hertz, Kobler & de Werra [Discrete Applied Mathematics 98, 1999] are answered in the negative.

KW - METIS-203193

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

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

M3 - Conference contribution

SN - 978-3-540-42707-0

T3 - Lecture Notes in Computer Science

SP - 296

EP - 305

BT - Graph-Theoretic Concepts in Computer Science

A2 - Brandstädt, Andreas

A2 - Le, Van Bang

PB - Springer

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

Y2 - 14 June 2001 through 16 June 2001

ER -

De Bruijn graphs and DNA graphs

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this