On almost disjunct matrices for group testing

DOI10.1007/978-3-642-35261-4_67MaRDI QIDQ4909581zbMATH OpenOpenAlexFDO

Authors Arya Mazumdar

Publication date 21 March 2013

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

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

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)

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$.

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)

Cited in

(12)

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