5 ms·

Why can't RT-PCR tests be used to detect virus in a sample mixed from a large number of individual samples? This would enable cheap and accurate mass testing, s

Why can't RT-PCR tests be used to detect virus in a sample mixed from a large number of individual samples? This would enable cheap and accurate mass testing, since you can find P positives from S samples with O(P*log(S/P)) tests. What's the catch?

tlb 7y ago
The main cost isn't per sample, it's the amount of time the machine takes to sequence enough fragments of RNA to achieve statistical significance. If you combine samples and want to not miss anything, you need to run it for longer.
- voidmain 7y ago
  Realtime PCR isn't sequencing. It increases the concentration of the targeted sequence exponentially, so it "should" take only logarithmically more temperature cycles to handle a smaller concentration of virus . If that is actually a big contributor to the testing cost, it would make the log in my analysis into a log^2.
yunesj 7y ago
There's no catch. It's called "pooling" and is used, e.g., to keep costs down for early detection of primary HIV infection.
mxwsn 7y ago
Just curious, can you expand a bit on the analysis? I see that by binary search you get O(log(S)) to identify a single positive, and naively rerunning search from the beginning P times yields O(P*log(S)). One can certainly do better by avoiding redundant tests but at some point one needs to start reasoning about the distribution of the positives in the samples and I'm not sure how to do that.
- daef 7y ago
  See https://youtu.be/GqAdVQeIXA0 https://youtu.be/GqAdVQeIXA0 for an explanation: starting at around 30% probability pooling stops making sense.
- mxwsn 7y ago
  Thought about it overnight and this is what I have: To reason about the distribution of positives in the sample, we consider two limiting cases, then interpolate between them. The cases are: 1. All positives are clustered exactly together. We start with log(S/P) queries to find the parent node of all positives, then test every node in the subtree with 2P-1 queries to identify all positives. In total, this is O(p + log(S/P)). 2. All positives are uniformly distributed. By the pigeonhole principle, the lowest level where every node tests positive must occur at log(P). Above this level, every node tests positive, so we must perform 2P-1 tests. Every P nodes on the level must be binary searched; each node has a subtree of height log(S/P), for Plog(S/P) operations. In total, this is O(P + Plog(S/P)) = O(Plog(S/P)). It is not immediately obvious that the worst case distribution is either case 1 or 2. To address this, we define an interpolation variable K in [0, 1] which describes a distribution where all positives begin clustered together, then KP positives are adversarially moved elsewhere. We claim that K = 0 is case 1 and K = 1 is case 2. Consider the case where KP = 1. As in case 1, we need 2P-1 + log(S/P) tests to fully identify the cluster; we also need a single binary search starting at the 2nd level corresponding to the other half of S, which takes log(S) - 1 operations, for a total of 2P-1+log(S/P)+log(S)-1. As KP increases, the level at which we transition from testing every node to initiating binary search on a node will decrease; as an example, when KP = 4, we fully test halves, then quarters, and then begin binary search. In general, we will need KPlog(S/KP) queries for all binary searches. Finally, no matter what KP is, we need no more than O(P) queries for subtrees where we need to test every node. This yields O(P + KPlog(S/KP)) This allows us to navigate around an adversary choosing the worst distribution of positives possible by taking the upper bound where K = 1, yielding O(P + Plog(S/P)) = O(Plog(S/P)), though this bound is not expected to be tight.

tlb 7y ago

The main cost isn't per sample, it's the amount of time the machine takes to sequence enough fragments of RNA to achieve statistical significance. If you combine samples and want to not miss anything, you need to run it for longer.

voidmain 7y ago
Realtime PCR isn't sequencing. It increases the concentration of the targeted sequence exponentially, so it "should" take only logarithmically more temperature cycles to handle a smaller concentration of virus . If that is actually a big contributor to the testing cost, it would make the log in my analysis into a log^2.

yunesj 7y ago

There's no catch. It's called "pooling" and is used, e.g., to keep costs down for early detection of primary HIV infection.

mxwsn 7y ago

Just curious, can you expand a bit on the analysis? I see that by binary search you get O(log(S)) to identify a single positive, and naively rerunning search from the beginning P times yields O(P*log(S)). One can certainly do better by avoiding redundant tests but at some point one needs to start reasoning about the distribution of the positives in the samples and I'm not sure how to do that.

daef 7y ago
See https://youtu.be/GqAdVQeIXA0 https://youtu.be/GqAdVQeIXA0 for an explanation: starting at around 30% probability pooling stops making sense.
mxwsn 7y ago
Thought about it overnight and this is what I have: To reason about the distribution of positives in the sample, we consider two limiting cases, then interpolate between them. The cases are: 1. All positives are clustered exactly together. We start with log(S/P) queries to find the parent node of all positives, then test every node in the subtree with 2P-1 queries to identify all positives. In total, this is O(p + log(S/P)). 2. All positives are uniformly distributed. By the pigeonhole principle, the lowest level where every node tests positive must occur at log(P). Above this level, every node tests positive, so we must perform 2P-1 tests. Every P nodes on the level must be binary searched; each node has a subtree of height log(S/P), for Plog(S/P) operations. In total, this is O(P + Plog(S/P)) = O(Plog(S/P)). It is not immediately obvious that the worst case distribution is either case 1 or 2. To address this, we define an interpolation variable K in [0, 1] which describes a distribution where all positives begin clustered together, then KP positives are adversarially moved elsewhere. We claim that K = 0 is case 1 and K = 1 is case 2. Consider the case where KP = 1. As in case 1, we need 2P-1 + log(S/P) tests to fully identify the cluster; we also need a single binary search starting at the 2nd level corresponding to the other half of S, which takes log(S) - 1 operations, for a total of 2P-1+log(S/P)+log(S)-1. As KP increases, the level at which we transition from testing every node to initiating binary search on a node will decrease; as an example, when KP = 4, we fully test halves, then quarters, and then begin binary search. In general, we will need KPlog(S/KP) queries for all binary searches. Finally, no matter what KP is, we need no more than O(P) queries for subtrees where we need to test every node. This yields O(P + KPlog(S/KP)) This allows us to navigate around an adversary choosing the worst distribution of positives possible by taking the upper bound where K = 1, yielding O(P + Plog(S/P)) = O(Plog(S/P)), though this bound is not expected to be tight.