An information theoretic approach to improving group infection testing

ISR’s information theoretic research spans many domains, from large-scale data centers to private information retrieval to wireless communication networks. A new paper by Professor Sennur Ulukus (ECE/ISR) and her Ph.D. student Batuhan Arasli takes an information theoretic approach to improving how group infection testing is conducted during epidemics and pandemics.

“Dynamic SAFFRON: Disease Control over Time Via Group Testing” considers dynamic infection spread based on the discrete standardized infection ratio (SIR) model. SIR assumes infections are spread over time via infected and non-isolated individuals. The main objective of Ulukus and Arasli’s research is not to minimize the number of required tests to identify every infection, but instead, to utilize available, given testing capacity to efﬁciently control infection spread.

The main idea behind group testing is to pool test samples and test the pool, instead of testing each sample individually. This idea first was proposed by R. Dorfman in the classic 1943 work, “The detection of defective members of large populations” in the Annals of Mathematical Statistics. Group testing can identify the infection status of a group of individuals even though it performs fewer tests than the number of individuals in the group. When a mixed sample tests negative, this implies that every test sample included in the mixed sample is negative. If a mixed sample tests positive, it implies that there is at least one positive test sample among the mixed test sample. In group testing, the testing scheme specifies test pools so the infected set is identiﬁed with a minimum number of tests.

Over the years, various group testing algorithms have been studied. The majority of works study either a combinatorial model where the number of infections is ﬁxed and the infected set is uniformly randomly selected from all ﬁxed sized subsets of all individuals, or the probabilistic model where each individual is independently infected with a ﬁxed probability. Group testing algorithms can be divided into several categories. In adaptive group testing algorithms, tests are performed in multiple steps and test results from previous steps can be used while designing future test pools. In non-adaptive group testing algorithms all the tests are designed to be performed in a single step.

Ulukus and Arasli consider their own discrete time, SIR-based dynamic infection spread model. Here, at each time instance, the testing capacity is limited and ﬁxed, and full identiﬁcation of the infections in the system is not possible. Each discrete time instance consists of two phases: infection spread phase and testing phase. Identiﬁed infections are isolated and further infection spread by them is prevented.

Since testing capacity is limited at each time instance, not all of the infections are detected and infected individuals that are not detected and isolated keep spreading the infection. Recognizing this, the researchers chose to efﬁciently utilize the available testing capacity at each time instance. This controls disease spread within a community, instead of minimizing the number of required tests to determine every infection, as in the static group testing problem.

Ulukus and Arasli introduced and studied a new performance metric that measures how fast a given algorithm can control the spread of a disease, characterized the performance of a dynamic individual testing algorithm and introduced a new dynamic SAFFRON (Sparse-grAph codes Framework For gROup testing)-based group testing algorithm.

Their simulations showed that the steady state mean number of susceptible individuals is slightly higher in the dynamic individual testing algorithm while convergence time is slightly lower in the dynamic SAFFRON-based group testing algorithm. This suggests that both algorithms can be used to optimize different performance metrics, depending on system requirements and parameters. In addition hybrid usage of dynamic algorithms is also possible as in the researchers’ hybrid dynamic SAFFRON-based group testing algorithm implementation.

Published July 6, 2022