Small error algorithms for tropical group testing

Abstract

We consider a version of the classical group testing problem motivated by PCR testing for COVID-19. In the so-called tropical group testing model, the outcome of a test is the lowest cycle threshold (Ct) level of the individuals pooled within it, rather than a simple binary indicator variable. We introduce the tropical counterparts of three classical non-adaptive algorithms (COMP, DD and SCOMP), and analyse their behaviour through both simulations and bounds on error probabilities. By comparing the results of the tropical and classical algorithms, we gain insight into the extra information provided by learning the outcomes (Ct levels) of the tests. We show that in a limiting regime the tropical COMP algorithm requires as many tests as its classical counterpart, but that for sufficiently dense problems tropical DD can recover more information with fewer tests, and can be viewed as essentially optimal in certain regimes.

References in corpus (6)

• Group testing algorithms: bounds and simulations
• The Capacity of Adaptive Group Testing
• A Compressed Sensing Approach to Pooled RT-PCR Testing for COVID-19 Detection
• Performance of group testing algorithms with near-constant tests-per-item
• Information-theoretic and algorithmic thresholds for group testing
• The capacity of Bernoulli nonadaptive group testing