最小覆蓋問題在測集設計的反物模型上的應用

Abstract

最小覆蓋問題在圖論中算是個大問題,很多題目都可以轉換成這類形的問題.在這篇文章中,我們會討論到的是它的一個特別例子,即發生在二分圖中的最小覆蓋問題,我們將給出一個下界並將這個結果用在測集設計中.

一個clone是一小段DNA序列,clone library是儲存了大量clone的地方,從clone library裡找出特定性質的clones, 我們稱之為正物,便是clone library的檢測問題。將一群clones放在一起並稱此集合為一個測集(pool)。我們用檢測測集代替檢測所有clone。另外,我們還希望同時檢測所有的測集,以節省我們的時間。所謂測集設計就是同時檢測所有測集的方法,我們利用它有效的找出正物。

由於DNA分子間的作用,有時正物會與某些亦存在於 clone library 裡的clones,我們稱之為反物.產生化學反應。如果受測試的測集中,同時包含了一些正物跟反物,我們會誤認此測集中並不含有正物.本論文利用了最小覆蓋問題的結果,提出了一個結果可以應用在測集設計上,達到檢測出所有正物的結果。