基于蚁群算法的复杂疾病上位性分析方法

吴蓉晖+卢友敏

收稿日期：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.