王麗美，王龍香，鄭程友（.臨滄師范高等?？茖W(xué)校數(shù)理系，云南臨滄677000；.福建農(nóng)林大學(xué)計算機(jī)與信息學(xué)院，福建福州5000；.桂林理工大學(xué)機(jī)械與控制工程學(xué)院，廣西桂林54000）

利用隨機(jī)擾動特性的集合覆蓋蟻群算法識別tag SNPs

王麗美1，王龍香2，鄭程友3
（1.臨滄師范高等?？茖W(xué)校數(shù)理系，云南臨滄677000；2.福建農(nóng)林大學(xué)計算機(jī)與信息學(xué)院，福建福州350002；3.桂林理工大學(xué)機(jī)械與控制工程學(xué)院，廣西桂林541000）

序列中的標(biāo)簽SNPs-tag SNPs攜帶了SNPs數(shù)據(jù)集的絕大部分遺傳信息，因此尋找tag SNPs意義重大.但從SNPs數(shù)據(jù)集中找出tag SNPs需要耗費巨大的計算量，傳統(tǒng)的方法效率低且費用昂貴，對于復(fù)雜的集合覆蓋問題，現(xiàn)有算法難以得到優(yōu)化解.鑒于蟻群算法有較強(qiáng)的近優(yōu)解搜索能力，提出具有隨機(jī)擾動特性的集合覆蓋蟻群算法（RCACO）用于tag SNPs搜索.模擬數(shù)據(jù)集上進(jìn)行的算法實驗結(jié)果表明，與近兩年的PSO、GA兩類算法相比，所提出的算法運行時間較短，搜索結(jié)果精確度更高.

tag SNPs；集合覆蓋；蟻群算法；隨機(jī)擾動

Wang LM,Wang LX,Zheng CY.A Collection of Random-Perturbation Characteristics Covered Ant Colony Algorithm to Identify TagSNPS[J].Journalof Yibin University,2015,15（6）：81-85.

全基因組關(guān)聯(lián)性分析（Genome-Wide Associa?tion Study,GWAS）[1]是指在人類全基因組范圍中找出單核苷酸多態(tài)性，從中挑選出與人類疾病相關(guān)的SNPs.SNP位點在藥物基因組學(xué)、疾病基因定位和人群多樣性的研究中發(fā)揮著及其重要的作用，是后基因組時代的重要研究課題.目前，很多的國內(nèi)外學(xué)者已經(jīng)在進(jìn)行相關(guān)問題的研究，但是海量的數(shù)據(jù)與位點也給SNPs研究者們提出了巨大的挑戰(zhàn).生物信息學(xué)的快速發(fā)展的同時，越來越多的研究人員使用計算機(jī)相關(guān)方法對SNP數(shù)據(jù)利用概率與統(tǒng)計學(xué)的知識，找出與復(fù)雜疾病相關(guān)的SNP位點.

仿生優(yōu)化算法是人工智能研究領(lǐng)域的一個很重要的分支，就是通過程序來模擬自然界已知的進(jìn)化方法來進(jìn)行優(yōu)化的方法，比如模擬鳥類捕食的粒子群算法、模擬生物進(jìn)化的遺傳算法以及模擬螞蟻覓食的蟻群算法等.從整體上來看，人類的智能遠(yuǎn)超越了其他生物的智能.鑒于人類生物系統(tǒng)的復(fù)雜性研究有極大的困難，將其他生物系統(tǒng)作為典型代表并加以探討，可能在現(xiàn)階段更具現(xiàn)實意義；同時作為人類生物系統(tǒng)復(fù)雜性研究的過渡階段，其相關(guān)成果還具有拓廣和延伸的價值.生物蟻群的行為規(guī)律研究可以集中顯示群集智能涌現(xiàn)的特性，正因為如此，目前蟻群算法引起了專家學(xué)者的極大關(guān)注.

蟻群算法，是一種用來尋找優(yōu)化路徑的機(jī)率型算法.它由意大利學(xué)者M(jìn)arco Dorigo于1992年在他的博士論文中首次提出，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為，其本質(zhì)上是一個復(fù)雜的智能系統(tǒng).蟻群算法是一種模擬進(jìn)化算法，研究表明該算法具有許多優(yōu)良的性質(zhì).目前，該研究已滲透到多個領(lǐng)域，并可解決多維的組合優(yōu)化問題，這一新興的仿生優(yōu)化算法已成為交叉學(xué)科中人工智能領(lǐng)域的研究熱點.

1　tag SNPs

1.1數(shù)據(jù)編碼

高通量基因芯片技術(shù)迅猛發(fā)展，使得海量SNP數(shù)據(jù)可通過其進(jìn)行基因分型，國際人類基因組單體型圖計劃（HapMap）為科學(xué)研究貢獻(xiàn)了規(guī)模最大的SNP數(shù)據(jù).構(gòu)建人類DNA序列的多態(tài)位點常見模式是HapMap計劃的最終目標(biāo)，即單體型圖[2-3].文章使用的SNP數(shù)據(jù)是經(jīng)PHASE軟件處理的HapMap的單體型數(shù)據(jù).

HapMap的單體型數(shù)據(jù)中，每個SNP均是二等位的，即一個SNP是由A、C、G和T四個字母中任意兩個字母表示的.為了便于機(jī)器學(xué)習(xí)方法的處理，對SNP的四個字母作了編碼.編碼的過程為：對每個SNP位點，分別統(tǒng)計表示它的兩個字母在數(shù)據(jù)中出現(xiàn)的頻率，將出現(xiàn)頻率大的編碼為1，將出現(xiàn)頻率小的編碼為0.

1.2tag SNPs獲取

獲取tag SNPs實際是在序列集中獲取最小數(shù)目的SNP位點集SU，且在給定的位點集中均能滿足上述兩個特征的tag SNPs位點.描述如下：

輸入：給定單體型序列集所對應(yīng)的m*n矩陣M

輸出：最小數(shù)目的tag SNPs位點集SU，且各tag SNPs位點需滿足三點：

（2）任一tag SNP位點與其關(guān)聯(lián)位點間的平均LD值應(yīng)大于一定閾值（設(shè)定為0.6～0.8）；

標(biāo)簽SNP預(yù)測的目標(biāo)是找出tag SNPs集，即H的最小最佳子集.引入了兩個間接SNP位點集，候選集合L和目標(biāo)集合B.集合L包含了所有符合作為標(biāo)簽SNP條件的SNP，集合B則包含了所有即將被選為標(biāo)簽SNP的位點，即集合L中的SNP與集合B中的標(biāo)簽SNP不存在連鎖不平衡.對L中的每一個am，令C（am）={a：a∈B和r2（a,am）≥r0}代表B的子集，集合中均是與am具有強(qiáng)連鎖不平衡的SNP，并令||C（am）為集合C（am）的元素個數(shù).換句話說，候選集合L是tag SNP集合的替補集..

1.3實驗數(shù)據(jù)集

隨著生物學(xué)的不斷發(fā)展，人類已經(jīng)掌握成百上千萬的SNP位點數(shù)據(jù)，其中部分?jǐn)?shù)據(jù)可以從網(wǎng)上獲取[4-6].下載HapMap（http：//www.hapmap.org）Encode數(shù)據(jù)庫中的phased haplotype data.因為數(shù)據(jù)集是更新的，SNPs的數(shù)目在相同的區(qū)域中有點小差異.實驗數(shù)據(jù)來自HapMap的4個編碼區(qū)：編碼區(qū)（STEAP，ENm010，ENm013，ENr113）數(shù)據(jù)收集于染色體7q21.13，2p16.3，4q26和5q31，分別包含25，105，376，523個SNP位點.其中STEAP來自于CEU種群，ENm010來自東京的日本種群，ENm013和ENr113來自于歐洲種群.在這四個序列集中來測試該算法的性能，并與近年來應(yīng)用于tag SNPs的遺傳算法（GA）及粒子群算法（PSO）的實驗結(jié)果進(jìn)行了比較.實驗所得到的精確度預(yù)測值是基于tag SNPs位點預(yù)測非tag SNPs位點.聚類處理中所使用的數(shù)據(jù)集則是HapMap中YRI（尼日利亞伊巴丹）人種1號染色體所對應(yīng)的單體型數(shù)據(jù)集（包括22 018個SNP位點構(gòu)成的120條序列）.

2　集合覆蓋蟻群思想

對集合覆蓋問題的求解，已經(jīng)有許多學(xué)者根據(jù)不同的思想提出了各種算法.比如，有基于分支定界思想來求解此問題的完整算法[7]，也有人通過對幾種完整算法進(jìn)行比較和分析，得出了針對于求解集合覆蓋問題最好的完整算法[8].集合覆蓋問題模型的應(yīng)用非常廣泛，目前優(yōu)化集合覆蓋問題主要采用的是一些近似算法，相對于復(fù)雜的或規(guī)模較大的數(shù)據(jù)集，傳統(tǒng)算法因其運算時間太長，集合覆蓋問題的優(yōu)化效果不太理想.近幾年，專家學(xué)者提出了啟發(fā)式算法來求解此問題，利用啟發(fā)式的優(yōu)點，使集合覆蓋的求解在可以接受的時間內(nèi)得到近似最優(yōu)解.

啟發(fā)式的典型代表之一就是蟻群算法.蟻群算法主要是基于群體智能而得出的一種進(jìn)化算法，它強(qiáng)調(diào)螞蟻個體間的合作，利用信息素正反饋機(jī)制，較于其他智能算法具有較強(qiáng)的搜索較優(yōu)解的能力.該算法從開始提出就受到了普遍關(guān)注，因其采用分布式并行計算機(jī)制，且易與其他機(jī)器學(xué)習(xí)方法結(jié)合，并且蟻群算法在很多復(fù)雜的組合優(yōu)化問題領(lǐng)域已經(jīng)有成功應(yīng)用的例子，其出色的優(yōu)化能力為本文優(yōu)化集合覆蓋問題提供了新的思路.

該算法同時也有消耗時間長和容易陷于局部最優(yōu)解的缺陷.對蟻群算法作了深入的研究分析，并提出了基于罰函數(shù)的集合覆蓋蟻群算法，將其命名為PCACO.主要內(nèi)容是針對標(biāo)準(zhǔn)蟻群算法的不足做了改進(jìn)，以此加強(qiáng)算法的優(yōu)化能力，提高其收斂速度.用PCACO來優(yōu)化集合覆蓋問題，實驗結(jié)果表明了PCACO求解集合覆蓋問題在全局尋優(yōu)及收斂速度上的優(yōu)化效果理想.

3　具有隨機(jī)擾動特性的集合覆蓋蟻群算法（RCACO）

3.1算法的評估準(zhǔn)則

目前，大多數(shù)文獻(xiàn)中所使用的對tag SNPs位點選擇算法的性能度量參數(shù)主要有三個：最終的tag SNPs位點數(shù)、算法運行時間及精確度值[5].在各個tag SNPs位點選擇算法中，最后的tag SNPs位點數(shù)指的是算法最終結(jié)果中的SNP位點數(shù)；算法的運行時間則是從輸入單體型數(shù)據(jù)開始直到算法終止所花費的時間；精確度值是用于衡量所tag SNPs位點所攜帶的信息量.

現(xiàn)已有若干種關(guān)于tag SNPs位點選擇算法的精確度評估準(zhǔn)則.兩條單體型序列所有的SNP位點中相同位置所擁有的不同堿基對總數(shù)被定義為單體型的多樣性，Clayton基于單體型的多樣性提出了一種精確度評估標(biāo)準(zhǔn).此方法能夠定義一個tag SNPs位點集合是否可以有效地區(qū)分單體型，但它僅適用于有限多樣性的單體型，面對單體型的大數(shù)據(jù)集卻有失偏頗.之后，Stram[9]等人提出用關(guān)系質(zhì)量度量r2來預(yù)測精確度.r2是tag SNPs位點預(yù)測得到的單體型數(shù)與所有SNP位點理論上的單體型數(shù)之間的一個關(guān)系度量，該度量標(biāo)準(zhǔn)適用于直接從基因型推導(dǎo)出的單體型.這兩種評估標(biāo)準(zhǔn)均不適用于本文的算法，所以根據(jù)交叉驗證的特點提出了新的評估標(biāo)準(zhǔn).

為了提高算法的精確度，根據(jù)SNP位點的性質(zhì)，提出了評估tag SNPs精度的公式，基本原理是基于獲得的tag SNPs位點對其余非tag SNPs位點預(yù)測其精度.算法使用精確度（Accuracy，acc）和敏感性（Sensitivity，sen）[10]作為tag SNPs評估標(biāo)準(zhǔn).

3.2RCACO算法原理及流程

基于罰函數(shù)的集合覆蓋蟻群算法取得了良好的效果.結(jié)果表明，PCACO算法利用蟻群算法發(fā)現(xiàn)較好解的性質(zhì)，優(yōu)化了全局能力，且能夠快速得到可行解，但最優(yōu)解的精確度沒有明顯的大變化.針對此問題，提出另外一種改進(jìn)方法：基于隨機(jī)擾動特性的集合覆蓋蟻群算法（RCACO）.

從ACO算法中的轉(zhuǎn)移概率出發(fā)，經(jīng)過深入分析后，提出了一種新的轉(zhuǎn)移策略，即隨機(jī)擾動的蟻群算法.新的轉(zhuǎn)移概率具有自適應(yīng)性和很強(qiáng)的擾動特性.RCACO主要包含兩個方面的改進(jìn)：一是設(shè)計了相應(yīng)的隨機(jī)選擇策略和擾動策略；二是提出倒指數(shù)曲線所描述的擾動因子.實驗表明：采用新轉(zhuǎn)移概率的RCACO算法的精確度要高于PCACO算法，而計算時間差別不大，表現(xiàn)出了更好的全局搜索能力.除此之外，對RCACO算法中參數(shù)的選取方法和取值范圍也進(jìn)行了探討.

從轉(zhuǎn)移概率公式可以看出，ACO算法的主要依據(jù)就是信息素正反饋和啟發(fā)因子的有機(jī)結(jié)合，基于此，采用了更為簡潔的轉(zhuǎn)移策略，公式如下：

其中，γ為擾動因子，螞蟻將選擇轉(zhuǎn)移概率最大的一條路徑.值得注意的是，如果γ取固定值，仍會出現(xiàn)停滯現(xiàn)象，因此采用可變的擾動因子.擾動因子的取值要根據(jù)要考慮以下兩個方面：

（1）螞蟻總是選擇轉(zhuǎn)移概率最大的路徑，當(dāng)樣本數(shù)目較大時，很難在短時間內(nèi)找出一條較好的路徑，所以在最初的迭代中，為了加速算法的收斂，我們同樣應(yīng)讓γ取較大的值，才會使較好路徑上的信息量高于其他路徑.

（2）若γ一直不變必將導(dǎo)致隨后的搜索出現(xiàn)停滯現(xiàn)象.因此，在之后的搜索過程中應(yīng)適當(dāng)減小γ的值，提高選擇的多樣性，即起到一定的擾動作用，其次也可使收斂走向平緩.

本文采用倒指數(shù)關(guān)系曲線來設(shè)置γ，公式如下：

γ=a×eb/k（k=1,2,…M）

其中，M表示最大迭代次數(shù)，a、b表示擾動尺度因子.為保證算法的隨機(jī)性，隨著迭代次數(shù)的逐漸增大，γ的值會慢慢接近系數(shù)a，且系數(shù)b的取值決定了曲線接近系數(shù)a的快慢.

為進(jìn)一步緩解算法的局部停滯現(xiàn)象，在迭代過程中引入具有隨機(jī)選擇策略的動態(tài)轉(zhuǎn)移概率.RCA?CO為了避免漏掉最優(yōu)的一條路徑，會對具有最大信息量的路徑單獨計算概率.所以，所設(shè)計的具有隨機(jī)擾動特性的轉(zhuǎn)移概率有以下四種情況：

s=max（Pij（k））所對應(yīng)的SNP位點集.

γ是具有倒指數(shù)性質(zhì)的擾動因子；r0、p則都是（0，1）中均勻分布的隨機(jī)數(shù).轉(zhuǎn)移概率公式表明，某只螞蟻在迭代過程中可以選擇多條路徑，對于信息素濃度最大的路徑，應(yīng)選用p＞r0的公式，體現(xiàn)了其確定性；其它可選路徑，則隨機(jī)選擇，這也導(dǎo)致了轉(zhuǎn)移概率具有較強(qiáng)的隨機(jī)性，該公式體現(xiàn)了確定性選擇和隨機(jī)選擇相結(jié)合的形式，它們的共同作用使RCACO有更強(qiáng)的全局搜索能力.

3.3RCACO算法參數(shù)的選取

RCACO算法中，參數(shù)的選取對計算結(jié)果有很大的影響，算法所涉及的參數(shù)主要有α、ρ、Q、r0、a、b等.對于這些參數(shù)，并沒有最佳組合，都是經(jīng)驗和具體問題試湊得來的.針對tag SNPs選取問題為例對RCACO進(jìn)行了分析，通過大量的仿真實驗確定了某些參數(shù)的最佳取值范圍.

選取參數(shù)范圍的步驟大致如下：

（1）實驗發(fā)現(xiàn)，對算法影響較大的是α和Q，且相應(yīng)的取值范圍也較大.由于ρ和r0對算法的影響較小，取值一般較固定，介于（0-1）.因此，隨機(jī)確定一組ρ和r0，接下來再調(diào)整α和Q，來獲到較理想的解.

（2）在基本確定α和Q后，進(jìn)行調(diào)整ρ和r0來尋找更優(yōu)的解.得到穩(wěn)定的結(jié)果后，將ρ和r0固定，再反過來調(diào)整α和Q值，如此反復(fù)，直到確定一組較為理想的參數(shù)組合.這種方法雖然繁瑣，卻效果明顯，具有一定的普遍意義.

經(jīng)此步驟，選取了以下參數(shù)的取值范圍，在此范圍時，算法可得到較好的解.

參數(shù)α表示信息量對螞蟻選擇路徑的影響程度，參數(shù)Q的大小則決定了信息量的更新程度.此算法中，α的取值范圍為0.1～0.5，Q本文取值為100.

ρ的取值不宜過小或過大.當(dāng)ρ＜0.5，將不能很好地利用所積累的信息；當(dāng)ρ＞0.8取值過大時，信息素密度則不能有效更新.ρ如果失去調(diào)節(jié)作用將導(dǎo)致會收斂于較差解，建議ρ的取值范圍為0.5～0.8.r0作為決定信息素濃度的臨界點，r0值的取值同樣不能過小或過大，當(dāng)r0＜0.3，則易丟掉路徑較優(yōu)的解，起不到該有的作用；當(dāng)r0＞0.8，則容易陷入局部最優(yōu)解，r0的取值范圍為0.3～0.8.

（3）擾動尺度因子a的取值范圍是1～10；b的取值范圍為1～5，本文中（a,b）較優(yōu)的組合有（3，2），（4，3），（5，2）.

4　仿真實驗及結(jié)果分析

算法的終止條件是迭代次數(shù)達(dá)到1 000次，同時針對參數(shù)對算法性能的影響采用的是改變參數(shù)的策略，且每組數(shù)據(jù)實驗30次取平均做比較.

采用1.3所表示的兩個實驗集，同時與GA、PSO 及PCACO三種方法進(jìn)行比較.具體實驗結(jié)果如下：

表1　仿真實驗結(jié)果1（α=0.3，r0=0.7，ρ=0.6，（a,b）=（3,2））

表2　仿真實驗結(jié)果2（α=0.4，r0=0.7，ρ=0.5，（a,b）=（4,3.2））

表3　仿真實驗結(jié)果3（α=0.4，r0=0.8，ρ=0.6，（a,b）=（5,2））

由上面3個表1、2、3可明顯看出，PCACO算法與RCACO算法的tag SNPs個數(shù)和運行時間均差別不大，但RCACO算法在精確度上卻顯著提高.

5　總結(jié)

特別針對標(biāo)準(zhǔn)蟻群算法中的轉(zhuǎn)移概率進(jìn)行了研究和探討，并提出了一種新的轉(zhuǎn)移策略，由此設(shè)計出一種隨機(jī)擾動蟻群算法RCACO，將其應(yīng)用在組合優(yōu)化問題上.該轉(zhuǎn)移概率帶有一定的自適應(yīng)性，并且具有很強(qiáng)的擾動特性.RCACO算法主要包含兩個方面：一是提出了擾動因子，并采用倒指數(shù)曲線來描述；二是設(shè)計出相對應(yīng)的擾動策略和隨機(jī)選擇策略.結(jié)果表明：這種新的轉(zhuǎn)移概率可以有效地克服算法容易出現(xiàn)停滯現(xiàn)象的缺陷，擁有了更好的全局搜索能力；有效的提高了算法運算效率和計算精度.除此之外，該算法還對該算法中參數(shù)的選取方法及取值范圍進(jìn)行了研究.

[1]Klein RJ,Zeiss C,Chew EY,et al.Complement factor H polymor?phism in age-related macular generation[J].Science,2005,308 （5720）：385-389.

[2]Carlson C,EberleM A.Selectingamaximally informative setofsin? gle-nucleotide polymorphisms for association analyses using link?age disequilibrium[J].Am JHum Genet,2004,74（1）：106-120.

[3]Phuong TM,Lin Z,Altman R B.Choosing SNPs using feature se?lection[C].Proc IEEEComputSystBioinform Conf,2005：301-309.

[4]Liu H,Motoda H.Feature selection forknowledge discovery and da?tamining[M].Boston：Kluwer Acdcemic Publishers,1998.

[5]WealeM.Selection and evaluation of tagging SNPs in the neuronalsodium-channel gene SCN1A：implications for linkage-disequilib?rium genemapping[J].Am JHum Genet,2003,73（3）：551-565.

[6]Stram D O,Leigh PC,Bretsky P,etal.Modeling and E-M estima?tion of haplotype specific relative risks from genotype data for a casecontrol study of unrelated individuals[J].Hum Heredity,2003, 55（4）：179-190.

[7]Youshikawa M,Amagasa T.Xrel：A path-based approach to stor?age and retrieval of XML documents using relational database[J].ACM Trans Internet Technology,2001.1（1）：110-141.

[8]Wen L,Zhang R,Lu X L.The design of efficient XML document model[C].Proceedings of the First International Conference on Ma?chine Leamingand Cybemetis,Beijing,2002：1102-1106.

[9]Dorigo M,Maniezzo V,Colorni A.Positive Feedback as a Search Strategy[M].Technical Report 91-016,Dip.Elettronica,Politeeni?co diMilano,1991.

[10]Dorigo M.Optimization,Learning,and Natural Algorithms（in Ital?ian）[D].Dip Elettronica,Politecnoco diMilano,1992.

（編校：許潔）

A Collection of Random-Perturbation Characteristics Covered Ant Colony Algorithm to Identify tag SNPs

WANG Limei1,WANG Longxiang2,ZHENGChengyou3
（1.Department ofMathematicsand Physics,Lincang Teachers'College,Lincang,Yunnan 677000,China；2.College ofComputerand Information Technology,Fujian Agriculture and Forestry University,Fuzhou,Fujian 350002,China；3.College ofMechanicsand Con?trol Engineering,Guilin University ofTechnology,Guilin,Guangxi541000,China）

Tag SNPs carriesmost of the genetic information of SNPs data set,which makes it significant to search tag SNPs.However,identifying tag SNPs from SNPs data set costs a huge amountof computation so that traditionalmethods are inefficientand expensive,and it turns difficult to obtain optimal solutions in case of complicated set cover problems.Since ant colony algorithms（ACO）work well in searching near-optimal solution,a new algorithm is proposed in searching tag SNPs,which combine setcoveringwith ACO based on random-perturbation（RCACO）.Experimental resultson simu?lated data sets show that the proposed algorithms achieve higher accuracy with less time consumption than PSO and GA algorithmsadopted in recentyears.

tag SNPs；setcover；antcolony algorithm；random-perturbation

TP301.6

A

1671-5365（2015）06-0081-05

2014-11-04修回：2014-12-09

王麗美（1987-），女，助教，碩士，研究方向為人工智能、數(shù)據(jù)挖據(jù)、生物信息

網(wǎng)絡(luò)出版時間：2014-12-10 09：16網(wǎng)絡(luò)出版地址：http：//www.cnki.net/kcms/detail/51.1630.Z.20141210.0916.004.html

引用格式：王麗美，王龍香，鄭程友.利用隨機(jī)擾動特性的集合覆蓋蟻群算法識別tag SNPs[J].宜賓學(xué)院學(xué)報,2015,15（6）：81-85.