Тестирование на инфекции с меньшим количеством тестов, чем у людей
С COVID-19, доминирующим в мировом масштабе, и когда я был программистом, я чувствовал, что у меня нет ничего, что могло бы повлиять на ситуацию. В конце концов, я ничего не знаю о биологии или стратегиях реагирования на пандемию. Я не биолог, эпидемиолог или статистик.
Однако есть кое-что, о чем я знаю:
- деревья двоичного поиска
- быстрая сортировка
- разделяй и властвуй алгоритмы
Так получилось, что у нас много людей и очень мало тестов. Можно ли использовать некоторые из этих методов информатики для тестирования большего числа людей?
Здесь я опишу стратегию тестирования, при которой удается протестировать N человек при выполнении менее N тестов. Цель - назначить каждому человеку положительные и отрицательные результаты.
Он делает несколько предположений, которые, учитывая отсутствие у меня полномочий, я не знаю, верны они или нет. Я был бы рад, если бы какие-либо эксперты могли высказать свое мнение по поводу этих предположений:
- образцов больше, чем тестов
- образцы могут быть объединены таким образом, что, если какой-либо образец положительный, комбинация дает положительный результат.
С этого момента мы будем принимать эти предположения как должное.
Эта стратегия тестирования состоит из нескольких этапов:
Этап 1: выборка
При отборе образцов у людей вы должны брать много образцов, а не только 1. Предположим, что мы сейчас берем по 11 образцов у каждого человека.
Этап 2: сегментация
Сегмент - это подмножество вашего населения. Эта схема тестирования будет проводиться для каждого сегмента населения. Поскольку у нас есть 11 образцов на человека, максимальный размер сегмента составляет (11 — 1)² = 1024. Рандомизируйте популяцию на сегменты этого размера.
Этап 3. Тестирование
Для каждого сегмента следуйте этому рекурсивному алгоритму:
1: объедините по одной выборке от каждого человека в сегменте
2: проверьте объединенный образец на вирус
3a: если он отрицательный, остановить: все в сегменте отрицательны
3b: если он положительный, разделите сегмент размера N на 2 подсегмента размера N / 2, вернитесь к шагу 1 для обоих подсегментов
Повторяйте этот процесс разветвления пополам, пока вы не протестируете сегменты размера 1, или остановитесь на шаге 3a для всех ветвей. Глубина дерева никогда не превышает log2(segment-size) + 1, поэтому достаточно 11 образцов на человека.
Чтобы определить эффективность этого подхода, я написал быстрый скрипт Scala, чтобы опробовать его:
При соотношении 0,167 (или 16,7% инфицированного населения) он, кажется, безубыточен с использованием около 1024 тестов для тестирования 1024 человек. По крайней мере, для меня удивительно то, что точка безубыточности 16,7% кажется магическим числом, которое является точкой безубыточности для любого размера сегмента на основе эмпирического тестирования.
Если процент инфицированных выше, то эта схема тестирования на самом деле хуже, чем простое тестирование одного человека за раз. Однако, если процент ниже, то в конечном итоге вам потребуется меньше тестов, чем размер сегмента.
Вот несколько примеров тестов, необходимых для данной скорости заражения в сегменте размером 1024:
16,7%: ~ 1024 тестов
15%: ~ 959 тестов
5%: ~ 466 тестов
1%: ~ 137 тестов
инфицирован ровно 1 человек: ровно 21 анализ
никто не заразился: ровно 1 тест
Очевидно, такая схема экономит больше на тестах, если процент заражений в вашем сегменте меньше. Это говорит мне о том, что мы могли бы использовать эту схему для популяций, которые, как мы знаем, имеют низкий уровень инфицирования, и только для людей, у которых нет симптомов и которые не знают, что контактируют с людьми, у которых есть симптомы или у которых есть положительный результат теста.
Еще одна интересная вещь, которую следует отметить, заключается в том, что вы можете начать тестирование случайным образом, одно за другим, и когда у вас есть высокая степень уверенности в уровне заражения, переключитесь на эту схему, если уровень значительно ниже 16,7%. Итак, представьте, что у вас есть образцы от миллионов людей. Если вы случайным образом протестируете, скажем, 2000 из них по отдельности, у вас будет приличная степень уверенности в том, что уровень заражения значительно ниже 16,7%.
Возможно, эта стратегия тестирования совершенно бесполезна. Может быть, предположения не соответствуют действительности, возможно, невозможно собрать и обработать такое количество образцов, может быть, на получение результатов потребуется слишком много времени. Есть много причин, по которым это может не сработать. Однако мы не продвигаемся вперед, сомневаясь в себе. Мы движемся вперед, мыслим нестандартно, пока не доберемся до чего-то ценного. Я призываю всех подумать о том, что они могут сделать для решения проблем, с которыми сталкиваются вы и другие люди, как большие, так и маленькие.
