DNA sequencing, Eulerian graphs, and the exact perfect matching problem

J. Blazewicz, P. Formanowicz, M. Kasprzak, P. Schuurman, Gerhard Woeginger

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

9 Citations (Scopus)

Abstract

We investigate the computational complexity of a combinatorial problem that arises in DNA sequencing by hybridization: The input consists of an integer l together with a set S of words of length k over the four symbols A, C, G, T. The problem is to decide whether there exists a word of length l that contains every word in S at least once as a subword, and does not contain any other subword of length k. The computational complexity of this problem has been open for some time, and it remains open. What we prove is that this problem is polynomial time equivalent to the exact perfect matching problem in bipartite graphs, which is another infamous combinatorial optimization problem of unknown computational complexity.
Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science
Subtitle of host publication28th International Workshop, WG 2002 Český Krumlov, Czech Republic, June 13–15, 2002 Revised Papers
EditorsGerhard Goos, Juris Hartmanis, Jan van Leeuwen, Ludek Kucera
PublisherSpringer
Pages13-24
ISBN (Electronic)978-3-540-36379-8
ISBN (Print)978-3-540-00331-1
DOIs
Publication statusPublished - 2002
Event28th International Workshop on Graph-Theoretic Concepts in Computer Science 2002 - Cesky Krumlov, Czech Republic
Duration: 13 Jun 200215 Jun 2002
Conference number: 28

Publication series

NameLecture notes in computer science
Volume2573
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference28th International Workshop on Graph-Theoretic Concepts in Computer Science 2002
Abbreviated titleWG 2002
CountryCzech Republic
CityCesky Krumlov
Period13/06/0215/06/02

Keywords

  • METIS-208662

Fingerprint Dive into the research topics of 'DNA sequencing, Eulerian graphs, and the exact perfect matching problem'. Together they form a unique fingerprint.

  • Cite this

    Blazewicz, J., Formanowicz, P., Kasprzak, M., Schuurman, P., & Woeginger, G. (2002). DNA sequencing, Eulerian graphs, and the exact perfect matching problem. In G. Goos, J. Hartmanis, J. van Leeuwen, & L. Kucera (Eds.), Graph-Theoretic Concepts in Computer Science: 28th International Workshop, WG 2002 Český Krumlov, Czech Republic, June 13–15, 2002 Revised Papers (pp. 13-24). (Lecture notes in computer science; Vol. 2573). Springer. https://doi.org/10.1007/3-540-36379-3_2