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

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

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

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

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