The approximability of the String Barcoding problem
2006
Understanding the String Barcoding Problem
publication
Evidence: high
Author Information
Author(s): Giuseppe Lancia, Romeo Rizzi
Primary Institution: Dipartimento di Matematica ed Informatica, Universitá di Udine, Italy
Hypothesis
The String Barcoding problem is as hard to approximate as the Set Cover problem.
Conclusion
The study demonstrates that both the unconstrained and constrained versions of the String Barcoding problem are NP-complete.
Supporting Evidence
- The String Barcoding problem is linked to the Set Cover problem, establishing its NP-completeness.
- The constrained version of the String Barcoding problem is also shown to be hard to approximate.
- Results indicate that the problem remains complex even with binary alphabets.
Takeaway
This study shows that finding the best way to identify viruses using short DNA sequences is really hard, just like solving a tricky puzzle.
Methodology
The authors linked the approximability of the String Barcoding problem to the classical Set Cover problem and provided reductions to show NP-completeness.
Digital Object Identifier (DOI)
Want to read the original?
Access the complete publication on the publisher's website