The String Barcoding Problem is NP-Hard

  • Marcello Dalpasso
  • Giuseppe Lancia
  • Romeo Rizzi
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3678)


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.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. MIT Press, Cambridge (2001)zbMATHGoogle Scholar
  2. 2.
    Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co, New York (1979)zbMATHGoogle Scholar
  3. 3.
    Karp, R.M.: Reducibility among combinatorial problems. Complexity and Computer Computations (1972)Google Scholar
  4. 4.
    Rash, S., Gusfield, D.: String Barcoding: Uncovering Optimal Virus Signatures. In: Proceedings of the Annual International Conference on Computational Molecular Biology (RECOMB). ACM Press, New York (2002)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Marcello Dalpasso
    • 1
  • Giuseppe Lancia
    • 2
  • Romeo Rizzi
    • 3
  1. 1.Dipartimento di Ingegneria dell’InformazioneUniversity of Padova 
  2. 2.Dipartimento di Matematica ed InformaticaUniversity of Udine 
  3. 3.Dipartimento di Informatica e TelecomunicazioniUniversity of Trento 

Personalised recommendations