二倍體單體型重建問(wèn)題研究.pdf

1、在生物科技發(fā)展迅速的二十一世紀(jì)，遺傳變異研究在人類(lèi)基因組測(cè)序計(jì)劃項(xiàng)目完成后成為了最為關(guān)注的熱門(mén)研究之一。而單核苷酸多態(tài)性(Single Nucleotide Polymorphisms，SNP)在各類(lèi)遺傳變異中是最為突出常見(jiàn)的一種形式，針對(duì)SNP的研究可以探索生物進(jìn)化歷程，解決很多遺傳性疾病的診療問(wèn)題、了解易感機(jī)制，以及對(duì)藥物研制等方面發(fā)揮重要作用。在一些相關(guān)研究中得知，單體型所攜帶的遺傳信息相比單個(gè)SNP位點(diǎn)要更豐富。然而，使用生物學(xué)

2、的傳統(tǒng)方法進(jìn)行個(gè)體單體型測(cè)序會(huì)受到實(shí)驗(yàn)條件和昂貴開(kāi)銷(xiāo)的限制，個(gè)體單體型重建這個(gè)計(jì)算問(wèn)題應(yīng)運(yùn)而生，即根據(jù)個(gè)體DNA測(cè)序片段，利用計(jì)算技術(shù)完成單體型的重建。本文針對(duì)二倍體個(gè)體單體型重建問(wèn)題展開(kāi)研究。
　　HapCompass算法是求解最少帶權(quán)邊刪除模型(The Minimum Weighted Edge Removal，MWER)的有效啟發(fā)式算法，該算法采用刪除權(quán)值絕對(duì)值最小的邊的方式消除沖突環(huán)基，當(dāng)同時(shí)存在多條權(quán)值絕對(duì)值最小的邊時(shí)，

3、HapCompass隨機(jī)選擇刪除邊，導(dǎo)致求解方案的不確定性，降低重建效果。針對(duì)此問(wèn)題，本研究提出算法IHapCompass，該算法改進(jìn)去邊規(guī)則，利用0011和0110分型的片段支持差異數(shù)與總片段數(shù)之間的比值來(lái)確定刪除邊，對(duì)隨機(jī)取值問(wèn)題做出有效限定。此外，IHapCompass以單體型中0/1取值的概率為圖中孤立點(diǎn)賦值，明確孤立點(diǎn)取值。采用HapMap發(fā)布的CEPH樣本中的單體型數(shù)據(jù)，由CELSIM和MetaSim兩種測(cè)序片段模擬生成器生

4、成片段數(shù)據(jù)，在片段覆蓋率、錯(cuò)誤率、單片段長(zhǎng)度和單體型長(zhǎng)度等參數(shù)的不同設(shè)置下，比較分析算法IHapCompass、HapCompass、DGS和Fast Hare的重建率和運(yùn)行時(shí)間。實(shí)驗(yàn)結(jié)果顯示，IHapCompass算法在不同的參數(shù)設(shè)置下，均能獲得最高的單體型重建率，具有較高的執(zhí)行效率。
　　最少錯(cuò)誤更正模型MEC試圖更正最少的測(cè)序錯(cuò)誤來(lái)確定單體型唯一分型，本文針對(duì)該模型提出一種有效啟發(fā)式算法HIEF。通過(guò)分析真實(shí)測(cè)序數(shù)據(jù)NA12

5、878的數(shù)據(jù)特征，發(fā)現(xiàn)存在于真實(shí)DNA測(cè)序片段數(shù)據(jù)中的規(guī)律，即測(cè)序片段的非空位點(diǎn)數(shù)越多，則攜帶的信息越可靠?；谶@個(gè)思路，算法HIEF首先選取測(cè)序片段中非空位點(diǎn)最多的一條片段作為基準(zhǔn)，然后基于MEC模型將剩下的片段劃分為兩個(gè)不相容的集合，劃分過(guò)程中不斷地對(duì)非空位點(diǎn)數(shù)最多的測(cè)序片段做擴(kuò)展，最終擴(kuò)展完成重建得出二倍體單體型。采用CELSIM生成的模擬數(shù)據(jù)和NA12878的真實(shí)測(cè)序片段數(shù)據(jù)對(duì)算法性能進(jìn)行測(cè)試和分析，實(shí)驗(yàn)結(jié)果顯示，算法在多個(gè)評(píng)價(jià)