Optimal Configuration of a Square Array Group Testing Algorithm

Abstract

We consider the optimal configuration of a square array group testing algorithm (denoted A2) to minimize the expected number of tests per specimen. For prevalence greater than 0.2498, individual testing is shown to be more efficient than A2. For prevalence less than 0.2498, closed form lower and upper bounds on the optimal group sizes for A2 are given. Arrays of dimension 2 × 2, 3 × 3, and 4 × 4 are shown to never be optimal. The results are illustrated by considering the design of a specimen pooling algorithm for detection of recent HIV infections in Malawi.

Keywords:

• Blood testing
• Composite sampling
• HIV
• Matrix
• Pooled testing
• Screening

Mathematics Subject Classification:

• Primary 62K05
• Secondary 62P10

Acknowledgment

This work was supported by National Institutes of Health grants P30 AI50410-07 and R03 AI068450-01. The authors thank an anonymous reviewer for helpful comments and suggestions.

Notes

^† v is the smallest n ≥ 4 for which r ₁(n) > q.