【摘要】：目前,群智能優(yōu)化算法得到長足的進步和發(fā)展,并已成功應用于科學計算和工程領域。然而,隨著科技進步和大數據時代的興起,大量復雜的高維優(yōu)化問題不斷涌現,使得很多現有優(yōu)化方法不再適用于新問題的求解。近年來,和聲搜索(Harmony Search,HS)和差分進化(Differential Evolution,DE)算法在求解復雜優(yōu)化問題方面引起研究者廣泛關注。和聲搜索算法具有很強的全局探索能力,不容易陷入局部搜索,適用于復雜的實數和離散優(yōu)化問題求解。差分進化算法在實數優(yōu)化方面具有豐富和成熟的研究基礎,在復雜問題求解方面也已展現出了優(yōu)異性能。然而,對于大規(guī)模高維(大于500維)復雜優(yōu)化問題,許多優(yōu)秀群智能優(yōu)化算法的全局求解性能會大幅下降。因此,高維復雜優(yōu)化問題求解成為信息科學領域研究的熱點之一。在生命科學領域,高通量測序技術產生了大量組學數據(基因組、代謝組、蛋白質組和糖組學等),為研究人類復雜疾病的致病原因提供了良好的研究基礎,但同時也對科學計算技術提出了巨大挑戰(zhàn)。特別是在全基因組關聯研究(Genome-wide Association Study,GWAS)中,人們試圖從全基因組序列中發(fā)現多個聯合作用于復雜疾病的單核苷酸多態(tài)性(Single Nucleotide Polymorphism,SNP)位點,但由于組合爆炸問題,傳統(tǒng)的窮舉法難以適用于鑒定所有SNP組合位點與復雜疾病的關聯性,使得目前成功的GWAS應用還主要是單個SNP致病位點的發(fā)現,而對于多SNP聯合致病組合位點探測,是非常復雜的高維組合優(yōu)化問題,依然沒有非常好的精確計算方法,成為目前生物信息學與生命科學研究的重點之一。針對上述兩個問題,本課題主要從高維復雜優(yōu)化問題的群智能求解算法及其在人類復雜疾病關聯分析中的應用展開研究。為了能夠提升高維復雜優(yōu)化問題的求解性能,重點研究了和聲搜索和差分進化算法在搜索過程中全局探索能力(Exploration power)和局部開發(fā)能力(Exploitation power)的變化,以及造成算法性能下降的主要因素。發(fā)現和聲搜索與差分進化算法有一個共同問題,在進行高維復雜問題優(yōu)化的后期,它們的更新操作成功率會非常低。另外,差分進化算法中的變異算子在求解高維優(yōu)化問題時,存在大量冗余計算,也是影響算法搜索速度的關鍵因素,為此,提出了兩個求解高維復雜問題的群智能優(yōu)化算法(面向高維復雜優(yōu)化問題的和聲搜索算法,改進的差分進化算法)。為了能夠從高維的SNP數據中快速搜索出多SNP聯合致病組合位點,重點研究了使用和聲搜索算法探測多SNP聯合致病組合位點的可能性,主要從算法的搜索速度和致病組合位點的識別能力方面進行研究,提出了兩種基于和聲搜索的SNP聯合致病位點探測算法。本博士論文主要在以下幾個方面進行了較為深入的研究和探索:(1)針對高維多峰值復雜優(yōu)化問題求解,提出了基于變量動態(tài)降維選擇調整策略的和聲搜索算法(DIHS)。通過比較傳統(tǒng)和聲搜索算法用于產生新和聲的Take-all策略和一個簡單的Take-One策略,發(fā)現在優(yōu)化進程的后期,Take-all策略產生優(yōu)勝新解的成功率隨著優(yōu)化問題維度的增高下降很快,是影響傳統(tǒng)HS算法求解速度和精度的關鍵因素。為此,提出采用變量動態(tài)降維選擇調整策略和動態(tài)步長擾動機制,用以提高和聲搜索算法產生優(yōu)勝新解的成功率,從而提升算法全局求解能力。通過對12個多峰和4個單峰的典型優(yōu)化問題進行測試,結果表明,對于高維多峰值優(yōu)化問題,DIHS在搜索過程中能夠始終保持較高的更新操作成功率,并能夠以較小的運行代價獲得高精度全局最優(yōu)解。與標準HS相比,在求解1000維的這16個測試問題時,求解精度平均提升了 90.33%,且運行時間平均減少23.8%。(2)針對差分進化(Differential Evolution,DE)算法在進行高維復雜問題求解時存在大量冗余計算、易陷入局部搜索等問題,提出改進的差分進化算法,將變異算子和交叉算子相融合,引入局部變量動態(tài)調整策略,以增強DE的全局搜索能力。采用動態(tài)的交叉概率參數(Crossover rate,CR)同時管理變異算子和局部變量調整策略,用于降低計算冗余。通過實驗測試表明,提出的DE算法的求解質量在所有測試問題上都優(yōu)于標準DE算法,并且在求解1000維的16個復雜測試問題時,計算速度平均提升13.79%,全局最優(yōu)解的求解精度平均提升81.96%。另外通過與三個經典的復雜問題求解算法(SaDE,CoDE,CMAES)和7個高維問題求解算法相比較,證明了改進DE算法求解高維復雜優(yōu)化問題的可行性。(3)在全基因組關聯性研究中,兩個SNP組合位點是非常常見和重要的致病組合。然而,由于SNP位點的組合數量巨大和致病模型豐富多樣,使得現有很多算法在進行致病位點探測時,存在運算代價大和致病模型識別準確率低的缺點。為此,提出了一種快速的兩位點探測算法(FHSA-SED),采用兩個互補的輕量級評分標準(基于貝葉斯網絡的K2-Score和Gini-Score)評價SNP組合位點與疾病狀態(tài)的關聯性;利用和聲搜索算法進行全局搜素,將評分較高的SNP組合位點存放在候選集中,最后利用改進的G-test方法對候選SNP組合位點進行檢驗和確認。12個有邊際效應(Disease with Marginal Effect,DME)與 70 個無邊際效應(Disease with No Marginal Effect,DNME)的仿真數據實驗和1個真實的老年性黃斑變性(age-related macular degeneration:AMD)數據實驗表明,FHSA-SED算法在進行兩個SNP致病位點探測時,具有搜索速度快,識別能力強和準確率高等特點。(4)為了能夠快速準確地進行多SNP聯合致病組合位點探測,提出了一種基于小生境策略的和聲搜索算法(NHSA-DHSC)。通過提出小生境識別技術輔助HS算法,探測不同類型的SNP致病組合模型并防止HS算法陷入局部搜索;通過運用SNP組合位點的聯合熵作為和聲搜索的啟發(fā)式因子,快速識別邊際效應低的致病SNP組合位點;K2-Score和Gini-Score用于識別多樣的致病組合模型;改進的G-test方法用于檢驗最終結果的真?zhèn)涡�。實驗采�?2個有邊際效應的DME仿真數據集,8個高階無邊際效應的DNME仿真數據集和1個真實的AMD數據測試NHSA-DHSC算法的致病位點探測性能,結果表明,該算法能夠快速準確的識別DME致病位點,可以快速識別一些無邊際效應的多SNP聯合致病組合位點,并且能夠從AMD數據中快速發(fā)現已知的致病SNP位點。
【圖文】：

圖１．邋１兩個ＤＮＡ序列的單位點多態(tài)性（Ｃ／Ａ多態(tài)）逡逑在人類基因組上，平均每５００？１０００個堿基對中就有１個ＳＮＰ位點，其總的ＳＮＰ逡逑數量超過了邋３００萬個。大部分ＳＮＰ不會對人的健康或表型產生影響，但是，，有些ＳＮＰ逡逑變異位點往往和人類的健康或外在表型特征有直接的關聯關系，特別是多個ＳＮＰ變逡逑

圖１．２論文組織結構圖逡逑
【學位授予單位】：西安電子科技大學
【學位級別】：博士
【學位授予年份】：2017
【分類號】：TP18;R-05


本文編號：2603022