关于针对书面报告的解释.doc

HR Planning System Integration and Upgrading Research of A Suzhou InstitutionGraph Theory書面報告 3學號：946349姓名：蘇育仁PaperTitle: A Greedier Approach for Finding Tag SNPsAuthors: Chia-Jung Changa, Yao-Ting Huanga, and Kun-Mao ChaoPublication: Bioinformatics Advance Access published January 10, 20061、ProblemSingle 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，而白色的則是不選擇該SNP。以圖中的problem為例，所有patterns選擇S1可以使得Dfinal包含最多Ei，因此L=1選擇S1，並產生一個不選擇S1的node。在選擇了S1為tag SNP的狀況下，選擇S2可以讓Dfinal能分辨的patterns增加最多，也就是同時考慮S1和S2可以讓Dfinal包含最多的Ei；另外，在不考慮S1為tag SNP的情況下，選擇S3可以讓Dfinal能分辨最多patterns，也就是說，只看一個SNP的話，S3的鑑別力是僅次於S1的；因此L=2時的兩個分支，分別選擇S2及S3為tag SNPs。上述步驟一直執行到分支的深度到達設定的L值，或是Dfinal可以分辨所有patterns為止。GPT執行到預設L值的時候，如果Dfinal還沒有辦法分辨所有patterns（作者實驗的資料中，通常設定L遠小於最佳解），則將剩下的subproblem用greedy algorithm的方式去解。因此如果以作者的實驗中，計算人類基因的資料為例，L設定為10的話，就會有1024個subproblems。3、Results下圖是greedy algorithm、LP-relaxation algorithm、GPT三種演算法，在Hudsons data，也就是人類的基因資料上的執行結果：表格中的OPT是最佳解，應該是由資料查到的，而不是真的用branch-and-bound algorithm去解的。由表格可以看出來，GPT的結果都和最佳解是一樣的，而greedy和LP-relaxation都和最佳解有一段誤差。4、Discussion作者所提出的這個GPT方法，根據實驗結果，可以同時兼顧運算時間和答案的正確性，而對於subproblems個數太多，所造成的運算時間負擔，也可以使用平行計算的方式處理掉，因為每個subproblem之間彼此獨立，所以在平行計算的時候不須要互相溝通、交換資料，也就是說，在平行計算的時候最主要的負擔，在GPT上是不須要考慮的。另外，我們自己提出的想法，是在GPT的前半段，也就是在上面的tree要做branch的時候，不是以greedy algorithm的原則來選擇SNP，而是以隨機的方式。雖然直覺上這樣不見得會比gre