K單體型重建算法的研究.pdf

1、隨著新一代基因測序技術的飛速發(fā)展，以及單體型數(shù)據(jù)在人類遺傳學等領域研究和應用的不斷深入，對單體型數(shù)據(jù)的研究開始轉向其他生物物種。由于測序技術的限制，通過生物學實驗的手段直接測定單體型的代價過于昂貴，因此，基于DNA片段數(shù)據(jù)的單體型組裝技術的研究仍然是這些應用得以大規(guī)模推廣的必要手段。由于許多其他物種的單體型個數(shù)均大于2，現(xiàn)有求解二倍體單體型的算法無法應用于這些物種的單體型組裝，因此研究適用于這些物種的K單體型組裝算法具有重要的科學研究價

2、值和現(xiàn)實意義。本文針對K單體型組裝算法進行研究。
　　論文首先介紹了K單體型組裝問題的相關背景知識和研究意義，闡述了其研究現(xiàn)狀和進展。K單體型計算問題可分為K值已知和K值未知兩種情況。本文分別對這兩種情況的計算問題進行研究，提出了基于遺傳算法的求解方法，并通過大量的實驗對算法進行性能分析。具體內(nèi)容如下:
　　針對K值已知的情況，對K值取3的三倍體單體型重建問題進行了研究，基于最少錯誤更正模型，提出了重建三倍體個體單體型的遺傳

3、算法GTIHR。算法采用了新穎的染色體編碼方法和有效的遺傳算子，其較短的染色體編碼方式能夠構造較小的解空間，從而使得算法快速收斂到最優(yōu)解，此外，提出的遺傳算子通過對染色體注入隨機信息而避免早熟現(xiàn)象，并在優(yōu)化過程中，有效地利用SNP片段中的信息來逐步修正染色體編碼取值。由于真實的DNA片段數(shù)據(jù)一般很難得到，實驗采用鳥槍法測序模擬片段生成器CELSIM生成片段數(shù)據(jù)。通過對算法進行測試表明，GTIHR算法能夠獲得更高重建率的單體型，實際使用價

4、值較強。
　　針對K值未知的情況，對病毒準種單體型重建問題進行了研究。在“已糾錯”片段的基礎上，提出一種求解該問題的遺傳算法GVQHR。針對病毒準種組裝問題的特點設計了有效的染色體編碼及爬山算子。染色體采用可變長的字符串集合進行編碼，爬山算子首先隨機去除準種中的某些單體型，然后根據(jù)剩余單體型及片段集合重新組建新的準種。算法采用HIV-1型病毒基因進行實驗測試。實驗結果顯示，在各個參數(shù)設置下，算法GVQHR能獲得較好的重建效果，對進