关于针对面报告解释.doc

HR Planning System Integration and Upgrading Research of A Suzhou Institution Graph Theory 書面報告 3 學號：946349 姓名：蘇育仁 Paper Title: A Greedier Approach for Finding Tag SNPs Authors: Chia-Jung Changa, Yao-Ting Huanga, and Kun-Mao Chao Publication: Bioinformatics Advance Access published January 10, 2006 1、Problem Single Nucleotide Polymorphism (SNP) A genetic variation when a single nucleotide (i.e., A, C, G, or T) in the DNA sequence is altered and kept through heredity thereafter. 上述是作者在paper中對於SNP的描述，SNP是同物種中，不同個體在DNA sequence間發生差異的最主要位置，而且通常只有一個鹼基會發生，如下圖： 上圖兩個個體之間，只有一個鹼基有差異，其他的序列都是一樣的，而且在那個SNP的地方，該物種的所有個體不是AT就是CG，不會是其他的，正如paper中那段話提到的，SNP的值是altered。 將一個個體的DNA序列中，只取其SNP的值出來，並以顯隱性表示之，稱為一個haplotype pattern。 正因為SNP的值有顯隱性之分，所以若有兩haplotype patterns A和B，在某一個SNP的值不同，則只要看該SNP的值，就可以區分這兩個haplotype patterns，進而區別出兩個不同個體，如下圖： 上圖中(a)表示在四個haplotype patterns中，四個SNP的值。圖(b)中以S1為例，有弧線相連的兩個patterns表示S1可以分辨的有P1和P2、P1和P3、P2和P4、P3和P4。 Finding tag SNPs 在一群haplotype patterns中，如果有一組SNPs足以分辨所有patterns的話，則稱之為tag SNPs。 以上圖(a)為例，選擇S1為一個tag SNP的話，根據圖(b)所示S1所能分辨的patterns，則必須另外選擇S2或S3以分辨P2和P3，以及選擇S4來分辨P1和P4，所以S1、S2、S4和S1、S3、S4是這些haplotype patterns的兩組tag SNPs。 由tag SNPs的定義，可以知道最差的情況就是把所有SNP都選為tag SNP，一定可以分辨所有patterns，因此找尋tag SNPs的問題，其目的在於找出tag SNP數量的最小值，最佳的tag SNPs可能不是唯一，但是最小值會只有一個解。 尋找tag SNPs的問題，可以如下圖表示為尋找cover的問題： E1到E6是所有patterns取兩個的所有狀況，而S1到S4為所有SNPs，若Si和Ej間有線相連，表示第i個SNP可以分辨Ej中的兩個patterns。 如此一來，找tag SNPs數量最小值的問題，也就變成尋找最少的D所成的集合，其中包含所有的E，可以視為一個尋找cover的問題，而這類的問題已經被證明是屬於NP-hard。 2、Method 正如前面所提到的，由於這個問題屬於NP-hard的問題，所以有兩類的方式來解決它： 一種是使用比較有效率的approximation algorithm，在paper中有提到，可以用greedy algorithm來處理，也就是maintain一個Dfinal為某些Di所成的集合，每次加一個新的SNP，使得Dfinal中所能分辨的E增加最多，直到D能夠分辨所有E為止。這個方法雖然能把時間複雜度減少為O(|E|nlogn)，但是所計算出的tag SNPs數量最小值和最佳解有一段差距，大約是0.5%左右，每個case有不同的差距。 另外一個方法則是使用branch-and-bound algorithm，雖然這樣可以保證找出最佳解，但是這種做法的時間複雜度是指數成長的，因為這個問題是NP-hard。 本篇paper的作者，則是提出了綜合greedy和branch-and-bound的演算法，稱之為Greedy-Partition-Tree (GPT)。 示意如下圖： 上圖中的root表示原來的problem，L的層數可以由使用者決定，而灰色的internal node表示選擇該SNP為tag SNP，而白色的則是不選擇該SN