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, G.J.

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.

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

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

M3 - Conference contribution

T3 - Lecture Notes in Computer Science

SP - 13

EP - 24

BT - Proceedings of the 28th Workshop on Graph-Theoretic Concepts in Computer Science (WG'02, Cseky Krumlov, Czech Republic, June 13-15, 2002)

PB - Springer

CY - Berlin

ER -