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

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

doi:10.1007/3-540-36379-3_2

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

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

Discrete Mathematics and Mathematical Programming

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

11 Citations (Scopus)

2 Downloads (Pure)

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 language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science
Subtitle of host publication	28th International Workshop, WG 2002 Český Krumlov, Czech Republic, June 13–15, 2002 Revised Papers
Editors	Gerhard Goos, Juris Hartmanis, Jan van Leeuwen, Ludek Kucera
Publisher	Springer
Pages	13-24
ISBN (Electronic)	978-3-540-36379-8
ISBN (Print)	978-3-540-00331-1
DOIs	https://doi.org/10.1007/3-540-36379-3_2
Publication status	Published - 2002
Event	28th International Workshop on Graph-Theoretic Concepts in Computer Science 2002 - Cesky Krumlov, Czech Republic Duration: 13 Jun 2002 → 15 Jun 2002 Conference number: 28

Publication series

Name	Lecture notes in computer science
Volume	2573
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	28th International Workshop on Graph-Theoretic Concepts in Computer Science 2002
Abbreviated title	WG 2002
Country/Territory	Czech Republic
City	Cesky Krumlov
Period	13/06/02 → 15/06/02

Keywords

METIS-208662

Access to Document

10.1007/3-540-36379-3_2

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

Blazewicz, J. ; Formanowicz, P. ; Kasprzak, M. et al. / DNA sequencing, Eulerian graphs, and the exact perfect matching problem. Graph-Theoretic Concepts in Computer Science: 28th International Workshop, WG 2002 Český Krumlov, Czech Republic, June 13–15, 2002 Revised Papers. editor / Gerhard Goos ; Juris Hartmanis ; Jan van Leeuwen ; Ludek Kucera. Springer, 2002. pp. 13-24 (Lecture notes in computer science).

@inproceedings{b070611c524d41cf8c4d62d8b5a4d0b7,

title = "DNA sequencing, Eulerian graphs, and the exact perfect matching problem",

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.",

keywords = "METIS-208662",

author = "J. Blazewicz and P. Formanowicz and M. Kasprzak and P. Schuurman and Gerhard Woeginger",

year = "2002",

doi = "10.1007/3-540-36379-3_2",

language = "English",

isbn = "978-3-540-00331-1",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "13--24",

editor = "Gerhard Goos and Juris Hartmanis and {van Leeuwen}, Jan and Ludek Kucera",

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

note = "28th International Workshop on Graph-Theoretic Concepts in Computer Science 2002, WG 2002 ; Conference date: 13-06-2002 Through 15-06-2002",

}

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. Lecture notes in computer science, vol. 2573, Springer, pp. 13-24, 28th International Workshop on Graph-Theoretic Concepts in Computer Science 2002, Cesky Krumlov, Czech Republic, 13/06/02. https://doi.org/10.1007/3-540-36379-3_2

DNA sequencing, Eulerian graphs, and the exact perfect matching problem. / Blazewicz, J.; Formanowicz, P.; Kasprzak, M. et al.
Graph-Theoretic Concepts in Computer Science: 28th International Workshop, WG 2002 Český Krumlov, Czech Republic, June 13–15, 2002 Revised Papers. ed. / Gerhard Goos; Juris Hartmanis; Jan van Leeuwen; Ludek Kucera. Springer, 2002. p. 13-24 (Lecture notes in computer science; Vol. 2573).

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

TY - GEN

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

AU - Blazewicz, J.

AU - Formanowicz, P.

AU - Kasprzak, M.

AU - Schuurman, P.

AU - Woeginger, Gerhard

N1 - Conference code: 28

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

KW - METIS-208662

U2 - 10.1007/3-540-36379-3_2

DO - 10.1007/3-540-36379-3_2

M3 - Conference contribution

SN - 978-3-540-00331-1

T3 - Lecture notes in computer science

SP - 13

EP - 24

BT - Graph-Theoretic Concepts in Computer Science

A2 - Goos, Gerhard

A2 - Hartmanis, Juris

A2 - van Leeuwen, Jan

A2 - Kucera, Ludek

PB - Springer

T2 - 28th International Workshop on Graph-Theoretic Concepts in Computer Science 2002

Y2 - 13 June 2002 through 15 June 2002

ER -

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

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

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this