遺傳多態(tài)性檢測(cè)中組合優(yōu)化問題的研究.pdf

1、遺傳多態(tài)性檢測(cè)是進(jìn)行遺傳多態(tài)性研究的關(guān)鍵環(huán)節(jié)。近年來，為降低檢測(cè)成本，以計(jì)算手段為輔助的多態(tài)性檢測(cè)已得到廣泛應(yīng)用，同時(shí)，在該研究領(lǐng)域中出現(xiàn)了一系列以提高檢測(cè)效率和降低檢測(cè)成本為目的的組合優(yōu)化問題。本文主要研究個(gè)體單體型檢測(cè)問題、基于連鎖不平衡的多種群標(biāo)簽SNPs選擇問題及多元聚合酶鏈反應(yīng)引物集設(shè)計(jì)問題。 本文針對(duì)個(gè)體單體型檢測(cè)問題的帶權(quán)最少字符修改模型，提出一種啟發(fā)式算法HAW。該算法先對(duì)每條SNP片段計(jì)算其全局兼容集，再選出包

2、含片段數(shù)最多且交集為空的兩個(gè)全局兼容集以生成一對(duì)初始單體型，最后通過剩余片段對(duì)其擴(kuò)充完成重建。大量實(shí)驗(yàn)結(jié)果表明HAW算法能快速求解該模型，并獲得較目前求解該模型的算法更高的單體型重建率。 針對(duì)個(gè)體單體型檢測(cè)問題的最少片段刪除模型，本文提出一種粒子群優(yōu)化算法PSO-MFR。該算法利用二進(jìn)制編碼粒子，并重新定義了粒子位置和速度之間的運(yùn)算操作。由于利用了SNP位點(diǎn)雜合率較低的特性，該算法所引入的編碼方式較短，能產(chǎn)生一個(gè)較小的解空間，從

3、而快速地獲得好的結(jié)果。實(shí)驗(yàn)結(jié)果表明，PSO-MFR算法是一種求解該模型的有效方法，能在較短時(shí)間內(nèi)獲得較高的單體型重建率，并得到較Fast Hare算法更高的重建率。 針對(duì)個(gè)體單體型檢測(cè)問題的最少錯(cuò)誤更正模型，本文深入分析了以往算法在求解該問題時(shí)遺失最優(yōu)解的原因，提出一種生成小規(guī)模優(yōu)化解集合的新研究思路。通過引入較短的染色體編碼方式和一種利用片段信息來修正染色體的重組算子，提出求解最少錯(cuò)誤更正模型的單親遺傳算法PGA-MEC。實(shí)驗(yàn)

4、結(jié)果表明PGA-MEC算法能有效求解該模型，在更短的運(yùn)行時(shí)間內(nèi)獲得較以往求解該模型的算法更高的單體型重建率。進(jìn)一步，將優(yōu)化解集合的思想運(yùn)用于PGA-MEC算法，提出IPGA-MEC算法。實(shí)驗(yàn)結(jié)果顯示優(yōu)化解集合的引入能有效避免最優(yōu)解的遺失，從而進(jìn)一步提高單體型的重建率。 針對(duì)基于連鎖不平衡的多種群標(biāo)簽SNPs選擇問題，給出其形式化描述，并通過對(duì)集合覆蓋問題在多項(xiàng)式時(shí)間內(nèi)的歸約證明其是NP-難的。進(jìn)一步，本文提出一種求解該問題的貪婪

5、算法MP-Tagging，該算法在每次迭代過程中選擇1個(gè)或2個(gè)標(biāo)簽SNPs。實(shí)驗(yàn)結(jié)果表明MP-Tagging算法能有效求解該問題，并能夠找到較以往算法更少的標(biāo)簽SNPs。 針對(duì)多元聚合酶鏈反應(yīng)引物集設(shè)計(jì)問題，提出一種多約束最小引物集選擇問題的數(shù)學(xué)模型。針對(duì)該模型，本文提出貪婪算法MG，并基于MG算法設(shè)計(jì)一種新穎的重組算子，從而給出求解該模型的單親遺傳算法MG-PGA。實(shí)驗(yàn)結(jié)果表明MG-PGA算法在滿足多約束條件下能獲得較以往求解