Merkle and Binary Tree Inspired Method for Accelerated COVID-19 Testing: A Concept

Before we start explaining our model, which is fairly simple for anyone out there. We’d like to bring an important concept here which is extremely important at the first place, for our solution to be viable. It is the concept of Pooling. While the term is fairly simple by it’s mere meaning, it has been involved in a breakthrough concept recently which is what we start this article with. In March-2020, Israeli Researchers at Technion and Rambam announced a new faster testing method that could expand the testing prowess of COVID-19. They extended prior experience with a “Pooling” technique which was used in Africa to test blood for HIV. They adapted this method to test for the novel Coronavirus which is the cause for the disease COVID-19. Since, most of the testing in the world right now is being conducted one individual at a time. This takes a huge toll on resources like time and also places a huge tax on critical equipment that are being used while conducting these tests. Here’s the catch. Their “Pooling Protocol” makes it possible to test up to 64 individuals at the same time which is pretty great, right?

Now, here’s our part to play. We formulated a conceptual model which if in case turns out to be correct will make a drastic change in COVID-19 testing which is what our model’s goal is. Our model is simple and easy enough to understand even for a non-technical person. However, it won’t be a good idea to put all the details in here. For brevity, we’d like to simplify the concept and try to make it clear and concise.

Our model

Our model has two phases:

1. The Sampling phase (Bottom-Up approach)
2. The Testing Phase (Top-down Approach)

In the Sampling Phase, we leveraged the concept of Merkle trees which combines individual samples and group them in two’s until we reach the Root, which we call the Merkle Root in our case. (We assume that multi-level pooling is possible without contaminating the samples, if that is the right term to use).

The General Figure for Sampling and Testing

We then move to the Testing procedure where we leveraged Binary Trees. We’ve a detailed algorithm for the testing procedure. But let’s not get into that here and consider a small case where we minimize the number of tests required to be carried out if the pooled sample is found positive.

The Case of 16 individuals where only one is positive. Red(Positive) and Green(Negative)

Consider 16 individuals whose samples are collected and we have no prior knowledge about who the positive patient is. We group the samples in Bottom up manner as mentioned in the sampling section until a common root is formed(Merkle Root).

Then, the testing procedure(Top-down approach) works as follows.

The Root is checked first, if found positive then we move one level down. We test both the children. If both are found positive, we stop our testing procedure and do it the traditional way. i.e., by testing all samples individually. If only one among the two is positive, we discard the subtree which is negative and follow the positive one and move another level down in that subtree. We repeat the procedure until leaves are found.

Figure for 16 individuals where only one is infected.

It is clear from the figure that in this case of 16 individuals, 16 tests were to be conducted by the traditional method. But with our model only 9 tests are to be conducted to successfully trace out the patient. (T1, T2,…,T9 represent tests that are to be done in that manner to trace out the infected individual). It is evident from this small example that we’ve reduced the complexity by almost half. We’ve conducted a thorough analysis of our conceptual under various cases and have analysed the best and worst cases for our model. It is to bring into the notice that no practical experiment have been carried out under this model as yet and there’s no evidence that supports it. However, we have to consider the fact that if this model is to be tested in practice. It should be done under the observation and supervision of a scientist who is an expert of the subject matter because experiments like this depends on various factors which might ruin it: like the controlled environment, calibration and precision. But we believe if our model proves to be correct, it’ll have some serious implications on the COVID-19 testing. We also believe that if this concept proves to be correct in various regards, the process can be further improved by the categorization/grouping of individuals based on their travel history, type of contact and severity of symptoms.

A much detailed explanation can be found in the original preprint. Our preprint is available on ResearchGate and can be found here:

We’d love feedback from every individual in this regard for the greater good. For any queries and suggestions, reach out to ahl@nitsri.net

It is a joint work by Aaqib Bashir, Muzafar Ahmad Wani, Auqib Lone and Prof. Roohie Naaz