关于针对书面报告的解释

《关于针对书面报告的解释》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、HRPlanningSystemIntegrationandUpgradingResearchofASuzhouInstitutionGraphTheory書面報告3學號：946349姓名：蘇育仁PaperTitle:AGreedierApproachforFindingTagSNPsAuthors:Chia-JungChanga,Yao-TingHuanga,andKun-MaoChaoPublication:BioinformaticsAdvanceAccesspublishedJanuary10,20061、ProblemSingleNucleotidePolymo

2、rphism(SNP)Ageneticvariationwhenasinglenucleotide(i.e.,A,C,G,orT)intheDNAsequenceisalteredandkeptthroughhereditythereafter.上述是作者在paper中對於SNP的描述，SNP是同物種中，不同個體在DNAsequence間發生差異的最主要位置，而且通常只有一個鹼基會發生，如下圖：上圖兩個個體之間，只有一個鹼基有差異，其他的序列都是一樣的，而且在那個SNP的地方，該物種的所有個體不是AT就是CG，不會是其他的，正如paper中那段話提到的，SNP的值是alt

3、ered。將一個個體的DNA序列中，只取其SNP的值出來，並以顯隱性表示之，稱為一個haplotypepattern。正因為SNP的值有顯隱性之分，所以若有兩haplotypepatternsA和B，在某一個SNP的值不同，則只要看該SNP的值，就可以區分這兩個haplotypepatterns，進而區別出兩個不同個體，如下圖：上圖中(a)表示在四個haplotypepatterns中，四個SNP的值。圖(b)中以S1為例，有弧線相連的兩個patterns表示S1可以分辨的有P1和P2、P1和P3、P2和P4、P3和P4。FindingtagSNPs在一群haplotyp

4、epatterns中，如果有一組SNPs足以分辨所有patterns的話，則稱之為tagSNPs。以上圖(a)為例，選擇S1為一個tagSNP的話，根據圖(b)所示S1所能分辨的patterns，則必須另外選擇S2或S3以分辨P2和P3，以及選擇S4來分辨P1和P4，所以S1、S2、S4和S1、S3、S4是這些haplotypepatterns的兩組tagSNPs。由tagSNPs的定義，可以知道最差的情況就是把所有SNP都選為tagSNP，一定可以分辨所有patterns，因此找尋tagSNPs的問題，其目的在於找出tagSNP數量的最小值，最佳的tagSNPs可能不是

5、唯一，但是最小值會只有一個解。尋找tagSNPs的問題，可以如下圖表示為尋找cover的問題：E1到E6是所有patterns取兩個的所有狀況，而S1到S4為所有SNPs，若Si和Ej間有線相連，表示第i個SNP可以分辨Ej中的兩個patterns。如此一來，找tagSNPs數量最小值的問題，也就變成尋找最少的D所成的集合，其中包含所有的E，可以視為一個尋找cover的問題，而這類的問題已經被證明是屬於NP-hard。2、Method正如前面所提到的，由於這個問題屬於NP-hard的問題，所以有兩類的方式來解決它：一種是使用比較有效率的approximationalgor

6、ithm，在paper中有提到，可以用greedyalgorithm來處理，也就是maintain一個Dfinal為某些Di所成的集合，每次加一個新的SNP，使得Dfinal中所能分辨的E增加最多，直到D能夠分辨所有E為止。這個方法雖然能把時間複雜度減少為O(

7、E

8、nlogn)，但是所計算出的tagSNPs數量最小值和最佳解有一段差距，大約是0.5%左右，每個case有不同的差距。另外一個方法則是使用branch-and-boundalgorithm，雖然這樣可以保證找出最佳解，但是這種做法的時間複雜度是指數成長的，因為這個問題是NP-hard。本篇paper的作者，則是

9、提出了綜合greedy和branch-and-bound的演算法，稱之為Greedy-Partition-Tree(GPT)。示意如下圖：上圖中的root表示原來的problem，L的層數可以由使用者決定，而灰色的internalnode表示選擇該SNP為tagSNP，而白色的則是不選擇該SNP。以圖中的problem為例，所有patterns選擇S1可以使得Dfinal包含最多Ei，因此L=1選擇S1，並產生一個不選擇S1的node。在選擇了S1為tagSNP的狀況下，選擇S2可以讓Dfinal能分辨的patterns增加最