Abstract

We propose a novel group testing method, termed semiquantitative group testing (SQGT), motivated by a class of problems arising in genome screening experiments. The SQGT is a (possibly) nonbinary pooling scheme that may be viewed as a concatenation of an adder channel and an integer-valued quantizer. In its full generality, SQGT may be viewed as a unifying framework for group testing, in the sense that most group testing models are special instances of SQGT. For the new testing scheme, we define the notion of SQ-disjunct and SQ-separable codes, representing generalizations of classical disjunct and separable codes. We describe several combinatorial and probabilistic constructions for such codes. While for most of these constructions, we assume that the number of defectives is much smaller than total number of test subjects, we also consider the case in which there is no restriction on the number of defectives and they may be as large as the total number of subjects. For the codes constructed in this paper, we describe a number of efficient decoding algorithms. In addition, we describe a belief propagation decoder for sparse SQGT codes for which no other efficient decoder is currently known.

Original languageEnglish (US)
Article number6823721
Pages (from-to)4614-4636
Number of pages23
JournalIEEE Transactions on Information Theory
Volume60
Issue number8
DOIs
StatePublished - Aug 2014

Keywords

  • Belief propagation decoders
  • disjunct and separable codes
  • group testing
  • integer compressed sensing
  • sparse models

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Fingerprint Dive into the research topics of 'Semiquantitative group testing'. Together they form a unique fingerprint.

  • Cite this