Improved matrix pooling

Abstract

Pooled testing is useful to identify positive specimens for large-scale screening. Matrix pooling is one of the commonly used algorithms. In this work, we investigate the properties of matrix pooling and reveal that the efficiency of matrix pooling is related with the magnitude of overlapping among groups. Based on this property, we develop a new design to further improve the efficiency while taking into account of testing error. The efficiency, pooling sensitivity and specificity of this algorithm are explicitly derived and verified through plasmode simulation of detecting acute human immunodeficiency virus among patients who were suspected to have malaria in rural Ugandan. We show that the new design outperforms matrix pooling in efficiency while retain the pooling sensitivity and specificity.

Keywords

Matrix pooling efficiency group testing sensitivity specificity

1 Introduction

Screening for transfusion-transmissible infections is important in national blood programs to ensure the safety of blood supply.^1,2 A recent survey in China shows that the seroprevalence of human immunodeficiency virus (HIV), hepatitis B and C viruses, and Treponema pallidum among 211,639 blood donors were 0.08%, 0.51%, 0.20% and 0.57%, respectively.³ Blood donation during seronegative ‘window period’ is considered as the greatest threat to the safety of blood supply.⁴ For HIV, window period donation accounts for at least 90% of risk.⁵ Nucleic acid amplification tests (NAAT) is proved to be beneficial for blood safety by shortening the window period considerably.⁶ However, NAAT is very expensive and thus pooled NAAT screening is usually used for its efficiency and cost saving. Pooled testing (or group testing) was originally introduced by Dorfman to screen blood samples for the syphilis antigen in U.S. soldiers during the Second World War.⁷ It has been widely applied in many fields, such as HIV/AIDS,^8,9 agriculture,^10,11 genetics^12,13 and compressed sensing.¹⁴

An essential step in group testing is to design the algorithm.¹⁵ For pooled NAAT, there are two types of pooling design: minipool and matrix pooling.^16,17 Minipool is a type of Dorfman’s algorithm, where non-overlapped groups are screened in the first stage. Matrix pooling (or two-dimensional array-based group testing algorithm) is performed through placing specimens in an array and then screening groups which are formed by rows and by columns.¹⁸ Basically, both designs are two-stage approaches, where groups are screened parallelly in the first stage and suspected infections are further screened individually in the second stage. As pointed out, matrix pooling outperforms minipool in efficiency and negative predictive value.¹⁹ Matrix pooling is widely used in high throughput screening, for example, to identify of individuals with acute HIV infections,²⁰ and to uncover of DNA variants.^21–23 In this study, we will focus on this type of group testing algorithm.

Efficiency is the main concern in group testing and is usually used to measure the performance of a group testing algorithm.^24–26 To improve efficiency, Berger et al.²⁷ proposed three-dimensional extensions of two-dimensional pooling approach. Sudbury²⁸ proposed an array-based algorithm using a selection design, but did not provide an instruction on how to construct such a design. Both studies assume perfect sensitivity and specificity of the screening tool. However, the screening tool is not perfect in practice.²⁹ Kim et al.²⁴ studied the operating characteristics of square array-based testing algorithms in the presence of testing error. Hedt and Pagano³⁰ proposed to improve the square array scheme through using the halving strategy for retesting. In this study, we aim to develop a more flexible and efficient array-based algorithm than the square array scheme in the presence of testing error.

This paper is organized as follows. In Section 2, we investigate the characteristics of matrix pooling and propose a general design for group testing, along with an approach to construct the design. Considering misclassification, we investigate the operating characteristics of our algorithm including the efficiency, pooling sensitivity and specificity. In Section 3, we conduct simulation studies and a real data analysis to explore the performances of our proposed algorithm. Some discussions are given in Section 4. All the technical details are presented in the Supplemental Material.

2 Method

2.1 The properties of matrix pooling

Suppose N specimens are denoted by a set

S_{N} = {ℐ_{1}, \dots, ℐ_{N}} .

They are assigned into m groups,

{G_{1}, \dots, G_{m}} .

Consider equal sized groups and denote matrix pooling with m groups by M_m. Table 1(a) shows the design of M₁₂. The specimens are placed in an array. Each row or each column forms a group. Shown by Table 1(a), the highlighted specimen

ℐ_{1}

is the intersection of the first row group and the first column group. Each specimen

ℐ

is covered by one row group and one column group. This property is formulated as

# (G_{i} \cap G_{j}) \leq 1, G_{i} \cap G_{j} \cap G_{l} = Ø, S_{N} = ⋃_{1 \leq i < j \leq m} (G_{i} \cap G_{j}), i < j < l \in {1, \dots, m} (*)

where

# (a)

denotes the number of elements contained in the set a. Denote an equal sized group testing algorithm satisfying the property (*) by A_k_, _m , where k is the group size.

Table 1.

The pooling design for 36 specimens.

Note that M_m is a special case of A_k_, _m , with m = 2k. Generally, we have the following relationship: mk = 2N for the design A_k_, _m . Table 1(a) also explains that there is no intersection between row groups or between column groups. To describe the magnitude of overlapping, we define a measurement ρ as follows

ρ (A_{k, m}) = \frac{1}{(\begin{matrix} m \\ 2 \end{matrix})} \sum_{1 \leq i < j \leq m} I_{{G_{i} \cap G_{j} \neq ϕ}} = \frac{2 N}{m (m - 1)} = \frac{k}{m - 1}

For the design M₁₂, we have $ρ (M_{12}) = 6 / 11 .$ If we increase ρ, e.g. to impose any two groups have a common specimen, will the efficiency of the corresponding group testing algorithm be improved?

To answer this question, we first investigate the relationship between ρ and the efficiency of A_k_, _m . Following Kim et al.,²⁴ efficiency is defined as the expected number of tests per specimen, and therefore, a smaller value is better. Denote it by ‘Eff’. Let G_i = 1 if the ith group is tested positive for $i = 1, \dots, n$ . Then the efficiency of group testing algorithm A_k_, _m is defined as

Eff (A_{k, m}) = \frac{m}{N} + \frac{1}{N} \sum_{1 \leq i < j \leq m} I_{{G_{i} \cap G_{j} \neq φ}} P (G_{i} = 1, G_{j} = 1)

For perfect screening, we have $Eff (A_{k, m}) = \frac{2}{k} + 1 - 2 (1 - p)^{k} + (1 - p)^{2 k - 1}$ , where $k = 4 N / (1 + \sqrt{1 + 8 N / ρ})$ derived from the definition of $ρ .$ To further show the relationship between $Eff (A_{k, m})$ and $ρ,$ denote by p the proportion of the trait of interest, e.g. the prevalence of a disease. Considering perfect screening, we have the following result.

Proposition 1

For a group testing algorithm A_k_, _m , there exists an upper bound p_u(k) that the efficiency $Eff (A_{k, m})$ is a decreasing function of ρ if the prevalence p is smaller than $p_{u} (k) .$

The proof of Proposition 1 is presented in the Supplemental Material, along with a list of the upper bound p_u(k). For example, the upper bound is $p_{u} (k) = 0.359$ for k = 5. Since the prevalence p is always smaller than p_u(k) for rare trait, the efficiency $Eff (A_{k, m})$ will be improved if we increase $ρ .$ The maximum value of $ρ (A_{k, m})$ is ρ = 1. One feasible design for N = 36 satisfying ρ = 1 is presented in Table 1(b). Each row forms a group. In this design, we just require an initial nine tests for N = 36 specimens. A natural question is how to design the array as Table 1(b) for general cases?

2.2 New design

In this section, we proceed to explore the design satisfying ρ = 1 (e.g. Table 1(b)). We first formally describe the structure of the new design

# (G_{i} \cap G_{j}) = 1, G_{i} \cap G_{j} \cap G_{k} = \emptyset, S_{N} = \underset{1 \leq i < j \leq m}{\cup} (G_{i} \cap G_{j}), \forall i < j < k

(1)

Denote the above formulas as Criterion (1). The first formula of Criterion (1) shows that there is one common specimen among any two groups. The second one shows that no common specimen is contained in any three groups. The last one reveals that each specimen is the intersection of two groups. This criterion is a special case of the property (*) and infers a group testing algorithm satisfying ρ = 1.

To facilitate the construction process, define a A_k_, _m as a m × N binary matrix

(a_{ij})_{m \times N},

with rows represent groups

{G_{1}, \dots, G_{m}}

and columns represent specimens

S_{N} = {ℐ_{1}, \dots, ℐ_{N}} .

Define the element a_ij = 1 if the jth specimen is contained in the ith group and a_ij = 0 otherwise, for

i = 1, \dots, m

and

j = 1, \dots, N .

As an example, the new design in Table 1(b) could be formatted as in Table 2. Note that for a design satisfying Criterion (1), the number of specimens is

N = (\begin{matrix} m \\ 2 \end{matrix})

Table 2.

Reformation of the design in Table 1(b).

$ℐ$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36
G ₁	1	1	1	1	1	1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
G ₂	1	0	0	0	0	0	0	0	1	1	1	1	1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
G ₃	0	1	0	0	0	0	0	0	1	0	0	0	0	0	0	1	1	1	1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
G ₄	0	0	1	0	0	0	0	0	0	1	0	0	0	0	0	1	0	0	0	0	0	1	1	1	1	1	0	0	0	0	0	0	0	0	0	0
G ₅	0	0	0	1	0	0	0	0	0	0	1	0	0	0	0	0	1	0	0	0	0	1	0	0	0	0	1	1	1	1	0	0	0	0	0	0
G ₆	0	0	0	0	1	0	0	0	0	0	0	1	0	0	0	0	0	1	0	0	0	0	1	0	0	0	1	0	0	0	1	1	1	0	0	0
G ₇	0	0	0	0	0	1	0	0	0	0	0	0	1	0	0	0	0	0	1	0	0	0	0	0	1	0	0	0	0	0	1	0	0	1	1	0
G ₈	0	0	0	0	0	0	1	0	0	0	0	0	0	1	0	0	0	0	0	1	0	0	0	0	0	1	0	0	0	0	0	1	0	1	0	1
G ₉	0	0	0	0	0	0	0	1	0	0	0	0	0	0	1	0	0	0	0	0	1	0	0	0	0	0	1	0	0	0	0	0	1	0	1	1

We then show how to obtain A_k_, _m under Criterion (1) for general cases. If $ρ = 1,$ we have $m = k + 1$ and therefore denote the design $A_{m - 1, m}$ by A_m for short. Let $1_{l}$ be a l-dimensional column vector with all the elements being 1 and $0_{l}$ be a l-dimensional column vector with all the elements being 0 for $l \geq 1 .$ Suppose that the group size is equal. The design A_m is formulated as

A_{m} = (\begin{matrix} \begin{array}{l} 1_{m - 1}^{'} \\ I_{(m - 1) \times (m - 1)} \end{array} & \begin{array}{l} 0_{N - (m - 1)}^{'} \\ A_{m - 1} \end{array} \end{matrix})

where

b'

denotes the transpose of matrix b and

I_{m \times m}

is an identity matrix of size

m \geq 2

and

A_{2} = 1_{2} .

For illustration, we display the design A_m with m = 3, 4, 5 in Table 3. The design A_m is iteratively constructed based on the design

A_{m - 1} .

To clearly show this relationship, we highlight A₄ in the design

A_{5},

and also A₃ in the design

A_{4} .

Table 3.

The designs $A_{3}, A_{4} and A_{5}$ .

2.3 The group testing algorithm using the design A_m

Considering misclassification, we use the design A_m to conduct screening and perform further retesting after the first-stage screening. Let S_e and S_p denote the sensitivity and specificity of the screening tool, respectively. Denote ${\tilde{I}}_{i}$ and I_i as the true status and observed status of the ith specimen for $i = 1, \dots, N .$ Now, we list two assumptions:

Assumption 1

${\tilde{I}}_{1}, \dots, {\tilde{I}}_{N}$ i.i.d. follow Bernoulli distribution with parameter p.

Assumption 2

For each test, S_e and S_p are independent of the group size.

Assumptions 1 and 2 have been discussed extensively²⁴ and are standard in group testing literature.²⁵

Let Z_j = 1 if the jth group of the design A_m tests positive and Z_j = 0 if negative. Let ${\tilde{Z}}_{j} = 1$ if the true status of the jth group is positive and ${\tilde{Z}}_{i} = 0$ otherwise. For any $i \neq j,$ denote the common specimens of ${G_{i}, G_{j}}$ by $ℐ_{i, j}$ . Suppose that we retest the specimen $ℐ_{i, j}$ if the groups ${G_{i}, G_{j}}$ all test positive, or if one of ${G_{i}, G_{j}}$ tests positive and the remaining groups test negative. The number of tests is defined by $T_{m} = m + \sum_{1 \leq i < j \leq m} T_{i, j},$ where

T_{i, j} = {\begin{array}{l} 1, Z_{i} = Z_{j} = 1 \\ 1, Z_{i} + Z_{j} = 1, \sum_{l = 1}^{m} Z_{l} = 1 \\ 0, others \end{array}

This retesting rule tells us that retesting is required when the common specimen $ℐ_{i, j}$ is suspected to be positive or there is inconsistency among the observed statuses of the groups. Such a situation might be faced in practice due to misclassification. Based on this rule, the expected number of tests is

E T_{m} = m + \sum_{1 \leq i < j \leq m} [P (Z_{i} + Z_{j} = 2) + P (Z_{i} + Z_{j} = 1, \sum_{l = 1}^{m} Z_{l} = 1)]

We proceed to obtain the explicit expression of ${ET}_{m} .$ Denote the number of specimens contained in n groups by $H (n, m) .$ As derived from the formulation of $A_{m},$ any n groups contain the same number of specimens. Therefore, H(n, m) is identical to the number of specimens covered by the first n groups, which is $H (n, m) = \sum_{j = 1}^{n} (m - j)$ for $1 \leq n \leq m$ and $H (0, m) = 0 .$ Then we have the following result.

Theorem 1

Consider the group testing algorithm using the design A_m with retesting rule $T_{i, j} .$ Under Assumptions 1 and 2, the expected number of tests is

\begin{array}{l} E T_{m} = m + (\begin{matrix} m \\ 2 \end{matrix}) \sum_{t_{1} = 0}^{2} (α_{1} (t_{1}) β_{1} (t_{1}, 2, m) + \sum_{t_{2} = 0}^{m - 2} α_{2} (t_{1}, t_{2}, m) β_{2} (t_{1}, t_{2}, m)) \end{array}

where

α_{1} (t_{1}) = (1 - S_{p})^{t_{1}} S_{e}^{2 - t_{1}}, α_{2} (t_{1}, t_{2}, m) = S_{e}^{2 - t_{1}} S_{p}^{t_{2}} (1 - S_{e})^{m - 2 - t_{2}} (1 - S_{p})^{t_{1}} [t_{1} \frac{S_{p}}{1 - S_{p}} + (2 - t_{1}) \frac{1 - S_{e}}{S_{e}}],

β_{1} (t_{1}, n, m) = (\begin{matrix} n \\ t_{1} \end{matrix}) Ψ_{m} (t_{1}, n) (1 - p)^{H (t_{1}, m)}, β_{2} (t_{1}, t_{2}, m) = (\begin{matrix} 2 \\ t_{1} \end{matrix}) (\begin{matrix} m - 2 \\ t_{2} \end{matrix}) Ψ_{m} (t_{1} + t_{2}, m) (1 - p)^{H (t_{1} + t_{2}, m)}

and

Ψ_{m} (x, y) = I_{{x \leq min {y, m - 2}}} - I_{{x < min {y, m - 1}}} \sum_{j = 1}^{y - x} (- 1)^{j - 1} (\begin{matrix} y - x \\ j \end{matrix}) (1 - p)^{H (j, m - x)} .

The proof is given in the Supplemental Material. Correspondingly, the efficiency is obtained, $Eff (A_{m}) = {ET}_{m} / N .$ For perfect screening, the expected number of tests ET_m is $m + (\begin{matrix} m \\ 2 \end{matrix}) \sum_{j = 0}^{2} (- 1)^{j} (\begin{matrix} 2 \\ j \end{matrix}) (1 - p)^{H (j, m)},$ which is concordant with the result of Theorem 2 in Sudbury.²⁸

2.4 Comparison of the efficiency of the design A_m and M_m

In Proposition 1, we have proved that the efficiency of A_k_, _m is able to be improved if the measurement ρ is increased. The design A_m is an improved version of M_m, since

ρ (A_{m}) = 1

and

ρ (M_{m}) = \frac{m}{2 (m - 1)} .

Proposition 1 only considers perfect screening. In this section, we will consider measurement error and extensively investigate the efficiency of

A_{m},

comparing with the efficiency of

M_{m} .

According to Kim et al.,²⁴ the efficiency of M_m without master pool testing is defined as follows

Eff (M_{m}) = \frac{2}{k} + S_{e} (f (k - 1) + f (k)) - f (k) f (k - 1) + 2 \sum_{c = 0}^{k} {γ_{0} (c) δ_{0} (c) + γ_{1} (c) δ_{1} (c)}

where

m = 2 k, f (k) = S_{e} - (S_{e} + S_{p} - 1) (1 - p)^{k},

and the definition of

γ_{i} (c)

and

δ_{i} (c)

for i = 0, 1 could refer to Kim et al.²⁴ Specially, we calculated the efficiency of M₁₂ and A₉, which are described in Table 1(a) and (b), respectively. The results are presented in Table 4. It shows that our algorithm A₉ needs smaller expected number of tests per specimen under different S_e, S_p and p.

Table 4.

The expected number of tests per specimen, Eff(A₉) and Eff(M₁₂).

(S_e,S_p)	Eff( $A$ )	p
(S_e,S_p)	Eff( $A$ )	0.001	0.005	0.01	0.02	0.03	0.04	0.05
(1,1)	A ₉	0.2510	0.2562	0.2646	0.2870	0.3158	0.3493	0.3865
	$M_{12}$	0.3344	0.3389	0.3457	0.3624	0.3827	0.4061	0.4319
(0.995,0.995)	A ₉	0.2605	0.2648	0.2723	0.2932	0.3206	0.3531	0.3892
	$M_{12}$	0.3438	0.3475	0.3533	0.3683	0.3873	0.4097	0.4348
(0.99,0.99)	A ₉	0.2692	0.2728	0.2795	0.2990	0.3252	0.3566	0.3919
	$M_{12}$	0.3528	0.3556	0.3605	0.3740	0.3918	0.4133	0.4376

We proceed to explore the relation of $Eff (M_{m})$ and $Eff (A_{m})$ for general cases. Define $m_{1} = [\sqrt{2 N}] + 1$ and $m_{2} = 2 [\sqrt{N}]$ , where N is the number of specimens and $[a]$ denotes the maximum integer that is not larger than a. Then the designs $A_{m_{1}}$ and $M_{m_{2}}$ contain nearly the same number of specimens. Moreover, we have the following result, whose proof is given in the Supplemental Material.

Theorem 2

For fixed number of specimens N, there exists a threshold of the prevalence, $p_{c} (S_{e}, S_{p})$ that the efficiency Eff $(A_{m_{1}})$ is smaller than Eff $(M_{m_{2}}) .$

Consider scenarios of the sensitivity S_e and specificity S_p ranging from 0.8 to 1 and the number of specimens

N = 16, 36, 64, 81, 100 .

The threshold p_c is calculated through the equation Eff

(A_{m_{1}})

= Eff

(M_{m_{2}}) .

Results are presented in Table 5. Note that we are interested in rare trait so that the thresholds p_c in Table 5 are relatively large. We will investigate the threshold p_c more thoroughly in Section 3.1.

Table 5.

The threshold p_c for different $S_{e} and S_{p}$ .

	N						N
( $S_{e}, S_{p}$ )	16	36	64	81	100	( $S_{e}, S_{p}$ )	16	36	64	81	100
(0.80,0.80)	0.276	0.185	0.084	0.059	0.048	(0.95,0.90)	0.263	0.100	0.054	0.041	0.035
(0.80,0.90)	0.283	0.193	0.079	0.059	0.048	(0.95,0.95)	0.266	0.099	0.055	0.042	0.036
(0.85,0.85)	0.272	0.225	0.069	0.051	0.042	(0.95,0.99)	0.268	0.099	0.055	0.043	0.036
(0.85,0.90)	0.275	0.143	0.069	0.051	0.043	(0.99,0.95)	0.210	0.091	0.051	0.039	0.033
(0.90,0.90)	0.268	0.116	0.060	0.046	0.038	(0.99,0.99)	0.201	0.091	0.051	0.040	0.034
(0.90,0.95)	0.272	0.114	0.061	0.047	0.039	(1.00,1.00)	0.192	0.089	0.051	0.039	0.034

Additionally, pooling sensitivity and pooling specificity are also important operating characteristics of a group testing algorithm. As defined in group testing literature,^24,26,29 pooling specificity is the probability a specimen is diagnosed as negative by a particular pooling procedure given that specimen is truly negative; pooling sensitivity is the probability a specimen is diagnosed as positive by a particular pooling procedure given that specimen is truly positive. Denote the pooling sensitivity and pooling specificity of our algorithm by $S_{e} (A_{m})$ and $S_{p} (A_{m}) .$ Based on Assumptions 1, 2 and Theorem 1, let $C_{1} = \sum_{t = 0}^{m - 2} α_{2} (0, t, m) β_{1} (t, m - r, m),$ $C_{2} = \sum_{t = 0}^{r} α_{1} (t; m, r) β_{1} (t, r; m, r)$ and $C_{3} = \sum_{t_{1} = 0}^{r} \sum_{t_{2} = 0}^{m - r} α_{2} (t_{1}, t_{2}; m, r) β_{2} (t_{1}, t_{2}; m, r) .$ Then we have

\begin{array}{l} S_{e} (A_{m}) = S_{e}^{3} + S_{e} \cdot C_{1}, and S_{p} (A_{m}) & = 1 - \frac{1 - S_{p}}{1 - p} [C_{2} + C_{3} - p \cdot (S_{e}^{r} + C_{1})] \end{array}

The detailed derivation of $S_{e} (A_{m})$ and $S_{p} (A_{m})$ is presented in the Supplemental Material. These characteristics of our extended array-based design A_m are extensively studied in Section 3.2.

2.5 Extension

In this section, we generalize Criterion (1) to enable more groups to have common specimens. It mimics the generalization from two-dimensional array-based group testing algorithm to three-dimensional array-based group testing algorithm.²⁷ Specifically, the generalized criterion is as follows

# (\cap_{j = 1}^{r} G_{i_{j}}) = s, \cap_{j = 1}^{r + 1} G_{i_{j}} = Ø, S_{N} = ⋃_{1 \leq i_{1} < \dots < i_{r} \leq m} (\cap_{j = 1}^{r} G_{i_{j}})

(2)

This criterion tells that there are s common specimens among r groups and no common specimen is contained in any r + 1 groups. All N specimens are covered by m groups.

Criterion (1) is a special case of Criterion (2). Especially, the individual testing is the case of

(r, s) = (1, 1) .

Denote the design under this rule by

A_{m}^{(r, s)},

which is

\begin{matrix} A_{m}^{(r, s)} = (\begin{matrix} 1_{k_{r} \cdot s}' & 0_{N - k_{r} \cdot s}' \\ A_{m - 1}^{(r - 1, s)} & A_{m - 1}^{(r, s)} \end{matrix}) \end{matrix}

where k_r is defined as

k_{r} = rN / m = (\begin{matrix} m - 1 \\ r - 1 \end{matrix}) .

Note that the design A_m is short for

A_{m}^{(2, 1)} .

For illustration, we display the design

A_{3}^{(2, 2)}

and

A_{4}^{(2, 2)}

in Table 6, along with the design

A_{3} .

Table 6.

The designs $A_{3}^{(2, 2)}, A_{3} and A_{4}^{(2, 2)}$ .

Take a close look at the design $A_{3}^{(2, 2)} .$ If we tie up every two specimens, then the design $A_{3}^{(2, 2)}$ reduces to A₃ with new ‘specimen's. Let $Z_{i}^{(r, s)} = 1$ if the ith group of the design $A_{m}^{(r, s)}$ is tested positive and $Z_{i}^{(r, s)} = 0$ if negative. Let ${\tilde{Z}}_{i}^{(r, s)} = 1$ if the true status of the ith group is positive and ${\tilde{Z}}_{i}^{(r, s)} = 0$ otherwise. Suppose we retest the ‘specimen’ $ℐ_{i_{1}, \dots, i_{r}}^{(s)}$ individually if the groups ${G_{i_{1}}, \dots, G_{i_{r}}}$ are all tested positive or if r – 1 groups of ${G_{i_{1}}, \dots, G_{i_{r}}}$ are tested positive and the remaining groups are tested negative. Since the ‘specimen’ $ℐ_{i_{1}, \dots, i_{r}}^{(s)}$ contains s specimens, the number of tests is defined by $T_{m}^{(r, s)} = m + \sum_{1 \leq i_{1} < \dots < i_{r} \leq m} T_{i_{1}, \dots, i_{r}}^{(s)},$ with

T_{i_{1}, \dots, i_{r}}^{(s)} = {\begin{array}{l} s, \sum_{j = 1}^{r} Z_{i_{j}}^{(r, s)} = r \\ s, \sum_{j = 1}^{r} Z_{i_{j}}^{(r, s)} = r - 1, \sum_{j = r + 1}^{m} Z_{i_{j}}^{(r, s)} = 0 \\ 0, others \end{array}

Therefore, the expected number of tests is

{ET}_{m}^{(r, s)} = m + s \cdot \sum_{1 \leq i_{1} < \dots < i_{r} \leq m} [P (\sum_{j = 1}^{r} Z_{i_{j}}^{(r, s)} = r) + P (\sum_{j = 1}^{r} Z_{i_{j}}^{(r, s)} = r - 1, \sum_{j = r + 1}^{m} Z_{i_{j}}^{(r, s)} = 0)]

The explicit expression of ${ET}_{m}^{(r, s)}$ , along with the pooling sensitivity and specificity, is derived and presented in the Supplemental Material.

3 Numerical results

3.1 Threshold and efficiency

In this section, we proceed to investigate the properties of our algorithm $A_{m},$ comparing with $M_{m} .$ First, we report the threshold $p_{c} (S_{e}, S_{p})$ within a wide range of sensitivity and specificity. Set the number of specimens for each pool by $N = 64 .$ The number of groups is defined by $m_{1} = [\sqrt{2 N}] + 1$ for our algorithm $A_{m_{1}}$ and $m_{2} = 2 [\sqrt{N}]$ for $M_{m_{2}} .$

Figure 1 shows the threshold $p_{c} (S_{e}, S_{p})$ under different sensitivity and specificity. For example, the threshold p_c is approximately 0.05 when sensitivity $S_{e} = 0.99$ and specificity $S_{p} = 0.99 .$ In this case, the efficiency Eff $(A_{m_{1}})$ is definitely smaller than Eff $(M_{m_{2}})$ if the prevalence p is smaller than $p_{c} = 0.05 .$ The relationship of $p_{c} (S_{e}, S_{p})$ with respect to S_e and S_p is similar for different N. Note that the value of p_c overall increases if N is smaller and decreases otherwise, which is also shown in Table 5.

Figure 1.

The contour plot of the threshold $p_{c} (S_{e}, S_{p})$ for N = 64. The efficiency of $A_{m_{1}}$ and $M_{m_{2}}$ satisfy that Eff $(A_{m_{1}}) <$ Eff $(M_{m_{2}})$ if the prevalence $p < p_{c} (S_{e}, S_{p}),$ where $m_{1} = [\sqrt{2 N}] + 1, m_{2} = 2 [\sqrt{N}]$ .

Next, we explore the operating characteristics of our algorithm A_m, including the efficiency, pooling sensitivity and pooling specificity, comparing with square array-based group testing algorithm $M_{m} .$ We consider two scenarios: varying prevalence p with fixed N and varying N with fixed p. The parameters are set at N = 64 and p = 0.01 for the two scenarios, respectively, while $S_{e} = 0.99$ and $S_{p} = 0.99 .$ The results are reported in Figure 2. For comparison, we also report the results of individual test.

Figure 2.

The efficiency, pooling sensitivity and pooling specificity of $A_{m_{1}}, M_{m_{2}}$ and individual test with $S_{e} = 0.99, S_{p} = 0.99$ and $m_{1} = [\sqrt{2 N}] + 1, m_{2} = 2 [\sqrt{N}] .$ The horizontal axis labels are the prevalence p (left panels) and the number of specimens N (right panels).

Figure 2 shows that the efficiency of $A_{m_{1}}$ is the lowest under different scenarios. For example, the efficiency of $A_{m_{1}}$ is 0.2125 while that of $M_{m_{2}}$ is 0.2762 for p = 0.01, N = 64 and $S_{e} = 0.99, S_{p} = 0.99 .$ If N increases, the efficiency becomes smaller for both $A_{m_{1}}$ and $M_{m_{2}},$ shown in the right top panel of Figure 2. However, our algorithm $A_{m_{1}}$ needs fewer expected number of tests per specimens than $M_{m_{2}} .$ The pooling sensitivity of $A_{m_{1}}$ and $M_{m_{2}}$ are similar and are a little lower than $S_{e} = 0.99 .$ The pooling specificity of both algorithms are very high, nearly 0.9998, which is much higher than $S_{p} = 0.99 .$ We omit the results under other settings, since their performance is similar as that under this setting.

3.2 Application to detect acute HIV infections

Bebell et al.³¹ reported a study of identifying acute human immunodeficiency (AHI) virus in Ugandan. They collected 7000 consecutive patients of all ages who were suspected to have malaria in seven government health clinics in rural Ugandan. Only 2893 adults (aged 13 years or older) were included in the study and 30 patients (1.04%) were identified as having AHI using pooled NAAT assay. In their setting, 10 specimens are pooled and screened, denoted by $D_{10} .$ The sensitivity and specificity of NAAT is high, but no HIV test can have a sensitivity of 100% due to factors such as ‘window period’.³² Some researchers reported the positive predictive value of 0.9804 with a specificity of 0.9998, since the NAAT-negative pools were not deconstructed and confirmed negative.³³ So, we set the parameters by $p = 0.0104,$ with $S_{e} = 0.995, S_{p} = 0.995$ or $S_{e} = 0.99, S_{p} = 0.99 .$

Let

A

be a group testing algorithm. We first calculate the operating characteristics of three pooling algorithms: D₁₀,

A_{m_{1}}

and

M_{m_{2}},

where

m_{1} = [\sqrt{2 N}] + 1

and

m_{2} = 2 [\sqrt{N}] .

The parameter N is set at

N = 100 .

The results are reported in Table 7. To demonstrate the application of our approach, we proceed to conduct a plasmode simulation. Create a pool

P_{2893}

of {0, 1} with a total number of 2893 and 30 of them are ‘1’. Draw 2893 samples with replacement from the pool and screen them using the pooling algorithms: D₁₀, A₁₅ and

M_{20},

with

S_{e} = 0.99, S_{p} = 0.99

S_{e} = 0.995, S_{p} = 0.995 .

Record the screening result for each specimen. Finally, we calculate the expected number of tests, the pooling sensitivity and specificity. Repeat the procedure by 10,000 times.

Table 7.

The efficiency, pooling sensitivity and specificity for detecting acute HIV infection.

	$S_{e} = 0.995, S_{p} = 0.995$				$S_{e} = 0.99, S_{p} = 0.99$
	$A$	Eff( $A$ )^a	$S_{e} (A)$	$S_{p} (A)$	Eff( $A$ )	$S_{e} (A)$	$S_{p} (A)$
Theoretical	A ₁₅	0.1737	0.9882	0.9999	0.1776	0.9761	0.9998
calculation	M ₂₀	0.2228	0.9888	0.9999	0.2269	0.9774	0.9998
	D ₁₀	0.2033	0.9900	0.9995	0.2073	0.9801	0.9990
Plasmode	Total number of specimens = 2893
	A ₁₅	0.1757	0.9882	0.9999	0.1799	0.9763	0.9998
	M ₂₀	0.2232	0.9888	0.9999	0.2274	0.9777	0.9998
	D ₁₀	0.2031	0.9899	0.9995	0.2073	0.9800	0.9990
simulation	Total number of specimens = 4200
	A ₁₅	0.1736	0.9881	0.9999	0.1774	0.9766	0.9998
	M ₂₀	0.2226	0.9885	0.9999	0.2267	0.9776	0.9998
	D ₁₀	0.2031	0.9900	0.9995	0.2072	0.9804	0.9990

Eff( $A$ ) is the expected number of tests per specimen.

The number of specimens in each pool is $(\begin{matrix} 15 \\ 2 \end{matrix}) = 105$ for A₁₅ and 100 for $M_{20} .$ Therefore, we also consider a total number of 4200 specimens to straightforwardly compare theoretical results and simulations, since it is a multiplier of both 105 and 100. In this case, we draw 4200 samples with replacement from the pool $P_{2893}$ and the remaining steps are the same as the case of 2893 specimens. All the results are reported in Table 7.

Table 7 shows that A₁₅ has lowest expected number of tests per specimen among the three algorithms. Both algorithms, A₁₅ and M₂₀, have higher pooling specificity and lower pooling sensitivity than D₁₀. The pooling sensitivity and specificity are highly related with the particular pooling procedure. Before the final individual test, a truly positive specimen will be identified as positive only if two groups containing this specimen are tested positive using the algorithms A₁₅ and M₂₀, while just one group containing this specimen needs to be tested positive using D₁₀. On the other hand, the pooling specificity will be improved using A₁₅ or $M_{20} .$ Note that our algorithm A₁₅ only sacrifices little pooling sensitivity but considerably reduces the expected number of tests per specimen. Additionally, the results of theoretical calculation and plasmode simulation in Table 7 are coincided, inferring that our results reported in Theorems 1 and 2 are confirmed. Results of plasmode simulation under different scenarios are presented in the Supplemental Material.

4 Discussion

Group testing is an efficient strategy to identify the infected subjects. One of the commonly used group testing algorithms is matrix pooling. This type of group testing algorithm has a property that groups are overlapped. Investigating the relationship of efficiency and the magnitude of overlapping ρ, we found that the efficiency is an increasing function of ρ within a range of the prevalence. Based on this property, we develop a new array-based design and also provide an iterative method to construct such a design.

Moreover, we have proved theoretically that this new design is more efficient than the existing matrix pooling if the disease prevalence is smaller than a reasonable threshold. Our algorithm retains the pooling sensitivity and specificity of matrix pooling. We use a plasmode simulation to demonstrate real application and also confirm the theoretical results of the operating characteristics of our algorithm. Note that the comparison is made under the condition of approximately the same number of specimens in each pool. Overall, our algorithm needs less number of tests than matrix pooling, which is meaningful while the cost of test is expensive, such as NAAT.

Some extensions of our algorithm are possible, such as different retesting rules in the second stage^30,34,35 and unequal group sizes,^27,36 which have been proposed for square array scheme. Besides, we do not take into account of the heterogeneity of the prevalence among specimens. In practice, some additional informations are able to be collected, such as clinical, demographic parameters and risk behaviors. This type of information is related with the possibility of being positive and is helpful for the process of detecting infective subjects.^37–39 Our design A_m is possible to be further improved if adding such information. These are potential directions of extending the design A_m for future work.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work is supported by National Natural Science Foundation of China [nos. 11526061, 11501134, 11371353]; Guangxi Natural Science Foundation [2015GXNSFBA139016]; the key project of Guangxi Normal University [2014ZD002]; Program on the High Level Innovation Team and Outstanding Scholars in Universities of Guangxi Province. Dr Li was supported in part by Special National Key Research and Development Plan under Grant [2016YFD0400206]; the Breakthrough Projects of Strategic Priority Program of the Chinese Academy of Sciences [XDB13040600].

Supplemental material

Supplemental material is available for this article online.

References

World Health Organization. Screening donated blood for transfusion-transmissible infections: recommendations, Geneva: World Health Organization, 2010.

World Health Organization. Blood safety and availability, Geneva: World Health Organization, 2016.

Yang

Jiao

Liu

et al.

Seroprevalence of human immunodeficiency virus, hepatitis B and C viruses, and Treponema pallidum infections among blood donors at Shiyan, Central China. BMC Infect Dis 2016; 16: 531–531.

Van der Bij

Coutinho

Van der Poel

. Surveillance of risk profiles among new and repeat blood donors with transfusion-transmissible infections from 1995 through 2003 in the Netherlands. Transfusion 2006; 46: 1729–1736.

Busch

Kleinman

Jackson

et al.

Nucleic acid amplification testing of blood donors for transfusion-transmitted infectious diseases. Transfusion 2000; 40: 143–159.

Ellingson

Seem

Nowicki

et al.

Estimated risk of human immunodeficiency virus and hepatitis C virus infection among potential organ donors from 17 organ procurement organizations in the United States. Am J Transplant 2011; 11: 1201–1208.

Dorfman

. The detection of defective numbers of large populations. Ann Math Stat 1943; 14: 436–440.

Pilcher

Fiscus

Nguyen

et al.

Detection of acute infections during HIV testing in North Carolina. N Engl J Med 2005; 352: 1873–1883.

Hutchinson

Patel

Sansom

et al.

Cost-effectiveness of pooled nucleic acid amplification testing for acute HIV infection after third-generation HIV antibody screening and rapid testing in the United States: a comparison of three public health settings. PLoS Med 2010; 7: e1000342–e1000342.

10.

Tebbs

Bilder

. Confidence interval procedures for the probability of disease transmission in multiple-vector-transfer designs. J Agric Biol Environ Stat 2004; 9: 75–90.

11.

Bilder

Tebbs

. Empirical Bayesian estimation of the disease transmission probability in multiple-vector-transfer designs. Biom J 2005; 47: 502–516.

12.

Gastwirth

. The efficiency of pooling in the detection of rare mutations. Am J Hum Genet 2000; 67: 1036–1039.

13.

Sham

Bader

Craig

et al.

DNA pooling: a tool for large-scale association studies. Nat Rev Genet 2002; 3: 862–871.

14.

Cormode

Muthukrishnan

. Combinatorial algorithms for compressed sensing. In: International colloquium on structural information and communication complexity 2006; Vol. 4056, Springer Berlin Heidelberg: SIROCCO, Lecture Notes in Computer Science, pp. 280–294.

15.

. A sequential method for screening experimental variables. J Am Stat Assoc 1962; 57: 455–477.

16.

Pilcher

Price

Hoffman

et al.

Frequent detection of acute primary HIV infection in men in Malawi. AIDS 2004; 18: 517–524.

17.

van Zyl

Preiser

Potschka

et al.

Pooling strategies to reduce the cost of HIV-1 RNA load monitoring in a resource-limited setting. Clin Infect Dis 2011; 52: 264–270.

18.

Phatarfod

Sudbury

. The use of a square array scheme in blood testing. Stat Med 1994; 13: 2337–2343.

19.

May

Gamst

Haubrich

et al.

Pooled nucleic acid testing to identify antiretroviral treatment failure during HIV infection. J Acquir Immune Defic Syndr 2010; 53: 194–201.

20.

Krajden

Cook

Mak

et al.

Pooled nucleic acid testing increases the diagnostic yield of acute HIV infections in a high-risk population compared to 3rd and 4th generation HIV enzyme immunoassays. J Clin Virol 2014; 61: 132–137.

21.

Kwiatkowski

Jr Zoghbi

Ledbetter

et al.

Rapid identification of yeast artificial chromosome clones by matrix pooling and crude lysate PCR. Nucleic Acids Res 1990; 18: 7191–7201.

22.

Zuzarte

Denroche

Fehringer

et al.

A two-dimensional pooling strategy for rare variant detection on next-generation sequencing platforms. PloS One 2014; 9: e93455–e93455.

23.

Sint

Sporleder

Wallinger

et al.

A two-dimensional pooling approach towards efficient detection of parasitoid and pathogen DNA at low infestation rates. Meth Ecol Evol 2016; 7: 1548–1557.

24.

Kim

Hudgens

Dreyfuss

et al.

Comparison of group testing algorithms for case identification in the presence of test error. Biometrics 2007; 63: 1152–1163.

25.

McMahan

Tebbs

Bilder

. Two-dimensional informative array testing. Biometrics 2012; 68: 793–804.

26.

Johnson

Kotz

. Inspection errors for attributes in quality control, New York: Chapman and Hall Ltd., 1991.

27.

Berger

Mandell

Subrahmanya

. Maximally efficient two-stage screening. Biometrics 2000; 56: 833–840.

28.

Sudbury

. Two-stage testing using selection schemes. Stat Med 2010; 29: 2194–2199.

29.

Litvak

Pagano

. Screening for the presence of a disease by pooling sera samples. J Am Stat Assoc 1994; 89: 424–434.

30.

Hedt BL and Pagano M. A matrix pooling algorithm for disease detection. Working Paper 57, Harvard University Biostatistics Working Paper Series, 2008.

31.

Bebell

Pilcher

Dorsey

et al.

Acute HIV-1 infection is highly prevalent in Ugandan adults with suspected malaria. AIDS 2010; 24: 1945–1952.

32.

Stekler

Swenson

Coombs

et al.

HIV testing in a high-incidence population: is antibody testing alone good enough?

Clin Infect Dis 2009; 49: 444–453.

33.

Patel

Mackellar

Simmons

et al.

Detecting acute human immunodeficiency virus infection using 3 different screening immunoassays and nucleic acid amplification testing for human immunodeficiency virus RNA, 2006–2008. Arch Intern Med 2010; 170: 66–74.

34.

Langfeldt SA, Hughes-Oliver JM, Ghosh SK, et al. Optimal group testing in the presence of blockers. Technical Report, Institute of Statistics Mimeograph Series No. 2297. North Carolina University, Raleigh, NC, USA, 1997.

35.

Xie

Tatsuoka

Sacks

et al.

Group testing with blockers and synergism. J Am Stat Assoc 2001; 96: 92–102.

36.

Habtesllassie

Haines

Mwambi

et al.

Array-based schemes for group screening with test errors which incorporate a concentration effect. J Stat Plann Inference 2015; 167: 41–57.

37.

Bilder

Tebbs

Chen

. Informative retesting. J Am Stat Assoc 2010; 105: 942–955.

38.

Black

Bilder

Tebbs

. Group testing in heterogeneous populations by using halving algorithms. J R Stat Soc Ser C Appl Stat 2012; 61: 277–290.

39.

McMahan

Tebbs

Bilder

. Informative Dorfman screening. Biometrics 2012; 68: 287–296.

Supplementary Material

Please find the following supplemental material available below.

For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.

For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.

0.00 MB

0.22 MB

Improved matrix pooling

Abstract

Keywords

1 Introduction

2 Method

2.1 The properties of matrix pooling

Proposition 1

2.2 New design

2.3 The group testing algorithm using the design Am

Assumption 1

Assumption 2

Theorem 1

2.4 Comparison of the efficiency of the design Am and Mm

Theorem 2

2.5 Extension

3 Numerical results

3.1 Threshold and efficiency

3.2 Application to detect acute HIV infections

4 Discussion

Footnotes

Declaration of conflicting interests

Funding

Supplemental material

References

Supplementary Material

2.3 The group testing algorithm using the design A_m

2.4 Comparison of the efficiency of the design A_m and M_m