On almost disjunct matrices for group testing

DOI10.1007/978-3-642-35261-4_67zbMATH Open1260.68289arXiv1111.5003OpenAlexW3101317493MaRDI QIDQ4909581FDOQ4909581

Authors: Arya Mazumdar 

Publication date: 21 March 2013

Published in: Algorithms and Computation (Search for Journal in Brave)

Abstract: In a emph{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 non-adaptive 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 emph{disjunct matrix}, an $MimesN$ 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 number $M$ of rows (tests). One of the main ways of constructing disjunct matrices relies on emph{constant weight error-correcting codes} and their emph{minimum distance}. In this paper, we consider a relaxed definition of a disjunct matrix known as emph{almost disjunct matrix}. This concept is also studied under the name of emph{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 emph{average distance} of a constant weight code to the parameters of an almost disjunct matrix constructed from it. Our second contribution is to explicitly construct almost disjunct matrices based on our average distance analysis, that have much smaller number of rows than any previous explicit construction of disjunct matrices. The parameters of our construction can be varied to cover a large range of relations for $t$ and $N$.

Full work available at URL: https://arxiv.org/abs/1111.5003

Recommendations

• Efficiently decodable non-adaptive group testing
• Error-correcting nonadaptive group testing with \(d^e\)-disjunct matrices
• Almost separable matrices
• Construction and properties of a class of random \(d\)-disjunct matrices
• Efficiently decodable error-correcting list disjunct matrices and applications (extended abstract)

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Combinatorics in computer science (68R05) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Other designs, configurations (05B30) Combinatorial codes (94B25)

Cited In (12)

• Rapid, large-scale, and effective detection of COVID-19 via non-adaptive testing
• Three-Dimensional Array-Based Group Testing Algorithms
• ERROR-TOLERANT TRIVIAL TWO-STAGE GROUP TESTING FOR COMPLEXES USING ALMOST SEPARABLE AND ALMOST DISJUNCT MATRICES
• Efficiently decodable error-correcting list disjunct matrices and applications (extended abstract)
• Efficiently decodable non-adaptive group testing
• Construction of \(d(H)\)\,-\,disjunct matrix for group testing in hypergraphs
• \(\varepsilon \)-almost selectors and their applications
• The design of (almost) disjunct matrices by evolutionary algorithms
• Strongly separable matrices for nonadaptive combinatorial group testing
• \(d\)-disjunct matrices: Bounds and Lovász local lemma
• An interpretable classification method for predicting drug resistance in \(M. tuberculosis\)
• Almost separable matrices

This page was built for publication: On almost disjunct matrices for group testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4909581)