J. Blazewicz, P. Formanowicz, M. Kasprzak, P. Schuurman, G.J. Woeginger,
"A polynomial time equivalence between DNA sequencing and the exact perfect matching problem",
Discrete Optimization 4 (2007) 154-162.
Download full text
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.
Back to the List of publications
25 Apr 2007