羅瓦胥局部引理在匯集設計上的應用

Abstract

在計算分子生物學的應用中，一個群試演算法(group testing algorithm)被稱作一個匯集設計(pooling design)，而每個合成測試被稱作一個匯集(pool)。匯集的數目反映了我們必須花費在實驗上的時間與金錢；因此，在測試物件數目固定的前提之下，不管使用逐步演算法(sequential algorithm)或是非調整型演算法(nonadaptive algorithm)，讓匯集的數目最小化是研究群試演算法的最重要任務。 在這篇論文裡，我們主要針對幾類可以應用在匯集設計的矩陣（其中包括(d,r]-分離矩陣、(d,r)-分離矩陣、(d,s out of r]-分離矩陣以及(k,m,n)-選擇器)，在固定行(column)數的前提之下，利用羅瓦胥局部引理分別去求得這些矩陣的最小列(row)數的上界。