5 ms·

Germany decided to mix 10 specimens and run a test, only then - if positive - test individual samples. They increased their testing capacity 10x (roughly) overn

Germany decided to mix 10 specimens and run a test, only then - if positive - test individual samples. They increased their testing capacity 10x (roughly) overnight. https://edition.cnn.com/world/live-news/coronavirus-pandemic-03-31-20/h_c9b8259b105b4f26a4ade9fb61b954ce https://edition.cnn.com/world/live-news/coronavirus-pandemic...

rplnt 7y ago
There was a study, IIRC from Israel, which said this is still reliable with 64 samples mixed. The next question is, do you need to test the individual samples then? Not sure how much available material for testing you have, but you might be able to just divide the mix to eliminate bigger groups first. Or even mix parts with new samples. There must be an ideal procedure (throughput-wise) if you know how the range of positives to expect.
- buboard 7y ago
  That works well for low infection rates https://www.biorxiv.org/content/10.1101/2020.04.03.024216v1.article-info https://www.biorxiv.org/content/10.1101/2020.04.03.024216v1.... https://www.medrxiv.org/content/10.1101/2020.04.05.20054445v1 https://www.medrxiv.org/content/10.1101/2020.04.05.20054445v...
- douglaswlance 7y ago
  You can do a binary search to efficiently locate the positive sample.
  - ced 7y ago
    But what if there are two (or more?) positive samples? It's an interesting problem.
    - bequanna 7y ago
      If the initial test size is 64 and contains a positive, split into two groups of 32 and test each. Continue splitting and testing when a positive is encountered.
      - ced 7y ago
        Yeah, but this version is not necessarily optimal. If you have 4 positive samples, then you will test 2+2+1+1+1+1 = 8, instead of 4 in the naive case. It feels like a problem for information theory.
        bequanna 7y ago
        I didn’t say it was optimal, but it is a huge improvement on doing 64 tests for 64 samples.
        ced 7y ago
        Oh, sure!
    - gnulinux 7y ago
      You keep binary searching each part. I.e. if both 32/32 subsamples turn positive, you perform binary search on those 32 samples.
  - timerol 7y ago
    Note that optimal branch factor would probably depend on the expected negative rate. If 98% of your samples are coming back negative, it may be more optimal to divide by into 4 or 8 groups instead of 2 groups.
phreeza 7y ago
https://en.wikipedia.org/wiki/Group_testing https://en.wikipedia.org/wiki/Group_testing
irishloop 7y ago
It's only tenfold if they all test negative, right? Otherwise you need to test subgroups to find out which test(s) were positive. So the real speedup is probably something like 2x-4x, depending on infection rates.
- gnulinux 7y ago
  Currently in the US ~85% of tests turn negative. If sample turned positive you'd perform 10% more tests (1 extra test for each 10 tests) i.e. x1.1. If it turned negative you'd perform 10% the tests you'd normally perform without this scheme i.e. x0.1. In this case .85 of tests would be .1 of what they're now. The rest of .15 will be 1.1 of what they're now. So if US did this, they would be testing ~x.3 of their current testing. This seems huge. Can someone check my math please.
  - timerol 7y ago
    This isn't accounting for combinatorial math. If each sample is negative 85%, then the probability that all 10 samples are negative is 0.85^10, or about 20%. If any sample turned positive (the other 80% of the time), then all will need to be retested. Instead of 1 test per sample, you're now running 0.2 * 0.1 + 0.8 * 1.1, or about 0.9 tests per sample. You've increased throughput by 10%, but not nearly as much as was hoped. Note that these numbers get more favorable with more negative tests, though. The general formula is (r^x) * (1/x) + (1 - r^x) * (1 + 1/x), where r is the percentage of negative tests and x is the number to mix. With an 85% negative rate, it's more beneficial to mix 3 tests at a time for 0.72 tests per sample. (2 samples gives 0.78 tests, 4 gives 0.73) As more samples come back negative it becomes more advantageous to mix more, but you shouldn't mix 10 tests at a time (as opposed to 9) till you get to about a 96% negative rate, at which point you're running 0.44 tests per sample. Edit: The binary search algorithm mentioned elsewhere would probably be more optimal, but I'm gonna do my day job instead of figuring out the dynamics of that one.
    - gnulinux 7y ago
      Ah I see, yes I agree.

rplnt 7y ago

There was a study, IIRC from Israel, which said this is still reliable with 64 samples mixed. The next question is, do you need to test the individual samples then? Not sure how much available material for testing you have, but you might be able to just divide the mix to eliminate bigger groups first. Or even mix parts with new samples. There must be an ideal procedure (throughput-wise) if you know how the range of positives to expect.

buboard 7y ago
That works well for low infection rates https://www.biorxiv.org/content/10.1101/2020.04.03.024216v1.article-info https://www.biorxiv.org/content/10.1101/2020.04.03.024216v1.... https://www.medrxiv.org/content/10.1101/2020.04.05.20054445v1 https://www.medrxiv.org/content/10.1101/2020.04.05.20054445v...
douglaswlance 7y ago
You can do a binary search to efficiently locate the positive sample.
- ced 7y ago
  But what if there are two (or more?) positive samples? It's an interesting problem.
  - bequanna 7y ago
    If the initial test size is 64 and contains a positive, split into two groups of 32 and test each. Continue splitting and testing when a positive is encountered.
    - ced 7y ago
      Yeah, but this version is not necessarily optimal. If you have 4 positive samples, then you will test 2+2+1+1+1+1 = 8, instead of 4 in the naive case. It feels like a problem for information theory.
      - bequanna 7y ago
        I didn’t say it was optimal, but it is a huge improvement on doing 64 tests for 64 samples.
        ced 7y ago
        Oh, sure!
  - gnulinux 7y ago
    You keep binary searching each part. I.e. if both 32/32 subsamples turn positive, you perform binary search on those 32 samples.
- timerol 7y ago
  Note that optimal branch factor would probably depend on the expected negative rate. If 98% of your samples are coming back negative, it may be more optimal to divide by into 4 or 8 groups instead of 2 groups.

phreeza 7y ago

https://en.wikipedia.org/wiki/Group_testing https://en.wikipedia.org/wiki/Group_testing

irishloop 7y ago

It's only tenfold if they all test negative, right? Otherwise you need to test subgroups to find out which test(s) were positive. So the real speedup is probably something like 2x-4x, depending on infection rates.

gnulinux 7y ago
Currently in the US ~85% of tests turn negative. If sample turned positive you'd perform 10% more tests (1 extra test for each 10 tests) i.e. x1.1. If it turned negative you'd perform 10% the tests you'd normally perform without this scheme i.e. x0.1. In this case .85 of tests would be .1 of what they're now. The rest of .15 will be 1.1 of what they're now. So if US did this, they would be testing ~x.3 of their current testing. This seems huge. Can someone check my math please.
- timerol 7y ago
  This isn't accounting for combinatorial math. If each sample is negative 85%, then the probability that all 10 samples are negative is 0.85^10, or about 20%. If any sample turned positive (the other 80% of the time), then all will need to be retested. Instead of 1 test per sample, you're now running 0.2 * 0.1 + 0.8 * 1.1, or about 0.9 tests per sample. You've increased throughput by 10%, but not nearly as much as was hoped. Note that these numbers get more favorable with more negative tests, though. The general formula is (r^x) * (1/x) + (1 - r^x) * (1 + 1/x), where r is the percentage of negative tests and x is the number to mix. With an 85% negative rate, it's more beneficial to mix 3 tests at a time for 0.72 tests per sample. (2 samples gives 0.78 tests, 4 gives 0.73) As more samples come back negative it becomes more advantageous to mix more, but you shouldn't mix 10 tests at a time (as opposed to 9) till you get to about a 96% negative rate, at which point you're running 0.44 tests per sample. Edit: The binary search algorithm mentioned elsewhere would probably be more optimal, but I'm gonna do my day job instead of figuring out the dynamics of that one.
  - gnulinux 7y ago
    Ah I see, yes I agree.