群試檢驗演算法的相關數學模型探討

Mathematical Models Related to Group Testing Algorithms

曾如汶(Ju-Wen Tseng)

指導教授 ： 翁志文

國立交通大學/理學院/應用數學系暨研究所/碩士(2012年)

https://doi.org/10.6842/NCTU.2012.00275

摘要

考慮一包含n個待測物，且最多有d個呈陽性的集合。我們的目的是藉由群試設計的概念找出所有呈陽性的待測物。一個群試設計含有多個測試，每個測試都包含兩個以上的待測物。我們探討群試設計的目的是去減少測試的個數和階段數。而在同一個階段裡的測試可同時執行。
我們修改並且分析了一個適用於在已知最多二個陽性物的情況下的二階段群試檢驗演算法。此演算法的測試次數是O(3log n)。

關鍵字

群試檢驗

並列摘要

Consider a set of n items which has at most d positive items. Our aim is to find all positive items by using the concept of group testing. A group testing consists of a few tests, each of them containing more than one item. The objective in the study of group testing is to reduce the number of test times and to reduce the number of stages which partition the tests into different time slots.

By group testing, each test contains more than one items in order to reduce the number of test times. And these tests often can be conducted simultaneously.
indent We modify and analysis a group testing algorithm, which has 2-stage for the case d=2 and the test number of this algorithm is
O(3log n).

並列關鍵字

group testing

參考文獻

Jun Guo and Kaishun Wang, "A construction of pooling designs with surprisingly high

A.J. Macula, A simple construction of $d$-disjunct matrices with certain constant weights, Discrete Math. 162 (1996) 311-

1.

D.Z.Du and F.K.Hwang, Pooling designs and nonadaptive group testing: important tools for DNA sequencing, World Scientific Publishong Company, 2006.

2.