利用搜尋隱藏圖作組合群試問題的研究

A Study of Complex Group Testing via Learning Hidden Graphs

施智懷(Chih-Huai Shih)

指導教授 ： 傅恆霖

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

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

摘要

在傳統群試(classical group testing) 裡，給定一個群體N 和一
個收集所有正物質的未知子集合D，其目標是通過詢問“N 中的一個子集是否包含一個正物質” 來確定D。這個問題已經被應用在很多領域且產生不同型態的模型跟問題，例如組合群試(complex group testing)、門檻群試(threshold group testing)和群試抑制模型(Inhibitor model)。
一般而言，群試演算法可以大致歸類成兩種類型: 逐步型(sequential) 和非調整型(non-adaptive)。逐步演算法中的測試是逐一進行的，而且每個測試是可以依據前面的測試結果來設計。非調整型演算法中的所有測試一開始就已經決定，因此每個測試的設計過程彼此互相獨立，雖然整體來看還是要具備有好的性質。介於逐步和非調整型演算法之間，還有一種s 階段的演算法，其中各階段是逐步的，而每階段中的試驗是同步
的。
組合群試可以設定成通過邊檢測試驗來重建隱藏超圖的問題，其中每一個試驗給的訊息是一組點的子集合是否包含圖形中的一條邊。在本論文中，我們首先重建一些有特別結構的隱藏圖，包含漢米爾頓圈(Hamiltonian cycle)、配對圖(matching)、星圖(star) 或局部完全圖(clique)。我們提供需要較少試驗次數的逐步演算法，然後提供新的理論下界並給出
一個具有高效率的逐步算演算法來重建n 個頂點和m 條邊的一般圖。最後，我們擴展一般圖的結果，並提供一個逐步演算法來重建隱藏的r-均衡超圖。
在應用面來說，重建隱藏超圖有助於我們解決門檻群試問題。本文中，我們的方法是藉由重建超圖來解決沒有間隙的門檻問題，且此方法已經達到理論下界。我們也可以考慮門檻群試在k-抑制模型上的問題，這是一種由門檻群試和抑制模型自然結合而成的模型。然後，我們提供非調整型演算法去克服此種模型，且允許試驗錯誤的發生。此外，我們提供了一個兩
階段的演算法，以確定所有的抑制物，並找到正物質集合的一個g-逼近集S。此種S滿足|SD|<=g和|SD|<=g，這裡的g表示門檻的距離、D為收集所有正物質的子集合。

關鍵字

搜尋隱藏圖 ； 組合群試 ； 抑制模型

並列摘要

In classical group testing, one is given a population N and an unknown subset DN of positive items, and the goal is to determine D by asking queries of the type ``whether a subset of N contains a positive item". The problem has been applied to many fields and generates different type of models and problems, such as complex group testing, threshold group testing, and the inhibitor model.

In general, group testing algorithm can be roughly classified into two types: sequential and nonadaptive. A sequential (or adaptive) algorithm conducts tests sequentially and each test may depend on the outcome of previous tests. A nonadaptive algorithm designs all the tests beforehand and thus each test is independent of the outcomes of other tests. Between the sequential and nonadaptive algorithms, there are the s-stage algorithms where stages are sequential and tests in a stage are parallel.

The complex model of group testing can be formulated as a problem of learning a hidden hypergraph by edge-detecting queries, each of which tells whether a set of vertices induces an edge of the hidden graph or not. In this thesis, we first reconstruct some hidden graphs of particular structure, including Hamiltonian cycles, matchings, stars, and cliques. We provide fully adaptive algorithms that reduce the number of queries needed. Then we provide a new information-theoretic lower bound and give a more efficient adaptive algorithm to learn a general graph with n vertices and m edges in mlogn + 10m + 3n edge-detecting queries. Finally, we extend the result of general graphs and provide an adaptive algorithm to learn a hidden r-uniform hypergraph with n vertices and m edges in mr(logn + 1)+(r+1)m+m^{r-1}+2^{(r+2)/2}r^{r}m^{r/2} edge-detecting queries.

On the application issue, learning a hidden hypergraph is helpful for us to solve the threshold group testing problem. In this thesis, we apply the strategy used in reconstructing a hidden hypergraph to the threshold group testing problem without gap, showing that up to d positive elements among n given elements can be determined by using O(dlogn) queries, with a matching lower bound. We can also consider threshold group testing on k-inhibitor model, which is a natural combination of threshold group testing and inhibitor model. Then we provide nonadaptive algorithms to conquer the threshold group testing on k-inhibitor model where error-tolerance is considered. Furthermore, we provide a two-stage algorithm to identify all inhibitors and find a
g-approximate set S. Note that S is g-approximate set if and only if |SD|<=g and |SD|<=g where g is the gap and D is the set of positive items.

並列關鍵字

learning hidden graph ； complex group testing ； inhibitor model

參考文獻

[1] Aigner, M.: Combinatorial Search. John Wiley and Sons (1988)

[2] Alon, N., Asodi, V.: Learning a hidden subgraph. SIAM J. Discrete Math. 18, 697-712 (2005)

[4] Anderson, I.: Combinatorial Designs: Construction Methods. Ellis Hor- wood (1990)

[6] Angluin, D., Chen, J.: Learning a hidden graph using O(log n) queries per edge. J. Comput.

closing in whole genome shotgun sequencing, Proc. 2001 RECOMB, ACM Press, 22-30