A polynomial time equivalence between DNA sequencing and the exact perfect matching problem

We investigate the computational complexity of a combinatorial problem that arises in DNA sequencing by hybridization: The input consists of an integer ℓℓ together with a set SS of words of length kk over the four symbols AA, CC, GG, TT. The problem is to decide whether there exists a word of length ℓℓ that contains every word in SS at least once as a subword, and does not contain any other subword of length kk.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.