HRPlanningSystemIntegrationandUpgradingResearchofASuzhouInstitutionGraphTheory書面報告3學號:946349姓名:蘇育仁PaperTitle:AGreedierApproachforFindingTagSNPsAuthors:Chia-JungChanga,Yao-TingHuanga,andKun-MaoChaoPublication:esspublishedJanuary10,20061、ProblemSingleNucleotidePolymorphism(SNP)icvariationwhenasinglenucleotide(.,A,C,G,orT),SNP是同物種中,不同個體在DNAsequence間發生差異的最主要位置,而且通常只有一個鹼基會發生,如下圖:上圖兩個個體之間,只有一個鹼基有差異,其他的序列都是一樣的,而且在那個SNP的地方,該物種的所有個體不是AT就是CG,不會是其他的,正如paper中那段話提到的,SNP的值是altered。將一個個體的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在一群haplotypepatterns中,如果有一組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可能不是唯一,但是最小值會只有一個解。尋找tagSNPs的問題,可以如下圖表示為尋找cover的問題:E1到E6是所有patterns取兩個的所有狀況,而S1到S4為所有SNPs,若Si和Ej間有線相連,表示第i個SNP可以分辨Ej中的兩個patterns。如此一來,找tagSNPs數量最小值的問題,也就變成尋找最少的D所成的集合,其中包含所有的E,可以視為一個尋找cover的問題,而這類的問題已經被證明是屬於NP-hard。2、Method正如前面所提到的,由於這個問題屬於NP-hard的問題,所以有兩類的方式來解決它:一種是使用比較有效率的app
关于针对书面报告的解释 来自淘豆网m.daumloan.com转载请标明出处.
