本文關(guān)鍵詞：基于多位點連鎖不平衡度量的標簽SNP選擇方法研究　出處：《中南大學(xué)》2014年碩士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： 單核苷酸多態(tài)性 標簽SNP 蟻群算法 生物信息學(xué)

【摘要】：摘要：基因組上由于單個核苷酸變異所導(dǎo)致的序列多態(tài)性被稱為單核苷酸多態(tài)性(Single Nucleotide Polymorphism, SNP)。研究發(fā)現(xiàn),在不同樣本之間可以通過使用少量的SNP位點即可以表示整個樣本主要的遺傳信息,而這些SNP位點被稱為標簽SNP(tag SNP)。通過基因型序列確定其對應(yīng)的單體型序列過程被稱為單體分型(Haplotyping)。雖然生物實驗可得到更為精確、可靠的單體分型結(jié)果,但是該過程代價高昂,難以滿足實時分析大規(guī)模生物數(shù)據(jù)的需求。因此,利用生物信息學(xué)方法選擇標簽SNP位點,然后在標簽位點上開展單體分析,可以大大降低代價,并可靠地保留原始序列的變異信息。 從包含幾十萬個SNP的基因組中選擇標簽SNP被證實為NP難問題。目前,已有一些方法被用于標簽SNP選擇。但是,它們?nèi)源嬖跁r間復(fù)雜度高、標簽SNP數(shù)目多以及樣本重構(gòu)準確度偏低等不足。針對這些不足,本文設(shè)計了一種基于多位點連鎖不平衡度量的標簽SNP選擇方法。本文主要的工作如下： 第一：結(jié)合現(xiàn)有文獻,更為系統(tǒng)地描述了標簽SNP選擇問題,并比較分析當(dāng)前基于不同思路的方法特點,然后詳細闡述基于樣本重構(gòu)策略的基本步驟。 第二：在候選子集構(gòu)造階段,本文主要創(chuàng)新工作在于結(jié)合SNP數(shù)據(jù)生物含義,將經(jīng)典的蟻群算法用于子集構(gòu)造。該過程中,為了有效降低算法的計算復(fù)雜度,本文以多位點連鎖不平衡度量為優(yōu)化目標,利用蟻群算法的尋找近優(yōu)解,其中工作內(nèi)容包括設(shè)計啟發(fā)函數(shù)及路徑選擇算子等,以提高算法性能。 第三：在標簽子集精選階段,我們提出后向刪除算法用于標簽SNP子集精選。該過程以樣本重構(gòu)的準確度為目標,采用后向淘汰策略選擇具有最優(yōu)分類準確度的標簽SNP子集,該過程的主要目的是進一步提高重構(gòu)準確率及降低標簽SNP的數(shù)量。 第四：為了驗證本文改進方法的有效性,我們基于C++語言設(shè)計實現(xiàn)了該改進算法。然后在多個真實數(shù)據(jù)集上進行了比較實驗,采用的評價指標有重構(gòu)準確度、運行時間上以及標簽SNP數(shù)量,實驗結(jié)果表明,本文方法具備較優(yōu)性能。
【學(xué)位授予單位】：中南大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：Q811.4;TP18

【參考文獻】

中國期刊全文數(shù)據(jù)庫 前1條

1 裴志利;梁艷春;盧奕南;曹忠波;孔英;;從SNP到標簽SNP的算法實現(xiàn)與討論[J];內(nèi)蒙古民族大學(xué)學(xué)報(自然科學(xué)版);2006年06期

，

本文編號：1316798