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

王麗美，王龍香，鄭程友（.臨滄師范高等專科學校數理系，云南臨滄677000；.福建農林大學計算機與信息學院，福建福州5000；.桂林理工大學機械與控制工程學院，廣西桂林54000）

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

王麗美1，王龍香2，鄭程友3
（1.臨滄師范高等專科學校數理系，云南臨滄677000；2.福建農林大學計算機與信息學院，福建福州350002；3.桂林理工大學機械與控制工程學院，廣西桂林541000）

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

tag SNPs；集合覆蓋；蟻群算法；隨機擾動

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.

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

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

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

1　tag SNPs

1.1數據編碼

高通量基因芯片技術迅猛發展，使得海量SNP數據可通過其進行基因分型，國際人類基因組單體型圖計劃（HapMap）為科學研究貢獻了規模最大的SNP數據.構建人類DNA序列的多態位點常見模式是HapMap計劃的最終目標，即單體型圖[2-3].文章使用的SNP數據是經PHASE軟件處理的HapMap的單體型數據.

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

1.2tag SNPs獲取

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

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

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

（2）任一tag SNP位點與其關聯位點間的平均LD值應大于一定閾值（設定為0.6～0.8）；

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

1.3實驗數據集

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

2　集合覆蓋蟻群思想

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

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

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

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

3.1算法的評估準則

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

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

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

3.2RCACO算法原理及流程

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

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

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

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

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

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

本文采用倒指數關系曲線來設置γ，公式如下：

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

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

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

s=max（Pij（k））所對應的SNP位點集.

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

3.3RCACO算法參數的選取

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

選取參數范圍的步驟大致如下：

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

（2）在基本確定α和Q后，進行調整ρ和r0來尋找更優的解.得到穩定的結果后，將ρ和r0固定，再反過來調整α和Q值，如此反復，直到確定一組較為理想的參數組合.這種方法雖然繁瑣，卻效果明顯，具有一定的普遍意義.

經此步驟，選取了以下參數的取值范圍，在此范圍時，算法可得到較好的解.

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

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

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

4　仿真實驗及結果分析

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

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

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

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

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

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

5　總結

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

[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-），女，助教，碩士，研究方向為人工智能、數據挖據、生物信息

網絡出版時間：2014-12-10 09：16網絡出版地址：http：//www.cnki.net/kcms/detail/51.1630.Z.20141210.0916.004.html

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