De Bruijn graphs and DNA graphs

Rudi Pendavingh, Petra Schuurman, Gerhard Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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 languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science
Subtitle of host publication27th International Workshop, WG 2001 Boltenhagen, Germany, June 14–16, 2001 Proceedings
EditorsAndreas Brandstädt, Van Bang Le
PublisherSpringer
Pages296-305
ISBN (Electronic)978-3-540-45477-9
ISBN (Print)978-3-540-42707-0
DOIs
Publication statusPublished - 2001
Event27th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2001 - Boltenhagen, Germany
Duration: 14 Jun 200116 Jun 2001
Conference number: 27

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume2204
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference27th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2001
Abbreviated titleWG
CountryGermany
CityBoltenhagen
Period14/06/0116/06/01

Keywords

  • METIS-203193

Fingerprint Dive into the research topics of 'De Bruijn graphs and DNA graphs'. Together they form a unique fingerprint.

  • 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