Can we use binary search algorithm against corona?

1

Firstly, it is not a programming question. Cut to the chase, most of you know what is binary search algorithm. There are 2 ways of testing the individuals, one is PCR, and other is ELISA. PCR seems to be more definitive per Wikipedia. Is it possible to take samples from say, 100 ppl in a quarantine, and slice these samples and mix them to make one big sample (may be culture all slices together) and then test them with PCR. If it comes positive, we can say, there is at least one corona positive person in the group, now we divide all previously taken samples, group them into group A and B, we do in binary search, and take further slices off these samples and mix them and culture them in 2 different big samples, each of 50 ppl, now one group for example tests negative, then we can declare 50 people to be virus free. For the other group we rinse and repeat the method, finding more negative and positive groups, till we have narrowed down to the individuals. Can our current testing apparatus be modified to deal with mixed samples or is it already capable of. I am asking this question because non-programmer biologists and medics donā€™t seem to be having much clue about algorithms and how it may help them and us all.

PS: The usual protocol is for the ppl in the quarantine to develop symptoms and they are approved for testing,but the quarantines are not perfect, specifically in poorer countries and positive patients are infecting healthy people that have been quarantined with them. Also there are other groups, that may benefit from periodic testing, for example you can test all the doctors and paramedics in a given hospital almost every day.

2

binary search would be generally more efficient if you have n groups of people, of which each group has just one people to find
still, this require 100% right result from the test. but in case of biological testing one needs a yes/no answer for each sample, with repeated testing for each person.

doing real testing also needs to account for the statistical part of data elaboration.
you have also a limited sample amount, most often than not you can do 1/2 tests on the specific sample, and the test is destructive.

and it is not even a yes/no answer, but often a quantitative answer with a statistical elaboration

even if I have 8 solutions and I have to find which one has the searches species, need to find which one of the 8 have it. I
wouldnā€™t use binary search
because of: limited quantity of sample, once sample are mixed, they canā€™t be separated (in case I need to use the sample, and the test is not destructive), if I need quantitative test that would just make things more complex, concentration species change when mixing stuff, it can go lower than the testing technique limit

ELISA in particular use absorbanceā€¦ already one work with really small concentration and so absorbanceā€¦ diluting more could make it impossible to find anything

short answer, from analytic point of view, NOPE

EDIT: this rant doesnā€™t want to be 100% precise, it is just my knee-jerk reaction as a chemist, with a brief course on bio-analytical techniques on my shoulders, and too many on analytical chemistry in general

1 Like
3
  • Its practically impossible to perfectly quarantine a significant portion of a population.
  • I donā€™t believe tests work with multiple samples, and if they did and the test comes back positive, then what? You canā€™t isolate a significant portion people, so you have to re-test everyone again.
  • Testā€™s are not fool proof and diluting the virus with other samples would make it even harder to detect

Iā€™m not sure how a binary search will help against the COVID-19.

Binary search is used to find a specific value in a sorted array. It might be useful to find multiple numbers in a given array, or other use cases where you can leverage the limited amount of look ups. It canā€™t really be applied or used to help determine who is or isnā€™t sick, at least with your example. A key part of making a Binary search is building the sorted array for use later. This requires going over the entire array at least 1 time (n), which in the real world would mean testing 100% of everyone which isnā€™t close to practically possible, even in countries who are prepared for the outbreak.

Basically all sorting algorithms wouldnā€™t be of much help with COVID-19.

The most applicable ā€œcomputer science mathā€ I can think of that could be useful is something along the lines of tree traversal, but then you still need to define the edges (vectors of transmission) to build your graph. To build the edges you still need to know who has the virus, and who interacts with who.(which is almost impossible in the real world) It might be useful to trace transmissions between known cases to know ā€œhow many hopsā€ the virus has taken, again only if you know who caught it from who.

Other math like statistics is useful for projections, and other data modeling (like what is linked below) so we can determine what should be done when and where. But all of this comes back to real world limitations, like testing, equipment, and logistics.

Social distancing and limiting how much people move is currently very important in slowing the spread. Here is a fantastic article on how changes to humans behavior affect the spread of the virus. Namely reducing the speed of the spread is key to saving lives as it ā€œflattens the curveā€, where the health care system stays under capacity and thus provide the best care to its patients, rather then having a ton of sick people at the same time.

This isnā€™t true at all. The CDC, WHO and other health organizations around the globe all know about how to manage a crisis using math and science, its their job. A lot of smart people around the globe are focusing their efforts on finding solutions to all the problems the virus has brought up. A lot of measures currently being in place (like all the social distancing and shutting down of large gathers) are based in statistics.

The current biggest challenge for most countries (including the United States) is the lack of tests. If a country has enough tests and follows the correct protocols (along with the proper social distancing measures) they can significantly limit the spread simply due to being able to enact the correct measures in the right places at the right time for the right people. Information is power, and in scenarios like COVID-19 information will save lives.
Examples of countries that have been very prepared, would be South Korea (which has tested 240k+ people to date), and Taiwan (which has only a handful of cases), both of which have significant testing and protocol measures across the country which help identify and limit the viruses ability to spread.

Stay safe out there!

4

Think about a rack of test tubesā€¦it is like an arrayā€¦ An array is nothing but a block of memory, with contiguous cells. The computer does not know individually which cell has what value. In case of rack of test tubes,
an array would look like {0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0}. While a computer can sort the array, if it runs a pointer across, every value, but here the computer is the lab technician with limited time and number of tests. He cannot sort it like a computer would, and he cannot test each individual test tube for lack of test kits or whatever method. He can give a wholesale clearance to the entire test tube rack assuming a highly sensitive test exists, or if the sample can be viral cultured, which basically would multiply viruses, (how successful that would be is another question). If the test comes positive, he divides the tubes into two rows, and makes two mixed samples. Suppose one group tested negative (and the other positive.) You see, he needed only two tests to clear 50 people (we are assuming these 100 ppl are properly quarantined and cannot transmit virus to each other).

[quote] Testā€™s are [not fool proof] and diluting the virus with other samples would make it even harder to detect[/unquote].
If a virus enters our body, our immune system produces antibodies which suppresses the viral load, but this happens in vivo. Out there in vitro, there is no immune system and only a biologist can tell, how the virus would behave inside this giant sample. What if the situation is ideal and the virus is actually a stupid crook and multiplies inside the giant sample or if we can culture it using some viral culture method (like centrifuging cells from the pulmonary vessels of a healthy person and placing a layer of those cells on a slide inside this sample). (Remember these test tubes do not necessarily have to contain blood, it could be some other specimen as well).
It is like writing a computer program where you use some library function that sums all array elements, if the sum is greater than 0, the program thinks the array is infected and has bad values, 0 being the only good value. then the program divides the array into two sub-arrays, and again uses the sumfunction, and it gives the output 0, meaning one sub-array has all good values.

5

I do not destroy individual samples, I empty each test tube partly in a giant test tube, say, from each 10 ml test tube, i take may be 1-2 ml, into the giant test tube. And the virus may actually grow in a large sample given absence of antibodies (in healthy samples) in-vitro. This basically means the infected individual specimen may have the virus as well as antibodies, but content from other test tubes will not have antibodies, still i am just using common sense, i am not trained in biology. You can read my replies to the other member as well, which will elucidate what I mean, thanx.

6

There is your problem right there. Trained biologists know what will and will not work. You canā€™t common sense around not having a decade of foundational knowledge.

1 Like
7

I get youā€™re trying to be helpful, but

You seem to have contracted a novel form of Hacker News Commenter Virus (or possibly Elon Techbro Syndrome). Afaik, current medical advice is to cease programming activities & self-isolate from programming & tech-related media/communities for either:

  • ~12 weeks or
  • until you can resist the urge to reinvent non-programming processes based on CS101 subject material/first principles
3 Likes
8

Someoneā€™s got a serious case of Dunning Kruger Effect. It indicates treatment with repeated applications of a clue.

3 Likes
9

itā€™s a virus. It needs living cells to replicate. And it needs time.

The current tests are engineered to work from the collected sample, the virus presence or absence is directly detected, probably even quantitavely.

If there is also need to add culture timeā€¦ letā€™s think of steps:

  • create a repeatible good environment for virus reproduction
  • find the ideal time of culture
  • if everything goes well, after a few months, we can mix and grow samples.
  • now we can test if one of these 100 samples is contamined.
  • oh, test is positive! at least one is contamined!

Doctors: we actually needed to know if each of this specific samples is contamined!
The thing is, in these cases, there is need to know which is actually contamined. Would you be content to know that ā€œmaybe you have the virusā€?

To actually know how many samples are contamined, a binary search is pretty useless.

1 Like
10

@banetanason you posed a good question and I donā€™t know why these other people are bashing you. some of the comments are just chiding you. guys, this is not a stackoverflow thread, ok?

anyways, I signed up for a forum account to show this,
while everyone else is insulting your expertise and pretending to have expertise themselves, actual scientists have carried out the experimental method

itā€™s on medxriv. since this is a new account Iā€™m not allowed to post links. just google ā€˜inurl:medxriv covid 19 test binary searchā€™

11

Weā€™ll see if it pans out. Medxriv papers have not yet been peer reviewed, and and even peer reviewed ideas need to actually meet with reality in clinical trials. Just because there are preprint papers reviewing the mathematics of using sample pooling does not mean that in the end it will be practical or effective.

12

Thereā€™s a vast difference between just throwing out sciency-sounding terms and actually applying a scientific methodology that might happen to use one of those terms.

Anyway, I think everythingā€™s been said already.

1 Like