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

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

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


本文編號：2603022