Group testing

In statistics and combinatorial mathematics, group testing is any procedure that breaks up the task of identifying objects into tests on groups of items, rather than testing each item individually. First studied by Robert Dorfman in 1943, group testing is a relatively new field of 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.…

In statistics and combinatorial mathematics, group testing is any procedure that breaks up the task of identifying objects into tests on groups of items, rather than testing each item individually. First studied by Robert Dorfman in 1943, group testing is a relatively new field of 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. The fundamental result by Peter Ungar in 1960 shows that if the prevalence rate p>p_{u} , where p_{u} = (3-\sqrt{5})/2\approx 0.38 , then individual testing is the optimal group testing procedure with respect to the expected number of tests, and if p , then it is not optimal. However, it is important to note that despite 80 years' worth of research effort, the optimal procedure is yet unknown for p and a general population size n>2 . Dorfman's '2-stage algorithm' to an arbitrary number of stages that required no more than t = \frac{e}{\log_2(e)}d \log_2(n) tests to be guaranteed to find d or fewer defectives among n items. The idea was to remove all the items in negative tests, and divide the remaining items into groups as was done with the initial pool. This was to be done s - 1 times before performing individual testing. Combinatorial group testing in general was later studied more fully by Katona in 1973. 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 = \lceil \log_2(n) \rceil tests, which he also proved to be optimal. 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. 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 tests above the information lower bound where d is the number of defectives. Considerable improvements to this were made in 2013 by Allemann, getting the required number of tests to less than 0.187d + 0.5\log_2(d) + 5.5 above the information lower bound when n/d \geq 38 and d \geq 10 . This was achieved by changing the binary search in the binary-splitting algorithm to a complex set of sub-algorithms with overlapping test groups. As such, the problem of adaptive combinatorial group testing – with a known number or upper bound on the number of defectives – has essentially been solved, with little room for further improvement. 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 , and that it is not minmax when n > 3d . It is currently conjectured that this bound is sharp: that is, individual testing is minmax if and only if n \leq 3d . Some progress was made in 2000 by Riccio and Colbourn, who showed that for large n , individual testing is minmax when d \geq n/\log_{3/2}(3) \approx 0.369n . In this vein, Chan et al. (2011) introduced COMP, a probabilistic algorithm that requires no more than t = ed(1+\delta)\ln(n) tests to find up to d defectives in n items with a probability of error no more than n^{-\delta} . This is within a constant factor of the t = O(d\log_2 n) lower bound. 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. 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 d^2 \geq n , by comparing it to a hypothetical algorithm that defines a reasonable optimum. The performance of this hypothetical algorithm suggests that there is room for improvement when d^2 , as well as suggesting how much improvement this might be. The input vector, \mathbf{x} = (x_1, x_2, \dots, x_n) , is defined to be a binary vector of length n (that is, \mathbf{x} \in \{0,1\}^n ), with the j-th item being called defective if and only if x_j= 1 . Further, any non-defective item is called a 'good' item. \mathbf{x} is intended to describe the (unknown) set of defective items. The key property of \mathbf{x} is that it is an implicit input. That is to say, there is no direct knowledge of what the entries of \mathbf{x} are, other than that which can be inferred via some series of 'tests'. This leads on to the next definition. Let \mathbf{x} be an input vector. A set, S \subseteq \{ 1, 2, \dots, n \} is called a test. When testing is noiseless, the result of a test is positive when there exists j \in S such that x_j = 1 , and the result is negative otherwise. Therefore, the goal of group testing is to come up with a method for choosing a 'short' series of tests that allow \mathbf{x} to be determined, either exactly or with a high degree of certainty. A group-testing algorithm is said to make an error if it incorrectly labels an item (that is, labels any defective item as non-defective or vice versa). This is not the same thing as the result of a group test being incorrect. An algorithm is called zero-error if the probability that it makes an error is zero. t(d, n) denotes the minimum number of tests required to always find d defectives among n items with zero probability of error by any group-testing algorithm. For the same quantity but with the restriction that the algorithm is non-adaptive, the notation \bar{t}(d, n) is used. Since it is always possible to resort to individual testing by setting S_j = \{j\} for each 1 \leq j \leq n , it must be that that \bar{t}(d, n) \leq n . Also, since any non-adaptive testing procedure can be written as an adaptive algorithm by simply performing all the tests without regard to their outcome, t(d, n) \leq \bar{t}(d, n) . Finally, when 0 \neq d \neq n , there is at least one item whose defectiveness must be determined (by at least one test), and so 1 \leq t(d, n) . In summary (when assuming 0 \neq d \neq n ), 1 \leq t(d,n) \leq \bar{t}(d, n) \leq n . Suppose a non-adaptive group testing procedure for n items consists of the tests S_1, S_2, \dots, S_t for some t \in \mathbb{N}_{\geq 0} . The testing matrix for this scheme is the t \times n binary matrix, M , where (M)_{ij} = 1 if and only if j \in S_i (and is zero otherwise). Thus each column of M represents an item and each row represents a test, with a 1 in the (i,j)\textrm{-th} entry indicating that the i\textrm{-th} test included the j\textrm{-th} item and a 0 indicating otherwise. As well as the vector \mathbf{x} (of length n ) that describes the unknown defective set, it is common to introduce the result vector, which describes the results of each test. Let t be the number of tests performed by a non-adaptive algorithm. The result vector, \mathbf{y} = (y_1, y_2, \dots, y_t) , is a binary vector of length t (that is, \mathbf{y} \in \{0,1\}^t ) such that y_i= 1 if and only if the result of the i\textrm{-th} test was positive (i.e. contained at least one defective). With these definitions, the non-adaptive problem can be reframed as follows: first a testing matrix is chosen, M , after which the vector \mathbf{y} is returned. Then the problem is to analyse \mathbf{y} to find some estimate for \mathbf{x} . In the simplest noisy case, where there is a constant probability, q , that a group test will have an erroneous result, one considers a random binary vector, \mathbf{v} , where each entry has a probability q of being 1 , and is 0 otherwise. The vector that is returned is then \hat{\mathbf{y}} = \mathbf{y} + \mathbf{v} , with the usual addition on (\mathbb{Z}/2\mathbb{Z})^n (equivalently this is the element-wise XOR operation). A noisy algorithm must estimate \mathbf{x} using \hat{\mathbf{y}} (that is, without direct knowledge of \mathbf{y} ). If n \leq 2d - 2 , test the n items individually. Otherwise, set l = n - d + 1 and \alpha = \lfloor \log_2{l/d} \rfloor . Test a group of size 2^\alpha . If the outcome is negative, every item in the group is declared to be non-defective; set n := n - 2^\alpha and go to step 1. Otherwise, use a binary search to identify one defective and an unspecified number, called x , of non-defective items; set n := n - 1 - x and d := d - 1 . Go to step 1. The generalised binary-splitting algorithm requires no more than T tests where T = \begin{cases} n & n \leq 2d-2\\ (\alpha+2)d + p - 1 & n \geq 2d - 1 \end{cases} . For n/d large, it can be shown that T \rightarrow d \log_2(n/d) , which compares favorably to the t = \frac{e}{\log_2 e}d\log_2 \left( \frac{n}{d} \right) tests required for Li's s -stage algorithm. In fact, the generalised binary-splitting algorithm is close to optimal in the following sense. When d \geq 2 it can be shown that T - B_I(d,n) \leq (d-1) , where B_I(d,n) = \left\lceil \log_2 \sum_{i=0}^d {n \choose i} \right\rceil is the information lower bound. x_i = 1 ~~ \text{ if } ~~ M(:,i)~.*~y = M(:,i) , where .* represents element wise multiplication and M(:,i) is the i th column of M . Since the decoding step is not difficult, PP is specialized for generating M . generated using a polynomial relation that specifies the indices of the samples contained in each pool. A set of input parameters determines the algorithm. For a prime number p>1 and an integer n \ge 1 any prime power is defined by q=p^n . For a dimension parameter c \ge 2 the total number of samples is n = q^c and the number of samples per pool is q^{c-1} . Further, the Finite field of order q is denoted by \mathbb{F}_q (i.e., the integers \{0,1,2,\ldots,q-1\} defined by special arithmetic operations that ensure that addition and multiplication in \mathbb{F}_q remains in \mathbb{F}_q ). The method arranges each sample in a grid and represents it by coordinates x = (u,v) . The coordinates are computed according to a polynomial relation using the integers 1 \le l \le c-1 , 0 \le u_{i_l} \le q-1 v~=~a^{c-1}~u_{i_{c-1}} + \cdots + a~u_{i_1} + b, \quad a, b, u_{i_l} \in \mathbb{F}_q. The combination of looping through the u_{i_l} values is represented by a set with q^{c-1} elements of a sequence of d-1 integers, i.e., u_{i_1} \times \cdots \times u_{i_{c-1}} = \{(i_1,\ldots,i_{c-1})\} , where 0 \le i_l \le q-1 . Without loss of generality, the combination is such that i_{d-1} cycles every q times, i_{d-2} cycles every q^2 times until i_1 cycles only once. Formulas that compute the sample indices, and thus the corresponding pools, for fixed a and b , are given by \begin{align} u_i &= \sum_{l=1}^{c-1}~q^{d-1-l}~i_l \\ v_{u_i} &= \sum_{l=1}^{c-1}~a^{l}~i_l + b\quad (\text{computed in } \mathbb{F}_q) \\ x_{q u_i + v_{u_i}} &= (u_i,v_{u_i}) \end{align} The computations in \mathbb{F}_q can be implemented with publicly available software libraries for finite fields, when q is a prime power. When q is a prime number then the computations in \mathbb{F}_q simplify to modulus arithmetics, i.e., v_{u_i} = (\sum_{l=1}^{c-1}a^{l}i_l + b) ~ \text{mod}~q . An example of how to generate one pool \ell when a = 1, b = 0, c = 2 is displayed in the table below, while the corresponding selection of samples is shown in the figure above. This method uses q(c-1)(d+1) tests to exactly identify up to d positives among n = q^c samples. Because of this PP is particularly effective for large sample sizes, since the number of tests grows only linearly with respect to c while the samples grow exponentially with this parameter. However PP can also be effective for small sample sizes. In a simple version of the problem, there is some unknown function, f: \{0,1\}^N \to \{0,1\} where f(\textbf{x}) = \textbf{a} \cdot \textbf{x} , and \textbf{a} \in \{0,1\}^N (using logical arithmetic: addition is logical OR and multiplication is logical AND). Here \textbf{a} is ' d sparse', which means that at most d \ll N of its entries are 1 . The aim is to construct an approximation to f using t point evaluations, where t is as small as possible. (Exactly recovering f corresponds to zero-error algorithms, whereas f is approximated by algorithms that have a non-zero probability of error.) In this problem, recovering f is equivalent to finding \textbf{a} . Moreover, f(\textbf{p}) = 1 if and only if there is some index, n , where \textbf{a}_n = \textbf{p}_n = 1 . Thus this problem is analogous to a group-testing problem with d defectives and n total items. The entries of \textbf{a} are the items, which are defective if they are 1 , \textbf{p} specifies a test, and a test is positive if and only if f(\textbf{p}) = 1 . In reality, one will often be interested in functions that are more complicated, such as f: \mathbb{C}^N \to \mathbb{C} , again where f(\textbf{x}) = \textbf{a} \cdot \textbf{x} . Compressed sensing, which is closely related to group testing, can be used to solve this problem. In compressed sensing, the goal is to reconstruct a signal, \textbf{v} \in \mathbb{C}^N , by taking a number of measurements. These measurements are modelled as taking the dot product of \textbf{v} with a chosen vector. The aim is to use a small number of measurements, though this is typically not possible unless something is assumed about the signal. One such assumption (which is common ) is that only a small number of entries of \textbf{v} are significant, meaning that they have a large magnitude. Since the measurements are dot products of \textbf{v} , the equation M\textbf{v} = \textbf{q} holds, where M is a t \times N matrix that describes the set of measurements that have been chosen and \mathbf{q} is the set of measurement results. This construction shows that compressed sensing is a kind of 'continuous' group testing. 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. 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 d2^{(\log_2 \log_2 N)^{O(1)}} measurements. However, as with group-testing, these are sub-optimal, and random constructions (such as COMP) can often recover f sub-linearly in N .

Text derived from https://en.wikipedia.org/w/index.php?oldid=1376238889 under CC BY-SA 4.0; modifications have been made.