グループテスト
The Annals of Mathematical Statistics 28 (4): 1033–1036. doi:10.1214/aoms/1177706807.
↑ Sobel, Milton; Groll, Phyllis A. (September 1959). “Group testing to eliminate efficiently all defectives in a binomial sample”. Bell System Technical Journal 38 (5): 1179–1252. doi:10.1002/j.1538-7305.1959.tb03914.x.
↑ Li, Chou Hsiung (June 1962). “A sequential method for screening experimental variables”. Journal of the American Statistical Association 57 (298): 455–477. doi:10.1080/01621459.1962.10480672.
↑ Katona, Gyula O.H. (1973). “A survey of combinatorial theory”. Combinatorial Search Problems (North-Holland, Amsterdam): 285–308.
1 2 3 4 Hwang, Frank K. (September 1972).
In general, the number of tests required in the Bernoulli noise case is a constant factor larger than in the noiseless case.
Aldridge, Baldassini and Johnson (2014) produced an extension of the COMP algorithm that added additional post-processing steps. They showed that the performance of this new algorithm, called DD, strictly exceeds that of COMP, and that DD is 'essentially optimal' in scenarios where d 2 ≥ n {\displaystyle d^{2}\geq n} , by comparing it to a hypothetical algorithm that defines a reasonable optimum. The performance of this hypothetical algorithm suggests that there is room for improvement when d 2 < n {\displaystyle d^{2}<n} , as well as suggesting how much improvement this might be.
数学の多くの分野とは異なり、グループテストの起源は、Robert Dorfmanという1人の人物が書いた1つの報告書に遡ることができる。第二次世界大戦中に、アメリカ公衆衛生局とセレクティブ・サービス・システムが, 入隊者の中から梅毒の男性全員を排除する大規模プロジェクトに着手したときにその動機が生じた。梅毒について個人を検査するには、血液サンプルを採取して, それを分析する必要がある。当時、この検査には費用がかかり、すべての兵士を個別に検査することは非常に費用がかかり、非効率的だった。
Supposing there are n {\displaystyle n} soldiers, this method of testing leads to n {\displaystyle n} separate tests. If a large proportion of the people are infected then this method would be reasonable.
(In this context, a column A is said to contain a column B if for every index where B has a 1, A also has a 1.)
A useful property of d {\displaystyle d} -disjunct testing matrices is that, with up to d {\displaystyle d} defectives, every non-defective item will appear in at least one test whose outcome is negative. This means there is a simple procedure for finding the defectives: just remove every item that appears in a negative test.
“Sharper bounds in adaptive group testing”. Taiwanese Journal of Mathematics 4 (4): 669–673. doi:10.11650/twjm/1500407300.
1 2 3 4 Aldridge, Matthew; Baldassini, Leonardo; Johnson, Oliver (June 2014). “Group Testing Algorithms: Bounds and Simulations”. IEEE Transactions on Information Theory 60 (6): 3671–3687. arXiv:1306.6438. doi:10.1109/TIT.2014.2314472.
↑ Baldassini, L.; Johnson, O.; Aldridge, M. (1 July 2013), “2013 IEEE International Symposium on Information Theory”, IEEE International Symposium on Information Theory: pp. 2676–2680, arXiv:1301.7023, doi:10.1109/ISIT.2013.6620712, ISBN 978-1-4799-0446-4
↑ Sobel, Milton; Elashoff, R. M. (1975). “Group testing with a new goal, estimation”.
(February 2006). “A new compressive imaging camera architecture using optical-domain compression”. Electronic Imaging. Computational Imaging IV 6065: 606509–606509–10. Bibcode: 2006SPIE.6065...43T. doi:10.1117/12.659602.
↑ Candès, E. J. (2014). "Mathematics of sparsity (and a few other things)". Proceedings of the International Congress of Mathematicians. Seoul, South Korea.
1 2 Gilbert, A. C.; Iwen, M. A.; Strauss, M. J. (October 2008). "Group testing and sparse signal recovery". 42nd Asilomar Conference on Signals, Systems and Computers: 1059–1063. Institute of Electrical and Electronics Engineers.
↑ Wright, S. J.; Nowak, R. D.; Figueiredo, M. A. T. (July 2009). “Sparse Reconstruction by Separable Approximation”.
There are endless ways to continue remixing the basic formula of group testing. The following elaborations will give an idea of some of the more exotic variants. In the 'good–mediocre–bad' model, each item is one of 'good', 'mediocre' or 'bad', and the result of a test is the type of the 'worst' item in the group. In threshold group testing, the result of a test is positive if the number of defective items in the group is greater than some threshold value or proportion. Group testing with inhibitors is a variant with applications in molecular biology. Here, there is a third class of items called inhibitors, and the result of a test is positive if it contains at least one defective and no inhibitors.
SCOMP (Sequential COMP) is an algorithm that makes use of the fact that DD makes no mistakes until the last step, where it is assumed that the remaining items are non-defective. Let the set of declared defectives be K {\displaystyle K} . A positive test is called explained by K {\displaystyle K} if it contains at least one item in K {\displaystyle K} . The key observation with SCOMP is that the set of defectives found by DD may not explain every positive test, and that every unexplained test must contain a hidden defective.
The algorithm proceeds as follows.
Origami assays provided a workaround for this construction problem by providing paper templates to guide the technician on how to allocate patient samples across the test wells.
Using the largest group testing designs (XL3) it was possible to test 1120 patient samples in 94 assay wells. If the true positive rate was low enough, then no additional testing was required.
One of the key insights in non-adaptive group testing is that significant gains can be made by eliminating the requirement that the group-testing procedure be certain to succeed (the "combinatorial" problem), but rather permit it to have some low but non-zero probability of mis-labelling each item (the "probabilistic" problem). It is known that as the number of defective items approaches the total number of items, exact combinatorial solutions require significantly more tests than probabilistic solutions — even probabilistic solutions permitting only an asymptotically small probability of error.
In this vein, Chan et al.
Finally, when 0 ≠ d ≠ n {\displaystyle 0\neq d\neq n} , there is at least one item whose defectiveness must be determined (by at least one test), and so 1 ≤ t ( d , n ) {\displaystyle 1\leq t(d,n)} .
In summary (when assuming 0 ≠ d ≠ n {\displaystyle 0\neq d\neq n} ), 1 ≤ t ( d , n ) ≤ t ̄ ( d , n ) ≤ n {\displaystyle 1\leq t(d,n)\leq {\bar {t}}(d,n)\leq n} .