The String Barcoding Problem is NP-Hard

The String Barcoding (SBC) problem, introduced by Rash and Gusfield (RECOMB, 2002), consists in finding a minimum set of substrings that can be used to distinguish between all members of a set of given strings. In a computational biology context, the given strings represent a set of known viruses, while the substrings can be used as probes for an hybridization experiment via microarray. Eventually, one aims at the classification of new strings (unknown viruses) through the result of the hybridization experiment. Rash and Gusfield utilized an Integer Programming approach for the solution of SBC, but they left the computational complexity of the problem as an open question. In this paper we settle the question and prove that SBC is NP-hard.

Authors and Affiliations

1. Dipartimento di Ingegneria dell’Informazione, University of Padova,  

   Marcello Dalpasso

2. Dipartimento di Matematica ed Informatica, University of Udine,  

   Giuseppe Lancia

3. Dipartimento di Informatica e Telecomunicazioni, University of Trento,  

   Romeo Rizzi

Editors and Affiliations

1. University of Dublin, Smurfit Institute of Genetics, Trinity College, Ireland

   Aoife McLysaght

2. Center for Bioinformatics ZBIT, Tübingen University, Sand 14, 72076, Tübingen, Germany

   Daniel H. Huson

Reprints and permissions

© 2005 Springer-Verlag Berlin Heidelberg

Policies and ethics