On the complexity and approximation of non-unique probe selection using d-disjunct matrix

My T. Thai, Taieb Znati

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

In this paper, we studied the MINimum-d-Disjunct Submatrix (MIN-d-DS), which can be used to select the minimum number of non-unique probes for viruses identification. We prove that MIN-d-DS is NP-hard for any fixed d. Using d-disjunct matrix, we present an O(logk)-approximation algorithm where k is an upper bound on the maximum number of targets hybridized to a probe. We also present a (1+(d+1)logn)-approximation algorithm to identify at most d targets in the presence of experimental errors. Our approximation algorithms also yield a linear time complexity for the decoding algorithms.

Original languageEnglish
Pages (from-to)45-53
Number of pages9
JournalJournal of Combinatorial Optimization
Volume17
Issue number1
DOIs
Publication statusPublished - Jan 2009
Externally publishedYes

Keywords

  • Non-adaptive group testing
  • Non-unique probe
  • Pooling designs
  • d-disjunct matrix

ASJC Scopus subject areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'On the complexity and approximation of non-unique probe selection using d-disjunct matrix'. Together they form a unique fingerprint.

Cite this