On almost disjunct matrices for group testing

Arya Mazumdar

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

15 Scopus citations

Abstract

In a group testing scheme, a set of tests is designed to identify a small number t of defective items among a large set (of size N) of items. In the nonadaptive scenario the set of tests has to be designed in one-shot. In this setting, designing a testing scheme is equivalent to the construction of a disjunct matrix, an MxN matrix where the union of supports of any t columns does not contain the support of any other column. In principle, one wants to have such a matrix with minimum possible numberM of rows (tests). One of the main ways of constructing disjunct matrices relies on constant weight error-correcting codes and their minimum distance. In this paper, we consider a relaxed definition of a disjunct matrix known as almost disjunct matrix. This concept is also studied under the name of weakly separated design in the literature. The relaxed definition allows one to come up with group testing schemes where a close-to-one fraction of all possible sets of defective items are identifiable. Our main contribution is twofold. First, we go beyond the minimum distance analysis and connect the average distance of a constant weight code to the parameters of an almost disjunct matrix constructed from it. Next we show as a consequence an explicit construction of almost disjunct matrices based on our average distance analysis. The parameters of our construction can be varied to cover a large range of relations for t and N. As an example of parameters, consider any absolute constant ε < 0 and t proportional to Nδ, δ > 0.With our method it is possible to explicitly construct a group testing scheme that identifies (1 - ε) proportion of all possible defective sets of size t using only O(t3/2√log(N/ ε)) tests (as opposed to O(t2 logN) required to identify all defective sets).

Original languageEnglish (US)
Title of host publicationAlgorithms and Computation - 23rd International Symposium, ISAAC 2012, Proceedings
PublisherSpringer Verlag
Pages649-658
Number of pages10
ISBN (Print)9783642352607
DOIs
StatePublished - 2012
Event23rd International Symposium on Algorithms and Computation, ISAAC 2012 - Taipei, Taiwan, Province of China
Duration: Dec 19 2012Dec 21 2012

Publication series

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

Other

Other23rd International Symposium on Algorithms and Computation, ISAAC 2012
CountryTaiwan, Province of China
CityTaipei
Period12/19/1212/21/12

Fingerprint Dive into the research topics of 'On almost disjunct matrices for group testing'. Together they form a unique fingerprint.

Cite this