The original problem of group testing consists in the identification of defective items in a collection, by applying tests on groups of items that detect the presence of at least one defective element in the group. The aim is then to identify all defective items of the collection with as few tests as possible. This problem is relevant in several fields, among which biology and computer sciences. In the present article we consider that the tests applied to groups of items returns a load, measuring how defective the most defective item of the group is. In this setting, we propose a simple non-adaptative algorithm allowing the detection of all defective items of the collection. Items are put on an n × n grid and pools are organised as lines, columns and diagonals of this grid. This method improves on classical group testing algorithms using only the binary response of the test. Group testing recently gained attraction as a potential tool to solve a shortage of COVID-19 test kits, in particular for RT-qPCR. These tests return the viral load of the sample and the viral load varies greatly among individuals. Therefore our model presents some of the key features of this problem. We aim at using the extra piece of information that represents the viral load to construct a one-stage pool testing algorithm on this idealized version. We show that under the right conditions, the total number of tests needed to detect contaminated samples can be drastically diminished.
Keywords: Group testing, one-stage algorithm, non-adaptative group testing, algorithm design and analysis, non binary test
@article{PS_2022__26_1_283_0,
author = {Joly, \'Emilien and Mallein, Bastien},
title = {A tractable non-adaptative group testing method for non-binary measurements},
journal = {ESAIM: Probability and Statistics},
pages = {283--303},
year = {2022},
publisher = {EDP-Sciences},
volume = {26},
doi = {10.1051/ps/2022007},
mrnumber = {4440012},
zbl = {1493.62022},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ps/2022007/}
}
TY - JOUR AU - Joly, Émilien AU - Mallein, Bastien TI - A tractable non-adaptative group testing method for non-binary measurements JO - ESAIM: Probability and Statistics PY - 2022 SP - 283 EP - 303 VL - 26 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ps/2022007/ DO - 10.1051/ps/2022007 LA - en ID - PS_2022__26_1_283_0 ER -
%0 Journal Article %A Joly, Émilien %A Mallein, Bastien %T A tractable non-adaptative group testing method for non-binary measurements %J ESAIM: Probability and Statistics %D 2022 %P 283-303 %V 26 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ps/2022007/ %R 10.1051/ps/2022007 %G en %F PS_2022__26_1_283_0
Joly, Émilien; Mallein, Bastien. A tractable non-adaptative group testing method for non-binary measurements. ESAIM: Probability and Statistics, Tome 26 (2022), pp. 283-303. doi: 10.1051/ps/2022007
[1] , and , Group testing: an information theory perspective. Found. Trends Commun. Inf. Theory 15 (2019) 196–392. | Zbl | DOI
[2] , and , Optimal risk-based group testing. Manag. Sci. 65 (2019) 4365–4384. | DOI
[3] , , , , , , , , , , , , , , , and , Large-scale implementation of pooled RNA-extraction and RT-PCR for SARS-CoV-2 detection. Preprint medRxiv (2020).
[4] , , , , , , and , Optimal Covid-19 Pool Testing with a priori Information. Preprint (2020). | arXiv
[5] , and , Group testing as a strategy for the epidemiologic monitoring of COVID-19. Preprint (2020). | arXiv
[6] , , , , , , , and , Pooling for SARS-COV-2 control in care institutions. Preprint medRxiv (2020). | DOI
[7] , , and , Efficient algorithms for noisy group testing. IEEE Trans. Inf. Theory 63 (2017) 2113–2136. | MR | Zbl | DOI
[8] , , , and , Pooling, lattice square, and union jack designs. Ann. Combinat. 3 (1999) 27–35. | MR | Zbl | DOI
[9] , The detection of defective members of large populations. Ann. Math. Stat. 14 (1943) 436–440. | DOI
[10] and , Combinatorial group testing and its applications. 2nd ed. World Scientific, Singapore 2nd ed. (2000). | MR | Zbl
[11] and , Code construction and decoding algorithms for semi-quantitative group testing with nonuniform thresholds. IEEE Trans. Inf. Theory 62 (2016) 1674–1687. | MR | Zbl | DOI
[12] , , , , , , and , Saving resources: Avian influenza surveillance using pooled swab samples and reduced reaction volumes in real-time RT-PCR. J. Virolog. Methods 186 (2012) 119–125. | DOI
[13] , The illusion of group testing. Research Report RR-9164, Inria Rennes Bretagne Atlantique (2018).
[14] , , , , , , , , , , , , , , , , , , , , , , , , , and , Tapestry: a single-round smart pooling technique for COVID-19 testing. Preprint medRxiv (2020). | DOI
[15] and , Group testing against Covid-19. Covid Econ. 2 (2020) 32–42.
[16] , and , Sample pooling as a strategy to detect community transmission of SARS-CoV-2. JAMA 323 (2020) 1967. | DOI
[17] and , Group testing to identify one defective and one mediocre item. J. Stat. Plann. Inference 17 (1987) 367–373. | MR | Zbl | DOI
[18] , , and , On the Optimality of the Kautz-Singleton Construction in Probabilistic Group Testing (2018). | MR
[19] , , , , , , , , and , An analysis of SARS-CoV-2 viral load by patient age. Preprint medRxiv (2020).
[20] , and , Sample pooling as a strategy to detect community transmission of SARS-CoV-2. N. Engl. J. Med. 382 (2020) 1194–1196.
[21] , , , , , , , and , Pooling of samples for testing for SARS-CoV-2 in asymptomatic people. Lancet Infect. Diseases 3099 (2020) 1231–1232. | DOI
[22] and , Group testing with random pools: optimal two-stage algorithms. IEEE Trans. Inf. Theory 57 (2011) 1736–1745. | MR | Zbl | DOI
[23] , and , Group testing with random pools: Phase transitions and optimal strategy. J. Stat. Phys. 131 (2008) 783–801. | MR | Zbl | DOI
[24] , , , , , , , , , , , , , , , , , , and , A strategy for finding people infected with SARS-CoV-2: optimizing pooled testing at low prevalence. Preprint arXiv (2020). DOI: | DOI
[25] , , and , Efficient and practical sample pooling for high-throughput PCR diagnosis of COVID-19. Preprint medRxiv (2020). | DOI
[26] , and , Evaluation of group testing for SARS-CoV-2 RNA. Preprint medRxiv (2020). | DOI
[27] , Rapid, large-scale, and effective detection of COVID-19 via non-adaptive testing. J. Theor. Biol. 506 (2020) 110450. | MR | Zbl | DOI
[28] , Pooling in systems biology becomes smart. Nat. Methods 3 (2006) 161–162. | DOI
[29] , Estimation of the proportion of vectors in a natural population of insects. Biometrics 18 (1962) 568. | DOI
[30] , and , Pooling of nasopharyngeal swab specimens for SARS-CoV-2 detection by RT-PCR. J. Med. Virol. (2020) 25971.
Cité par Sources :
CNRS MODCOV-19 plateform.
