二倍體單體型重建問題研究.pdf

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

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

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

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

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