基于蟻群算法的復雜疾病上位性分析方法

吳蓉暉+盧友敏

收稿日期：20130930

基金項目：湖南省科技計劃資助項目（2014FJ3079）

作者簡介：吳蓉暉（1967-），女，河南太康人，湖南大學副教授，博士

通訊聯系人，Email：55251983@qq.com

摘要：針對全基因組規模的上位性分析中存在的問題，首先采用基于多準則融合的過濾法對大量變異位點進行篩選以過濾無關位點，并結合蟻群算法對變異位點進行上位性分析，從而進一步剔除冗余位點，最后采用支持向量機作為上位性與復雜疾病關系的分類模型.實驗結果表明，先過濾再分類的策略，不僅大大降低了上位性時間復雜度，并且在分類準確度上也有一定程度提高.

關鍵詞：復雜疾??；上位性；支持向量機

中圖分類號：TP399 文獻標識碼：A

An Epistasis Analysis Method of Complex

Diseases Based on Ant Colony Algorithm

WU Ronghui1， LU Youmin1，2

（1. College of Information Science and Engineering，Hunan Univ，Changsha，Hunan410082，China；

2. Dept of Computer Engineering，Huaihua Univ，Huaihua，Hunan418400，China）

Abstract： To solve the problem of epistasis analysis in genomewide， a filter method based on multiple criteria fusion was developed to remove the unrelated SNP loci. After that， ant colony algorithm was used to construct the SNP set with epistasis interaction. In the phase of constructing， a support vector machine was proposed to build the relationship between the SNP set and complex diseases. The experiment results show that， with multiple criteria evaluating each SNP and ant colony optimization， the prediction accuracy and running time have been improved， making it better than conventional methods.

Key words： complex disease； epistasis； support vector machines

隨著人類基因組計劃（HGP）測序工作的完成，生命科學的研究重點已經從確定 DNA序列組成轉移到了研究基因功能.由于復雜疾病[1]在人群中具有高死亡率及難以治愈等特點，使得復雜疾病成為醫學、生物學相關科研人員的重點研究對象.復雜疾病不同于孟德爾疾病，它的形成與發展通常涉及到多個基因的相互作用或者基因與環境的交互作用即上位作用.而從分子層次上看，上位作用即為基因調控網絡或生物化學代謝通路中的生物分子（例如 DNA，RNA 的蛋白質等）之間的物理相互作用[2].通常上位作用在基因型和疾病表型之間一般都表現為非線性關系，從而難以被檢測.在特殊情況下，單個基因與表型之間并沒有表現出相關性，但是當該基因與其他基因或者環境聯合分析時，則存在明顯的上位作用.因此，復雜疾病一般具有表型異質性、遺傳異質性等特點，使人們難以從根本上理解其致病機理.

全基因組范圍內的復雜疾病易感基因的發掘及其與疾病關聯方式的確定，將有利于更全面地理解復雜疾病發病機理，從而實現復雜疾病的預防、診斷和治療.盡管針對復雜疾病的SNP芯片已經產生海量的數據，但是由于該數據本身具有的特征維數高和上位性分析存在組合爆炸等特點，使得該研究中如何對數據進行有效降維，并保留關鍵的上位作用，并有效刻畫上位作用與復雜疾病之間關系，成為了復雜疾病的全基因組關聯研究的熱點.本文首先采用多準則融合策略對無關、冗余SNP位點進行過濾，然后采用蟻群優化算法進一步剔除冗余SNP位點，實現對數據的降維并找出與疾病相關的上位性組合，然后采用支持向量機作為分類模型.實驗表明，本文方法具有實用意義.

1全基因組關聯研究中存在的問題

復雜疾病上位性研究一般由數據預處理，上位性檢測以及分類評估3個階段構成.目前，研究人員在這3個階段，提出將關聯統計分析、機器學習等方法應用到該研究中，從而發展了很多上位性分析的模型及算法.

統計檢驗方法[3]如信息增益、方差檢驗和卡方檢驗等被用于上位性檢測，這些方法都暗含了各個特征SNP之間是相互獨立的這一假設，因此，在對特征進行評估時只考慮了特征與疾病性狀之間的關系，而忽略了特征與特征之間的相互作用，因此對于評估可能包含上位作用的生物數據存在準確率較低等缺點.在眾多機器學習算法中，決策樹算法是較早被確認為是識別SNPSNP相互作用的有用工具，但是該類方法只應用于相對較小的數據集.為了解決較大規模數據集上的上位性分析，Chen等[4]研究了隨機森林中的統計效率，用于分析包含了成百上千個候選SNPs的疾病數據集.目前，雖然這些方法具有一定的優勢，但是仍然存在時間復雜度高、分類準確率低、假陽性高等不足.

針對以上存在的問題，當前已有一些研究提出先過濾掉冗余、無關的SNP再進行上位性分析的策略.如果單個 SNP 對疾病具有統計可檢測的主效應，那么可以檢測出其與疾病之間的關聯（association），然后過濾掉低關聯強度的SNP，從而縮小后續上位性組合檢測中所需搜索的組合空間.但是，某種情況下可能出現純上位性現象，傳統單SNP分析方法可能剔除了這些位點，而導致后續分類準確低，并且由于組合爆炸，對所有 SNP 組合進行窮舉搜索大大增加了計算復雜度.因此，亟需一種有效的篩選方法剔除無關、冗余SNP位點，并有效保留純上位作用SNP位點及主效應SNP位點，在保證分類準確度的基礎上降低計算復雜度.

2基于蟻群算法的分析方法

基于分類的復雜疾病上位性分析有一個基本假設：如果某一SNP上位性組合與復雜疾病的形成相關，那么通過分析個體在這些SNP位點上的組合模式，則可以判別個體是否患病.利用該假設，對復雜疾病上位性分析轉換為以下數學模型：

max C（S′）

min S′.（1）

其中S′表示構成上位性的SNP組合；C（S′）為SNP組合G′的分類能力.在具有相同分類能力的不同SNP組合之間選擇較小的SNP組合，是符合復雜疾病研究的發展規律.

由于復雜疾病SNP芯片數據具有的特征維數高以及上位作用等特點，為了保證在對SNP數據進行降維基礎上，同時保留其中的關鍵上位組合，并有效對SNP上位性組合與復雜疾病之間建立映射，本文提出先過濾后分類的分析框架，如圖1所示.

2.1多準則融合過濾

在SNP數據的上位性分析中，面臨的最大挑戰是SNP組合空間的爆炸，而對所有的SNP組合進行窮舉分析，則是NP難問題.為了降低上位性分析時間復雜度，一種有效策略是對復雜疾病的患病對照數據進行分析，然后利用某種過濾規則去除噪聲、無關SNP位點，這些位點主要表現為在對照樣本中與患病樣本中的SNP基因型基本一致，則可以認為它們是與復雜疾病無關的位點.

為了防止一些易感SNP因為單位點的弱效應被過濾，本文提出采用多準則融合策略綜合地、更為全面地評價每個SNP位點.主要原因有兩點：第一，借鑒集成多個弱分類器可以顯著提高分類的能力這一事實，采用多準則融合可以更為準確地評價每個SNP組合，從而降低假陽性；第二，因每個評價規則都具有獨特的傾向性，從而導致容易陷入局部最優，而通過融合多種特征，可以更好地尋找全局最優的上位性組合.本文采用對信噪比[5]、Relief[6]和卡方檢驗[7]準則進行融合的方法來對SNP數據篩選過濾.

1）信噪比.廣義來講，信噪比（Signal to Noise Ratio）是指有效信息被破壞的程度，本文中用該指標作為度量每個SNP位點對樣本分類貢獻的大小.

d（s）=μ+s-μ-sσ+s+σ-s.（2）

式中：d（s）為SNP位點s的打分值；μ+s和μ-s分別為不同類別中s的基因型平均值；σ+s和σ-s為基因型的標準差.從式（2）可以看出，SNP位點打分值越高，表明它在不同類間的差異越大或類內變化率越小，那么其對于分類的貢獻越大.

2）Relief可作為一種基于權值的單位點排序方法，它通過多次迭代來評價位點的相關性，每次迭代過程中，首先隨機地從數據集中選擇一個樣本X，以及同一類中的X與它最近的鄰居H和不同類中與X最近的M，然后利用公式（3）計算H與M的差別，從而更新所有特征的相關性.

W（j）=W（j）-diff（j，X，H）n+diff（j，X，M）n.

（3）

式中：W（j）為SNP位點j在X與目標之間的相關性，迭代初始時被設置為0；diff（j，x，x′）為SNP位點j在樣本x與x′上的差別.

diff（j，x，x'）=0：x的j位點的基因型與x'基因型相同，

1：相同.（4）

3）Pearson卡方檢驗是Karl Pearson提出的用于檢驗樣本中某一些事件發生的概率是否等于理論分布的一種檢驗方法，也稱為擬合優度檢驗.對于一般的I×J列聯表，Pearson檢驗可以表示為：

x2=∑i（Oi-Ei）2Ei.（5）

式中：Oi是第i個格子基因型觀測到的頻數；Ei是該基因型的理論頻數；∑對所有的格子求和.

由于以上3個標準對每個SNP位點評價的度量值不統一，本文首先對所有SNP位點分別按照以上3種不同準則所對應的重要程度進行排序，則每個位點i將有3種排名值分別為di，wi以及xi，然后將排名值相加得一個Si并排序，則并排序的名次綜合反映了每個SNP位點的重要程度，然后設定一個閾值（本文設為100），大于該閾值的位點則被過濾掉.

2.2上位性分析

蟻群算法[8]已成功應用于各個領域中的組合優化NP難問題，如旅行商問題、圖著色問題以及微陣列特征選擇等.它具有天然的并行性，通過并行策略能極大提高運算速度.

人工蟻群算法由多個并行的螞蟻構成，螞蟻之間通過概率密度函數進行通信，該函數由權重因子以及信息素濃度構成.在蟻群算法用于上位性分析中，第k次迭代中位點i的選擇概率被定義為：

pki（t）=τiαηiβ∑i∈R[τi]α[ηi]β，i∈R.

0，否則.（6）

式中：α為信息素權值；β為啟發因子的權值；τi為第i個位點上信息素濃度；每個位點的啟發性信息ηi都被置為常數1. 初始化時，每個位點都設置為相等的初始濃度值τ0.利用式（6），每只螞蟻m從所有SNP位點中選擇n（1≤n≤SNP位點數-1）只螞蟻分別構造一個SNP上位性組合Sm，而每個SNP組合的分類性能則作為下一輪迭代中信息素更新的依據，更新函數為式（7）.其中，該過程中采用支持向量機[9]作為分類學習模型.

τi（t）=（1-ρ）τi（t-1）+Δτi（t-1）.（7）

式中：ρ為大于0小于1的信息素揮發因子；Δτi（t-1）為第t-1次迭代中的最佳上位性組合Smax的分類準確率.如果位點i屬于Smax，那么在第t次迭代中則按照式（7）改變其信息素，如果不屬于，則Δτi（t-1）等于0.以下是蟻群算法的偽代碼.

蟻群算法

輸入：復雜疾病SNP數據集

輸出：SNP上位性組合位點

Step1：數據預處理；

Step2：初始化蟻群算法參數如蟻群規模iAntCount，最大迭代次數maxIteration；

Step3：每只螞蟻m根據概率選擇函數構造上位性組合Sm；

Step4：利用支持向量機對每個Sm采用五折交叉驗證法評價分類性能；

Step5：記錄最優分類性能的上位性組合Smax，更新每個位點信息素；

Step6：判斷是否滿足終止條件，如果不滿足則回到Step3，否則執行Step7 ；

Step7：輸出上位性組合位點，退出程序.

2.3分類評估方法

支持向量機（Support Vector Machines，SVM）[9]是一種成熟的模式識別模型，它遵循結構風險最小化原則，在小樣本學習中體現出卓越優勢，并且，其計算復雜度僅僅與支持向量數目有關，而與輸入空間維數無關，因此，它非常適宜處理復雜疾病SNP芯片數據這種典型的高維、少樣本數據.

為了降低峰值現象，從而更可信地度量分類準確率，本文采用五折交叉驗證法.五折交叉驗證法首先將樣本數據集分為5個子集，然后將其中4個作為訓練集，另外一個作為測試集，進行一次分類測試，每個子集將被用作一次測試集，依次循環迭代5次，最后對5次分類準確度求平均值，以此評價上位性SNP組合的分類準確度.平均值的計算方法為：

Acc=∑5i=1pi5. （8）

式中：pi為第i次迭代的分類準確度.

3仿真實驗及分析

為了合理地評價該改進方法在上位性分析中的有效性，分別在分類準確率以及運行時間指標上對本文方法進行了驗證評價.首先采用C++實現了本文算法，然后在WIN7環境下執行測試，測試環境的硬件配置為2 G內存，AMD雙核2.80 GHz.

3.1數據集

由于有采用的成本及涉及患者隱私的情況存在，使得復雜疾病分析的真實數據集中樣本量小，同時，有些真實復雜疾病數據中真正的致病基因，或者不同實驗分析的結果存在不一致性，因此無法用于驗證生物信息學方法得到的結果，所以現有研究中通常采用仿真數據評價機器學習方法.仿真數據生

成需要設置幾個重要參數，如基因的外顯率函數、遺傳度以及次要等位基因頻率（MAF）等.本文仿真數據集來自參考文獻[10]，下載地址為http：//discovery.dartmouth.edu/epistatic_data/.本文下載了2種不同參數的數據集，數據集的詳細介紹列于表1.

3.2實驗分析

利用以上數據集，用本文方法與SNPRuler 算法[11]進行比較驗證.SNPRuler算法是基于預測規則推理和兩階段（twostage）策略設計的，通過預測規則學習特征與類變量之間的關系，然后在測試數據上預測類標簽.其上位性檢測中利用規則學習，原因在于：首先，上位性組合蘊含了一些模式或預測規則；再者，評估規則的尋找更為容易，更快捷.因此，SNPRuler方法通過挖掘預測規則來發現潛在的上位性組合.

SNP組合的上位性可以通過個體性狀的分類性能來評價，本文采用五折交叉驗證法驗證不同SNP組合的分類準確度.在以上2個數據集中的分類準確度的實驗結果分別如圖2和圖3所示.從圖2和圖3可知，在不同數據集上，本文方法的分類準確度平均高于SNPRuler 算法2%.通過分析可以發現，外顯率對上位性分析也有影響，外顯率高則更容易發現真正的致病位點，分類準確度更高.

2種方法運行時間比較結果如圖4所示，運行時間分別對應著不同方法尋找到最優上位性組合即具有最高分類準確度SNP組合所消耗的時間.由圖4可知，本文方法通過先過濾掉大量無關SNP后再搜索，使得上位性分析的運行時間總體看來大致接近SNPRuler 算法的一半，較大地提高了上位性分析的效率.

4結束語

為了探索與復雜疾病發生、發展相關的上位性，針對現有上位性分析方法存在高運算成本、假陽性高等不足，本研究提出了一種基于蟻群算法的上位性分析方法，它包含過濾以及上位性分析兩個階段，在過濾階段剔除大量無關位點后，使上位性分析過程的SNP組合空間大大縮小，使得高階上位性分析成為可能.并且，過濾階段采用了多準則融合策略，更為全面、綜合地評價每個SNP位點，能有效保留單個弱效SNP位點.實驗表明，本文方法在分類準確度以及運行時間上都有一定程度提高，具有實用意義.

參考文獻

[1]孫玉琳，趙曉航.復雜疾病基因定位策略與腫瘤易感基因鑒定[J].生物化學與生物物理進展，2005， 32（9）：804-809.

SUN Yulin，ZHAO Xiaohang. The genetic mapping of complex diseases and the identification of tumorssusceptible genes[J]. Prog Biochem Biophys， 2005， 32（9）：804-809. （In Chinese）

[2]王文菊， 尹先勇， 崔勇， 等. IL23 /Th17 通路基因上位性作用與漢族人銀屑病易感性研究[J]. 實用醫院臨床雜志， 2013， 10（1）：1-3.

WANG Wen ju， YIN Xian yong， CUI Yong， et al. Genes in IL23 /Th17 pathway have epistatic effects on psoriasis susceptibility in Chinese Han population[J]. Practical Journal of Clinical Medicine， 2013， 10（1）：1-3. （In Chinese）

[3]GENIN E， COUSTET B， ALLANORE Y，et al. Epistatic Interaction between BANK1 and BLK in rheumatoid arthritis： results from a large transethnic metaanalysis[J]. Plos One，2013， 8（4）：e61044.

[4]CHEN S H， SUN J，DIMITROV L， et al. A support vector machine approach for detecting genegene interaction[J].Genetic Epidemiology， 2008，32：152-167.

[5]阮曉鋼， 晁浩. 腫瘤識別過程中特征基因的選取[J]. 控制工程， 2007， 14（4）：374-375.

RUAN Xiaogang， CHAO Hao. Selection of feature genes in cancer classification[J]. Control Engineering of China，2007，14（4）：374-375. （In Chinese）

[6]ROBNIKIKONJA M， KONONENKO I. Theoretical and empirical analysis of relief and relief[J]. Machine Learning， 2003， 53（1）： 23-69.

[7]WAN Xiang，YANG Can，YANG Qiang， et al. The complete compositional epistasis detection in genomewide association studies[J]. BMC Genetics，2013， 14（7）：1-11.

[8]吳建輝，章兢，劉朝華. 基于蟻群算法和免疫算法融合的TSP問題求解[J].湖南大學學報：自然科學版，2009，36（10）：82-85.

WU Jianhui，ZHANG Jin，LIU Zhaohua.Solution of TSP problem based on the combination of ant colony algorithm and immune algorithm[J].Journal of Hunan University：Natural Sciences， 2009， 36（10）：82-85.（In Chinese）

[9]文益民，王耀南，張瑩.基于分類面拼接的快速模塊化支持向量機研究[J].湖南大學學報：自然科學版，2009，36（3）：46-49.

WEN Yimin，WANG Yaonan，ZHANG Ying.On pasting small fast modular SVMs for classification[J]. Journal of Hunan University：Natural Sciences，2009，36（3）：46-49. （In Chinese）

[10]WANG Y， LIU G M.An empirical comparison of several recent epistatic interaction detection methods[J]. Bioinformatics，2011， 27（21）： 2936-2943.

[11]WAN Xiang，YANG Can，YANG Qiang，et al. Predictive rule inference for epistatic interaction detection in genomewide association studies[J]. Bioinformatics， 2010，26 （1）：30-37.

[4]CHEN S H， SUN J，DIMITROV L， et al. A support vector machine approach for detecting genegene interaction[J].Genetic Epidemiology， 2008，32：152-167.

[5]阮曉鋼， 晁浩. 腫瘤識別過程中特征基因的選取[J]. 控制工程， 2007， 14（4）：374-375.

RUAN Xiaogang， CHAO Hao. Selection of feature genes in cancer classification[J]. Control Engineering of China，2007，14（4）：374-375. （In Chinese）

[6]ROBNIKIKONJA M， KONONENKO I. Theoretical and empirical analysis of relief and relief[J]. Machine Learning， 2003， 53（1）： 23-69.

[7]WAN Xiang，YANG Can，YANG Qiang， et al. The complete compositional epistasis detection in genomewide association studies[J]. BMC Genetics，2013， 14（7）：1-11.

[8]吳建輝，章兢，劉朝華. 基于蟻群算法和免疫算法融合的TSP問題求解[J].湖南大學學報：自然科學版，2009，36（10）：82-85.

WU Jianhui，ZHANG Jin，LIU Zhaohua.Solution of TSP problem based on the combination of ant colony algorithm and immune algorithm[J].Journal of Hunan University：Natural Sciences， 2009， 36（10）：82-85.（In Chinese）

[9]文益民，王耀南，張瑩.基于分類面拼接的快速模塊化支持向量機研究[J].湖南大學學報：自然科學版，2009，36（3）：46-49.

WEN Yimin，WANG Yaonan，ZHANG Ying.On pasting small fast modular SVMs for classification[J]. Journal of Hunan University：Natural Sciences，2009，36（3）：46-49. （In Chinese）

[10]WANG Y， LIU G M.An empirical comparison of several recent epistatic interaction detection methods[J]. Bioinformatics，2011， 27（21）： 2936-2943.

[11]WAN Xiang，YANG Can，YANG Qiang，et al. Predictive rule inference for epistatic interaction detection in genomewide association studies[J]. Bioinformatics， 2010，26 （1）：30-37.

[4]CHEN S H， SUN J，DIMITROV L， et al. A support vector machine approach for detecting genegene interaction[J].Genetic Epidemiology， 2008，32：152-167.

[5]阮曉鋼， 晁浩. 腫瘤識別過程中特征基因的選取[J]. 控制工程， 2007， 14（4）：374-375.

RUAN Xiaogang， CHAO Hao. Selection of feature genes in cancer classification[J]. Control Engineering of China，2007，14（4）：374-375. （In Chinese）

[6]ROBNIKIKONJA M， KONONENKO I. Theoretical and empirical analysis of relief and relief[J]. Machine Learning， 2003， 53（1）： 23-69.

[7]WAN Xiang，YANG Can，YANG Qiang， et al. The complete compositional epistasis detection in genomewide association studies[J]. BMC Genetics，2013， 14（7）：1-11.

[8]吳建輝，章兢，劉朝華. 基于蟻群算法和免疫算法融合的TSP問題求解[J].湖南大學學報：自然科學版，2009，36（10）：82-85.

WU Jianhui，ZHANG Jin，LIU Zhaohua.Solution of TSP problem based on the combination of ant colony algorithm and immune algorithm[J].Journal of Hunan University：Natural Sciences， 2009， 36（10）：82-85.（In Chinese）

[9]文益民，王耀南，張瑩.基于分類面拼接的快速模塊化支持向量機研究[J].湖南大學學報：自然科學版，2009，36（3）：46-49.

WEN Yimin，WANG Yaonan，ZHANG Ying.On pasting small fast modular SVMs for classification[J]. Journal of Hunan University：Natural Sciences，2009，36（3）：46-49. （In Chinese）

[10]WANG Y， LIU G M.An empirical comparison of several recent epistatic interaction detection methods[J]. Bioinformatics，2011， 27（21）： 2936-2943.

[11]WAN Xiang，YANG Can，YANG Qiang，et al. Predictive rule inference for epistatic interaction detection in genomewide association studies[J]. Bioinformatics， 2010，26 （1）：30-37.