# Putative Positive Subjects

Select the pools that tested positive by clicking on the table above. The subjects that only belong to positive pools will be considered as putative positives, and those should be tested individually in stage two. In the table below, the putative positives will be highlighted in red.

# Overview

Pooled testing (also known as group testing or specimen pooling) has recently arisen as a promising scientific solution to the world-wide challenge of achieving widespread testing for individuals with SARS-CoV-2 infection in the face of substantial resource constraints. Pooled testing methods utilize constrained testing resources more efficiently by pooling specimens together, potentially allowing larger populations to be screened with fewer tests. The varying testing requirements and resource constraints due to the global nature of the pandemic calls for a pooling strategy that is simple (to aid implementation), flexible (to tailor to different testing needs), and yet efficient (screen more people with fewer tests). This online tool implements the HYPER method, which provides efficient pooling designs through achieving balance among the pools and subjects via hypergraph factorizations (see below). It is a two-stage design, where the subjects are assigned to different pools and the pools are tested in stage one. Then, in stage two, the subjects that only belong to positive pools are tested individually. The HYPER pooling designs are,

1. Easy to implement, even in laboratories without a robot pipetting facility, as specimen from each subject is split into $q=1,2$, or $3$ pools ($q=1$ corresponds to partitioning the set of subjects into equal sized pools, which can easily be done using just pencil and paper, and thus not included in this tool),
2. Flexible, as it can handle any number of subjects and vastly varying number of pools, and still produce maximally balanced designs (see below). Moreover, the result turnover time is substantially less than methods that require more than two stages of testing,
3. Efficient, especially when the vast majority of the population is disease-free, resulting in most of the pools to return negative results, and thus eliminating the need to test the subjects in those pools individually.

# Usage

Our tool provides maximally balanced pooling designs, i.e., one for which,

1. Each subject belongs to the same number of pools (two or three, specified on the left panel by user),
2. Number of subjects per pool is as uniform as possible,
3. Number of subjects in each pair/trio of pools is as uniform as possible.

## Generating the design

To generate the HYPER pooling design, start by selecting the number of pools each subject goes into ($q$) on the left panel. Then, select the number of testing pools ($m$) and the number of subjects per batch ($n$) to test. The table in the "Subjects" tab will show the IDs of the pools each subject should go into. This table can be downloaded in csv format, and can also be used as a checklist by either clicking on the rows, or on the "Mark completed" button above. To view which subjects are assigned to each pool, go to the "Pools" section under the "Results" tab. This table can also be downloaded in csv format to infer the putative positive subjects (see below) manually using a spreadsheet or pencil and paper.

## Inferring putative positives

After conducting the tests on the pools generated by our tool, the subjects that only belong to the positive pools are considered as putative positives, and are tested individually. To infer the putative positives based on the test results of the pools, go to the "Results" tab, and select the pools that tested positive in the "Pools" section. The table under the "Putative Positive Subjects" section will highlight the putative positive subjects in red, and also list those subject IDs below the table.

# Detailed method to generate the pooling design

The HYPER method is a two-stage pooling strategy that uses maximally balanced pools built on hypergraph factorizations. Stage one consists of testing pools of subjects to identify putative positives, who are tested individually in stage two. We illustrate the details via a toy example with $n=12$ individuals split into $q=2$ out of $m=6$ pools.

First, to create pools for stage one, we assign each individual to $q$ out of $m$ pools by cycling through an ordered list of ${m\choose q}=15$ possible pool combinations. The ordered list is generated in a way to ensure that there is no overlap among the combinations in each consecutive block of $m/q=3$ combinations. In our toy example (see the design above), the first three pool-pairs AB, CD, EF do not overlap, as with the next three BC, DF, AE, and so on. This ensures that the pool sizes as well as the pool combinations are balanced. Each pair in this example appears only once, and all pools contain four subjects. If instead we had $n=11$ subjects, the pools would no longer be perfectly uniform in size, since pools A and D would have only three subjects, but they would still be as uniform as possible. The same holds for any number of subjects, which makes the HYPER method extremely flexible in handling widely different testing needs.

## Hypergraph Factorization

To generate the ordered list of pool combinations as described above, the HYPER method utilizes a sophisticated mathematical technique called hypergraph factorization. We can think of each pool as one of $m$ vertices in a hypergraph, where each hyperedge is a set of $q$ out of the $m$ vertices. Each hyperedge will correspond to a potential set of pools into which any individual sample can be split. Putting together all ${m\choose q}$ hyperedges forms the so-called hypergraph $K_m^q$ of order $q$ on $m$ vertices. Any subset of the hyperedges that uses all vertices exactly once is called a $1$-factor of the hypergraph. Our objective here is to divide the ${m\choose q}$ hyperedges of $K_m^q$ into disjoint $1$-factors, i.e., 1-factors that do not have any hyperedge in common. The proof of existence and construction of such hypergraph factorization for $q>2$ require sophisticated mathematical techniques, which are described in the HYPER manuscript. However, the output is easy to use, and it is straight-forward to verify that the output designs are indeed maximally balanced. Here, we describe a construction technique for $q=2$ using $m=6$ pools as in the toy example above.

### Construction of hypergraph factorization for two-way split

To obtain the disjoint 1-factors of the hypergraph $K_m^q$ for $q=2$ and $m=6$, we start from the following "starter" diagram:

The edges of this diagram give the first 1-factor (AB, CD, EF), i.e., the first set of $m/q=3$ edges where each vertex appears exactly once. Then, we rotate the diagram anti clock-wise (can be done clock-wise as well) one step at a time, and each rotation will provide a 1-factor that is disjoint from the set of edges that appeared before.

In this example, rotating the diagram one step provides the 1-factor (BC, DF, AE), rotating two steps provides the 1-factors (AD, BE, CF), and so on until we get back to the starter diagram. Combining all of these 1-factors, we can obtain the complete hypergraph factorization of $K_m^q$ as AB, CD, EF, BC, DF, AE, AD, BE, CF, BD, AF, CE, BF, DE, AC. We can then cycle through this list to assign the individuals in order to achieve maximal balance as described above.