In statistics and combinatorial mathematics, group testing is any procedure that breaks up the task of identifying certain objects into tests on groups of items, rather than on individual ones. First studied by Robert Dorfman in 1943, group testing is a relatively new field of applied mathematics that can be applied to a wide range of practical applications and is an active area of research today.
A familiar example of group testing involves a string of light bulbs connected in series, where exactly one of the bulbs is known to be broken. The objective is to find the broken bulb using the smallest number of tests (where a test is when some of the bulbs are connected to a power supply). A simple approach is to test each bulb individually. However, when there are a large number of bulbs it would be much more efficient to pool the bulbs into groups. For example, by connecting the first half of the bulbs at once, it can be determined which half the broken bulb is in, ruling out half of the bulbs in just one test.
Schemes for carrying out group testing can be simple or complex and the tests involved at each stage may be different. Schemes in which the tests for the next stage depend on the results of the previous stages are called adaptive procedures, while schemes designed so that all the tests are known beforehand are called non-adaptive procedures. The structure of the scheme of the tests involved in a non-adaptive procedure is known as a pooling design.
Group testing has many applications, including statistics, biology, computer science, medicine, engineering and cyber security. Modern interest in these testing schemes has been rekindled by the Human Genome Project.
Unlike many areas of mathematics, the origins of group testing can be traced back to a single report written by a single person: Robert Dorfman. The motivation arose during the Second World War when the United States Public Health Service and the Selective service embarked upon a large-scale project to weed out all syphilitic men called up for induction. Testing an individual for syphilis involves drawing a blood sample from them and then analysing the sample to determine the presence or absence of syphilis. At the time, performing this test was expensive, and testing every soldier individually would have been very expensive and inefficient.
Supposing there are
n
n
The items that cause a group to test positive are generally called defective items (these are the broken lightbulbs, syphilitic men, etc.). Often, the total number of items is denoted as
n
d
There are two independent classifications for group-testing problems; every group-testing problem is either adaptive or non-adaptive, and either probabilistic or combinatorial.
In probabilistic models, the defective items are assumed to follow some probability distribution and the aim is to minimise the expected number of tests needed to identify the defectiveness of every item. On the other hand, with combinatorial group testing, the goal is to minimise the number of tests needed in a 'worst-case scenario' – that is, create a minmax algorithm – and no knowledge of the distribution of defectives is assumed.
The other classification, adaptivity, concerns what information can be used when choosing which items to group into a test. In general, the choice of which items to test can depend on the results of previous tests, as in the above lightbulb problem. An algorithm that proceeds by performing a test, and then using the result (and all past results) to decide which next test to perform, is called adaptive. Conversely, in non-adaptive algorithms, all tests are decided in advance. This idea can be generalised to multistage algorithms, where tests are divided into stages, and every test in the next stage must be decided in advance, with only the knowledge of the results of tests in previous stages.Although adaptive algorithms offer much more freedom in design, it is known that adaptive group-testing algorithms do not improve upon non-adaptive ones by more than a constant factor in the number of tests required to identify the set of defective items.[1] [2] In addition to this, non-adaptive methods are often useful in practice because one can proceed with successive tests without first analysing the results of all previous tests, allowing for the effective distribution of the testing process.
There are many ways to extend the problem of group testing. One of the most important is called noisy group testing, and deals with a big assumption of the original problem: that testing is error-free. A group-testing problem is called noisy when there is some chance that the result of a group test is erroneous (e.g. comes out positive when the test contained no defectives). The Bernoulli noise model assumes this probability is some constant,
q
Group testing can be extended by considering scenarios in which there are more than two possible outcomes of a test. For example, a test may have the outcomes
0,1
2+
{0,1,\ldots,k+}
k\inN
Another extension is to consider geometric restrictions on which sets can be tested. The above lightbulb problem is an example of this kind of restriction: only bulbs that appear consecutively can be tested. Similarly, the items may be arranged in a circle, or in general, a net, where the tests are available paths on the graph. Another kind of geometric restriction would be on the maximum number of items that can be tested in a group, or the group sizes might have to be even and so on. In a similar way, it may be useful to consider the restriction that any given item can only appear in a certain number of tests.[2]
There are endless ways to continue remixing the basic formula of group testing. The following elaborations will give an idea of some of the more exotic variants. In the 'good–mediocre–bad' model, each item is one of 'good', 'mediocre' or 'bad', and the result of a test is the type of the 'worst' item in the group. In threshold group testing, the result of a test is positive if the number of defective items in the group is greater than some threshold value or proportion.[4] Group testing with inhibitors is a variant with applications in molecular biology. Here, there is a third class of items called inhibitors, and the result of a test is positive if it contains at least one defective and no inhibitors.[5]
The concept of group testing was first introduced by Robert Dorfman in 1943 in a short report published in the Notes section of Annals of Mathematical Statistics.[2] Dorfman's report – as with all the early work on group testing – focused on the probabilistic problem, and aimed to use the novel idea of group testing to reduce the expected number of tests needed to weed out all syphilitic men in a given pool of soldiers. The method was simple: put the soldiers into groups of a given size, and use individual testing (testing items in groups of size one) on the positive groups to find which were infected. Dorfman tabulated the optimum group sizes for this strategy against the prevalence rate of defectiveness in the population.Stephen Samuels[6] found a closed-form solution for the optimal group size as a function of the prevalence rate.
After 1943, group testing remained largely untouched for a number of years. Then in 1957, Sterrett produced an improvement on Dorfman's procedure.[7] This newer process starts by again performing individual testing on the positive groups, but stopping as soon as a defective is identified. Then, the remaining items in the group are tested together, since it is very likely that none of them are defective.
The first thorough treatment of group testing was given by Sobel and Groll in their formative 1959 paper on the subject.[8] They described five new procedures – in addition to generalisations for when the prevalence rate is unknown – and for the optimal one, they provided an explicit formula for the expected number of tests it would use. The paper also made the connection between group testing and information theory for the first time, as well as discussing several generalisations of the group-testing problem and providing some new applications of the theory.
The fundamental result by Peter Ungar in 1960 shows that if the prevalence rate
p>pu=(3-\sqrt{5})/2 ≈ 0.38
p<pu
p<pu
n>2
Group testing was first studied in the combinatorial context by Li in 1962,[10] with the introduction of Li’s
s
t=
| e | |
| log2(e) |
dlog2(n)
d
n
s-1
Combinatorial group testing in general was later studied more fully by Katona in 1973.[11] Katona introduced the matrix representation of non-adaptive group-testing and produced a procedure for finding the defective in the non-adaptive 1-defective case in no more than
t=\lceillog2(n)\rceil
In general, finding optimal algorithms for adaptive combinatorial group testing is difficult, and although the computational complexity of group testing has not been determined, it is suspected to be hard in some complexity class.[2] However, an important breakthrough occurred in 1972, with the introduction of the generalised binary-splitting algorithm. The generalised binary-splitting algorithm works by performing a binary search on groups that test positive, and is a simple algorithm that finds a single defective in no more than the information-lower-bound number of tests.
In scenarios where there are two or more defectives, the generalised binary-splitting algorithm still produces near-optimal results, requiring at most
d-1
d
0.187d+0.5log2(d)+5.5
n/d\geq38
d\geq10
There is an open question as to when individual testing is minmax. Hu, Hwang and Wang showed in 1981 that individual testing is minmax when
n\leq\lfloor(5d+1)/2\rfloor
n>3d
n\leq3d
n
d\geqn/log3/2(3) ≈ 0.369n
One of the key insights in non-adaptive group testing is that significant gains can be made by eliminating the requirement that the group-testing procedure be certain to succeed (the "combinatorial" problem), but rather permit it to have some low but non-zero probability of mis-labelling each item (the "probabilistic" problem). It is known that as the number of defective items approaches the total number of items, exact combinatorial solutions require significantly more tests than probabilistic solutions — even probabilistic solutions permitting only an asymptotically small probability of error.[1]
In this vein, Chan et al. (2011) introduced COMP, a probabilistic algorithm that requires no more than
t=ed(1+\delta)ln(n)
d
n
n-\delta
t=O(dlog2n)
Chan et al. (2011) also provided a generalisation of COMP to a simple noisy model, and similarly produced an explicit performance bound, which was again only a constant (dependent on the likelihood of a failed test) above the corresponding lower bound.[1] In general, the number of tests required in the Bernoulli noise case is a constant factor larger than in the noiseless case.
Aldridge, Baldassini and Johnson (2014) produced an extension of the COMP algorithm that added additional post-processing steps. They showed that the performance of this new algorithm, called DD, strictly exceeds that of COMP, and that DD is 'essentially optimal' in scenarios where
d2\geqn
d2<n
This section formally defines the notions and terms relating to group testing.
x=(x1,x2,...,xn)
n
x\in\{0,1\}n
xj=1
x
x
x
x
S\subseteq\{1,2,...,n\}
j\inS
xj=1
Therefore, the goal of group testing is to come up with a method for choosing a 'short' series of tests that allow
x
t(d,n)
d
n
\bar{t}(d,n)
Since it is always possible to resort to individual testing by setting
Sj=\{j\}
1\leqj\leqn
\bar{t}(d,n)\leqn
t(d,n)\leq\bar{t}(d,n)
0 ≠ d ≠ n
1\leqt(d,n)
In summary (when assuming
0 ≠ d ≠ n
1\leqt(d,n)\leq\bar{t}(d,n)\leqn
A lower bound on the number of tests needed can be described using the notion of sample space, denoted
l{S}
l{S}
t\geq\lceillog2{|l{S}|}\rceil
t
l{S}
However, the information lower bound itself is usually unachievable, even for small problems.[2] This is because the splitting of
l{S}
In fact, the information lower bound can be generalised to the case where there is a non-zero probability that the algorithm makes an error. In this form, the theorem gives us an upper bound on the probability of success based on the number of tests. For any group-testing algorithm that performs
t
P(rm{success})
P(rm{success})\leqt/log2{n\choosed}
P(rm{success})\leq
| 2t | |
| {n\choosed |
Algorithms for non-adaptive group testing consist of two distinct phases. First, it is decided how many tests to perform and which items to include in each test. In the second phase, often called the decoding step, the results of each group test are analysed to determine which items are likely to be defective. The first phase is usually encoded in a matrix as follows.
n
S1,S2,...,St
t\inN\geq
t x n
M
(M)ij=1
j\inSi
Thus each column of
M
1
(i,j)rm{-th}
irm{-th}
jrm{-th}
0
As well as the vector
x
n
t
y=(y1,y2,...,yt)
t
y\in\{0,1\}t
yi=1
irm{-th}
With these definitions, the non-adaptive problem can be reframed as follows: first a testing matrix is chosen,
M
y
y
x
In the simplest noisy case, where there is a constant probability,
q
v
q
1
0
\hat{y
(Z/2Z)n
x
\hat{y
y
The matrix representation makes it possible to prove some bounds on non-adaptive group testing. The approach mirrors that of many deterministic designs, where
d
M
d
d
\bar{d}
d
M
M
k
k\leqd
When
M
d
\bar{d}
d
M
d
d
A useful property of
d
d
Using the properties of
d
d
d
n
O(dlog2n)
O(d2log2n)
O\left(
| d2log2n | |
| log2d |
\right)
The generalised binary-splitting algorithm is an essentially-optimal adaptive group-testing algorithm that finds
d
n
n\leq2d-2
n
l=n-d+1
\alpha=\lfloorlog2{l/d}\rfloor
2\alpha
n:=n-2\alpha
x
n:=n-1-x
d:=d-1
The generalised binary-splitting algorithm requires no more than
T
T=\begin{cases} n&n\leq2d-2\\ (\alpha+2)d+p-1&n\geq2d-1 \end{cases}
For
n/d
T → dlog2(n/d)
t=
| e | |
| log2e |
dlog2\left(
| n | |
| d |
\right)
s
d\geq2
T-BI(d,n)\leq(d-1)
BI(d,n)=\left\lceillog2
| d | |
| \sum | |
| i=0 |
{n\choosei}\right\rceil
Non-adaptive group-testing algorithms tend to assume that the number of defectives, or at least a good upper bound on them, is known.[17] This quantity is denoted
d
d
Combinatorial Orthogonal Matching Pursuit, or COMP, is a simple non-adaptive group-testing algorithm that forms the basis for the more complicated algorithms that follow in this section.
First, each entry of the testing matrix is chosen i.i.d. to be
1
1/d
0
The decoding step proceeds column-wise (i.e. by item). If every test in which an item appears is positive, then the item is declared defective; otherwise the item is assumed to be non-defective. Or equivalently, if an item appears in any test whose outcome is negative, the item is declared non-defective; otherwise the item is assumed to be defective. An important property of this algorithm is that it never creates false negatives, though a false positive occurs when all locations with ones in the j-th column of
M
The COMP algorithm requires no more than
ed(1+\delta)ln(n)
n-\delta
In the noisy case, one relaxes the requirement in the original COMP algorithm that the set of locations of ones in any column of
M
q
4.36(\sqrt{\delta}+\sqrt{1+\delta})2(1-2q)-2dlog2{n}
n-\delta
The definite defectives method (DD) is an extension of the COMP algorithm that attempts to remove any false positives. Performance guarantees for DD have been shown to strictly exceed those of COMP.[19]
The decoding step uses a useful property of the COMP algorithm: that every item that COMP declares non-defective is certainly non-defective (that is, there are no false negatives). It proceeds as follows.
Note that steps 1 and 2 never make a mistake, so the algorithm can only make a mistake if it declares a defective item to be non-defective. Thus the DD algorithm can only create false negatives.
SCOMP (Sequential COMP) is an algorithm that makes use of the fact that DD makes no mistakes until the last step, where it is assumed that the remaining items are non-defective. Let the set of declared defectives be
K
K
K
The algorithm proceeds as follows.
K
K
K
K
In simulations, SCOMP has been shown to perform close to optimally.
A deterministic algorithm that is guaranteed to exactlyidentify up to
d
M
y
xi=1~~if~~M(:,i)~.*~y=M(:,i)
.*
M(:,i)
i
M
M
A group/pool
\ell
p>1
n\ge1
q=pn
c\ge2
n=qc
qc-1
q
Fq
\{0,1,2,\ldots,q-1\}
Fq
Fq
x=(u,v)
1\lel\lec-1
0\le
| u | |
| il |
\leq-1
v~=~ac-1
| ~u | |
| ic-1 |
+ … +
| a~u | |
| i1 |
+b, a,b,
| u | |
| il |
\inFq.
The combination of looping through the
| u | |
| il |
qc-1
d-1
| u | |
| i1 |
x … x
| u | |
| ic-1 |
=\{(i1,\ldots,ic-1)\}
0\leil\leq-1
id-1
q
id-2
q2
i1
a
b
\begin{align} ui&=
| c-1 | |
| \sum | |
| l=1 |
~qd-1-l~il\\
| v | |
| ui |
&=
| c-1 | |
| \sum | |
| l=1 |
~al~il+b (computedinFq)\\
| x | |||||||
|
&=(ui,v
| ui |
) \end{align}
The computations in
Fq
q
q
Fq
| v | |
| ui |
=
| c-1 | |
| (\sum | |
| l=1 |
alil+b)~mod~q
\ell
a=1,b=0,c=2
i1 | i2 | ui |
| qui+
| \ell | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | x0 | ||||||||
0 | 1 | 1 | 1 | 4 | x4 | ||||||||
0 | 2 | 2 | 2 | 8 | x8 | ||||||||
1 | 0 | 3 | 1 | 10 | x10 | ||||||||
1 | 1 | 4 | 2 | 14 | x14 | ||||||||
1 | 2 | 5 | 0 | 15 | x15 | ||||||||
2 | 0 | 6 | 2 | 20 | x20 | ||||||||
2 | 1 | 7 | 0 | 21 | x21 | ||||||||
2 | 2 | 8 | 1 | 25 | x25 |
This method uses
q(c-1)(d+1)
d
n=qc
c
The generality of the theory of group testing lends it to many diverse applications, including clone screening, locating electrical shorts;[2] high speed computer networks;[21] medical examination, quantity searching, statistics; machine learning, DNA sequencing;[22] cryptography;[23] [24] and data forensics.[25] This section provides a brief overview of a small selection of these applications.
A multiaccess channel is a communication channel that connects many users at once. Every user can listen and transmit on the channel, but if more than one user transmits at the same time, the signals collide, and are reduced to unintelligible noise. Multiaccess channels are important for various real-world applications, notably wireless computer networks and phone networks.[26]
A prominent problem with multiaccess channels is how to assign transmission times to the users so that their messages do not collide. A simple method is to give each user their own time slot in which to transmit, requiring
n
In the context of group testing, this problem is usually tackled by dividing time into 'epochs' in the following way.[2] A user is called 'active' if they have a message at the start of an epoch. (If a message is generated during an epoch, the user only becomes active at the start of the next one.) An epoch ends when every active user has successfully transmitted their message. The problem is then to find all the active users in a given epoch, and schedule a time for them to transmit (if they have not already done so successfully). Here, a test on a set of users corresponds to those users attempting a transmission. The results of the test are the number of users that attempted to transmit,
0,1,
2+
\{0,1,2+\}
Machine learning is a field of computer science that has many software applications such as DNA classification, fraud detection and targeted advertising. One of the main subfields of machine learning is the 'learning by examples' problem, where the task is to approximate some unknown function when given its value at a number of specific points.[2] As outlined in this section, this function learning problem can be tackled with a group-testing approach.
In a simple version of the problem, there is some unknown function,
f:\{0,1\}N\to\{0,1\}
f(bf{x})=bf{a} ⋅ bf{x}
bf{a}\in\{0,1\}N
bf{a}
d
d\llN
1
f
t
t
f
f
In this problem, recovering
f
bf{a}
f(bf{p})=1
n
bf{a}n=bf{p}n=1
d
n
bf{a}
1
bf{p}
f(bf{p})=1
In reality, one will often be interested in functions that are more complicated, such as
f:CN\toC
f(bf{x})=bf{a} ⋅ bf{x}
In compressed sensing, the goal is to reconstruct a signal,
bf{v}\inCN
bf{v}
bf{v}
bf{v}
Mbf{v}=bf{q}
M
t x N
q
The primary difficulty in compressed sensing is identifying which entries are significant. Once that is done, there are a variety of methods to estimate the actual values of the entries.[29] This task of identification can be approached with a simple application of group testing. Here a group test produces a complex number: the sum of the entries that are tested. The outcome of a test is called positive if it produces a complex number with a large magnitude, which, given the assumption that the significant entries are sparse, indicates that at least one significant entry is contained in the test.
There are explicit deterministic constructions for this type of combinatorial search algorithm, requiring
| (log2log2N)O(1) | |
| d2 |
f
N
During a pandemic such as the COVID-19 outbreak in 2020, virus detection assays are sometimes run using nonadaptive group testing designs.[31] [32] One example was provided by the Origami Assays project which released open source group testing designs to run on a laboratory standard 96 well plate.[33]
In a laboratory setting, one challenge of group testing is the construction of the mixtures can be time-consuming and difficult to do accurately by hand. Origami assays provided a workaround for this construction problem by providing paper templates to guide the technician on how to allocate patient samples across the test wells.[34]
Using the largest group testing designs (XL3) it was possible to test 1120 patient samples in 94 assay wells. If the true positive rate was low enough, then no additional testing was required.
See also: List of countries implementing pool testing strategy against COVID-19.
Data forensics is a field dedicated to finding methods for compiling digital evidence of a crime. Such crimes typically involve an adversary modifying the data, documents or databases of a victim, with examples including the altering of tax records, a virus hiding its presence, or an identity thief modifying personal data.[25]
A common tool in data forensics is the one-way cryptographic hash. This is a function that takes the data, and through a difficult-to-reverse procedure, produces a unique number called a hash. Hashes, which are often much shorter than the data, allow us to check if the data has been changed without having to wastefully store complete copies of the information: the hash for the current data can be compared with a past hash to determine if any changes have occurred. An unfortunate property of this method is that, although it is easy to tell if the data has been modified, there is no way of determining how: that is, it is impossible to recover which part of the data has changed.[25]
One way to get around this limitation is to store more hashes – now of subsets of the data structure – to narrow down where the attack has occurred. However, to find the exact location of the attack with a naive approach, a hash would need to be stored for every datum in the structure, which would defeat the point of the hashes in the first place. (One may as well store a regular copy of the data.) Group testing can be used to dramatically reduce the number of hashes that need to be stored. A test becomes a comparison between the stored and current hashes, which is positive when there is a mismatch. This indicates that at least one edited datum (which is taken as defectiveness in this model) is contained in the group that generated the current hash.[25]
In fact, the amount of hashes needed is so low that they, along with the testing matrix they refer to, can even be stored within the organisational structure of the data itself. This means that as far as memory is concerned the test can be performed 'for free'. (This is true with the exception of a master-key/password that is used to secretly determine the hashing function.)[25]