生物應用衍生的群試問題

Abstract

在計算分子生物學裡，群試理論(Group Testing)是實驗設計的一種基本工具。例如，用來有效率地找出哪些克隆(clone)含有一個特定的因子。克隆如果含有這個特定因子則稱它為正的克隆；反之，稱為負的克隆。最傳統的群試模型就是每次都可以選擇任意的一些克隆去作實驗，實驗的反應若為陽性代表這群克隆裡面有至少一個是正的；若為陰性則代表這些克隆都是負的。目標就是找出所有正的克隆。而我們將藉由群試設計來減少實驗的次數以及節省所需的時間。 在應用上，除了正和負的克隆之外，還有一種稱為抑制□(inhibitor)的克隆，它的功能就是會抑制正克隆的反應，導致實驗的結果呈現陰性。此外，在某些應用上，實驗的陽性反應僅僅只會發生在某些特定的克隆同時出現時，而這種會發生陽性反應的克隆集合被稱為正的複合物。我們的目標就是要找出所有的正複合物，而這樣的模型則被稱之為複合物模型(complex model)。 群試的演算法大致上可以分為兩類：逐步演算法(sequential algorithm)以及非調整型演算法(nonadaptive algorithm)。逐步演算法指的是實驗是一個接著一個進行的；也就是說可以利用之前的實驗結果來安排下一個實驗。而非調整型演算法指的是所有的實驗必須事先安排好，不能參考其他的實驗結果來作調整。因此，在理論上是可以視為所有實驗可以同時進行的同步演算法。在分子生物的應用裡，大多數的實驗都是很費時的，一個實驗快則幾個小時可以完成，慢則需要好幾天，甚至是幾個星期。因此，可以同步進行的非調整型演算法是比較能夠被接受且常用的方法。 在這篇論文裡，我們主要的工作就是去設計非調整型演算法，來解決生物應用所衍生出來的一些模型。首先，我們把非調整型演算法表示成矩陣的樣子，並且定義一些矩陣的性質。在第三章，我們討論了基本群試模型的矩陣性質間的關係。第四章，我們從解碼的角度出發，去探索目前分子生物學所衍生出來的群試模型之間的異同。第五章主要是討論複合物模型。值得一提的是，在這裡我們提出了兩種對應到非調整型演算法的矩陣的建構方法，而這種矩陣也適用於後面的章節。第六章的焦點是放在有抑制□存在的群試模型。特別的是，除了找出所有正的克隆之外，我們還去探討如何找出所有的抑制□，在這篇論文裡提出了第一個非調整型的演算法來達到這個目標。最後，在第七章我們研究的是傳統群試模型的推廣，稱為門檻群試 (threshold group testing)。

Combinatorial group testing is a basic tool in conducting experiments of tests which can be applied to computational molecular biology. For example, in screening clone library the goal is to determine which clones in the clone library hybridize with a given probe in an efficient fashion. A clone is said to be positive if it hybridizes with the probe, and negative otherwise. In practical applications, besides positive and negative clones, there is a third category of clones called inhibitors whose e□ect is to neutralize positive clones. Therefore, we shall have models of group testing with or without inhibitors. Also, in applications, we may face the situation that the property of being positive or negative is de‾ned on subsets of items instead of on individual items. Such a model is known as a complex model. The study of complex models does have a signi‾cant impact in recent years. Group testing algorithms can be generally divided into two types, sequential and nonadaptive. A sequential algorithm conducts the tests one by one and the outcomes of all previous tests can be used to set up the later test. A nonadaptive algorithm speci‾es all tests in advance so that they can be conducted simultaneously; thus forbidding using the information of previous tests to design later ones. Sequential algorithms require fewer number of tests in general, because extra information helps for more e±cient test designs. Nonadaptive algorithms permit to conduct all tests simultaneously, thus saving time for testing. In most applications to molecular biol- ogy, an experiment can be time-consuming. Therefore, it is much preferable to have a nonadaptive algorithm where all tests are specified in advance; thus can be conducted simultaneously. In this thesis, we first introduce a few types of matrices such as separable or disjunct matrices and then a connection between separability and disjunctness will be provided in Chapter 3. Chapter 4 reviews various models in molecular biology by focusing on the angle of decoding. Chapter 5 studies the complex model, and provides two methods to construct generalized disjunct matrices. Chapter 6 focuses on group testing with inhibitors. In particular, we study a generalized problem that is to also identify the inhibitors besides the positive clones. Finally, in Chapter 7 we have made some contributions in threshold group testing.