Faster algorithm for the set variant of the string barcoding problem

Leszek Ga̧sieniec, Cindy Y. Li, Meng Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution


A string barcoding problem is defined as to find a minimum set of substrings that distinguish between all strings in a given set of strings . In a biological sense the given strings represent a set of genomic sequences and the substrings serve as probes in a hybridisation experiment. In this paper, we study a variant of the string barcoding problem in which the substrings have to be chosen from a particular set of substrings of cardinality n. This variant can be also obtained from more general test set problem, see, e.g., [1] by fixing appropriate parameters. We present almost optimal -time approximation algorithm for the considered problem. Our approximation procedure is a modification of the algorithm due to Berman et al. [1] which obtains the best possible approximation ratio (1∈+∈ln n), providing . The improved time complexity is a direct consequence of more careful management of processed sets, use of several specialised graph and string data structures as well as tighter time complexity analysis based on an amortised argument.

Original languageEnglish (US)
Title of host publicationCombinatorial Pattern Matching - 19th Annual Symposium, CPM 2008, Proceedings
Number of pages13
StatePublished - Jul 1 2008
Externally publishedYes
Event19th Annual Symposium on Combinatorial Pattern Matching, CPM 2008 - Pisa, Italy
Duration: Jun 18 2008Jun 20 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5029 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference19th Annual Symposium on Combinatorial Pattern Matching, CPM 2008

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Faster algorithm for the set variant of the string barcoding problem'. Together they form a unique fingerprint.

Cite this