透過群試對壓縮基因分型的研究

A Study of Compressed Genotyping via Group Testing

蔣依芸(Yi-Yun Jian)

指導教授 ： 潘戍衍

國立清華大學/理學院/數學系/碩士(2014年)

摘要

群試有時被稱為測試的池子，可以應用到具有兩個可能結果的任意子集上，陰性的結果顯示S中的所有樣本都是陰性的，而陽性的結果表示S中有些樣本是陽性的。
基因分型是通過使用生物測定法檢查其DNA序列，並將其與另一個個體的序列或參照序列以判別個體的遺傳組成（基因型）的差異的過程。也就是說，基因分型是判斷個體中某些性狀的遺傳變異的過程。
廣為人知的，群試在DNA 的測序上扮演極為重要的角色，因此我們可以使用這個概念來判斷個體所有的基因型。在這篇論文中，我們主要使用disjunct 矩陣來實現目標。更確切地說，我們將使用d'-disjunct 矩陣和二階段的演算法去找到d個正的樣本，在d>d'的情況下 。
我們先從2-disjunct 矩陣A為例，找到一個具有3個1的二進制向量x，接著我們探討d和d'之間的關係 ，所得到的結論是﹔如果d和d'之間的差距不是太大的話，那麼我們的池子的設計可以運用。然而對於固定的d'，如果d越大時，應用群試的方法可能會有困難，我們將舉一個例子，在上下文中顯示這個事實。

關鍵字

群試 ； 基因分型

並列摘要

無資料

並列關鍵字

Group Testing ； Genotyping

參考文獻

[1] E. Candes, J. Romberg, and T. Tao. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory, 52:489–509, 2006.

[2] H. B. Chen. Combinatorial nonadaptive group testing with biological applications. Ph.D. Thesis, National Chiao Tung University, 2006.

[3] Y. Cheng, D. Z. Du, and G. Lin. On the upper bounds of the minimum number of rows of disjunct matrices. Springer-Verlag., pages 297–302, 2008.

[4] K. R. Chi. The year of sequencing. Nat. Methods, 5:11–14, 2008.

[5] S. Deschamps, V. Llaca, and G. D. May. Genotyping-by-sequencing in plants. Biology, 1:460–483, 2012.