In the group testing problem we aim to identify a small number of infected individuals within a large population. We avail ourselves to a procedure that can test a group of multiple individuals, with the test result coming out positive iff at least one individual in the group is infected. With all tests conducted in parallel, what is the least number of tests required to identify the status of all individuals? In a recent test design [ 2016] the individuals are assigned to test groups randomly, with every individual joining an equal number of groups. We pinpoint the sharp threshold for the number of tests required in this randomised design so that it is information-theoretically possible to infer the infection status of every individual. Moreover, we analyse two efficient inference algorithms. These results settle conjectures from [ 2014, 2019].
The most interesting regime for the group testing problem is when the number @math of infected individuals scales as a power @math of the entire population. Mathematically this is because in the linear regime @math the optimal strategy is to perform @math individual tests @cite_6 . Thus, for @math linear in @math there is nothing interesting to do. But the sublinear case is also of practical relevance, as witnessed by Heap's law in epidemiology @cite_42 or biological applications @cite_23 .
@cite_42 @cite_23 @cite_6
2085816609 2784892334
Power-law distributions have been observed in a wide variety of areas. To our knowledge however, there has been no systematic observation of power-law distributions in chemoinformatics. Here, we present several examples of power-law distributions arising from the features of small, organic molecules. The distributions of rigid segments and ring systems, the distributions of molecular paths and circular substructures, and the sizes of molecular similarity clusters all show linear trends on log-log rank frequency plots, suggesting underlying power-law distributions. The number of unique features also follow Heaps'-like laws. The characteristic exponents of the power-laws lie in the 1.5-3 range, consistently with the exponents observed in other power-law phenomena. The power-law nature of these distributions leads to several applications including the prediction of the growth of available data through Heaps' law and the optimal allocation of experimental or computational resources via the 80 20 rule. More importantly, we also show how the power-laws can be leveraged to efficiently compress chemical fingerprints in a lossless manner, useful for the improved storage and retrieval of molecules in large chemical databases. We consider nonadaptive probabilistic group testing in the linear regime, where each of n items is defective independently with probability p in (0,1), where p is a constant independent of n. We show that testing each item individually is optimal, in the sense that with fewer than n tests the error probability is bounded away from zero.