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

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

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

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

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

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