基于C3NET和图滤波器的基因特征选择算法

王 薇， 蒋俊正

(桂林电子科技大学 信息与通信学院,广西 桂林 541004)

如今，癌症的病发率越来越高，根据国际癌症研究机构最新发表的《2020年全球癌症统计报告》，2020年全球新发恶性肿瘤1 930万例，全球恶性肿瘤死亡病例约为1 000万例，癌症已经成为了全球第二大死因[1]。随着计算机技术和基因芯片技术的发展，海量的基因表达数据可以被获取，这为致癌机理的研究和癌症的早期诊断提供了一种全新的方法。然而，相对于可以大量获取的基因表达数据，可获得的用于分析基因数据特性的样本较少，且仅有一小部分的基因与癌症分类识别相关。因此，如何降低基因表达数据的维度，从成千上万的基因表达数据中筛选出分类能力高的基因，对基因表达数据的研究具有重要意义[2-3]。

特征选择是常用的降维方法之一，其主要思想是基于一定准则，筛选出符合要求的特征[4]。目前，许多学者已将特征选择应用到基因表达数据的降维中。Chris等[5]提出了最小冗余最大相关(minimum redundancy-maximum relevance, 简称MRMR)方法，并用于基因选择，该方法能有效减少冗余，并具有较好的泛化能力。Sun等[2]利用多个不同的滤波器以选择出具有不同分类能力的候选基因子集，然后使用交叉熵算法剔除候选基因子集中的冗余基因。Li等[6]将基因选择问题建模为一个多元优化问题，提出了一种多目标排序二元人工蜂群算法，对基因表达数据进行降维。然而，在基因表达过程中，一个基因会受到其他基因或者分子(如蛋白质)的调控作用，并且这个基因又可能调控其他基因的表达[7]。但是，现有的特征选择方法在对基因表达数据进行降维时，大多未考虑基因之间的调控作用，仅仅依据特定的准则来选取基因，通过这种方式选择出的基因很可能缺失基因之间调控作用的信息，不利于癌症的致癌机理研究。因此，如何对特征选择方法进行改进，使其在筛选基因时可以纳入基因之间的调控作用，是一个值得研究的问题。

基因之间的调控作用可通过推断基因调控网络来实现。利用基因表达数据推断基因调控网络的模型主要有3类：贝叶斯网络模型、布尔网络模型、常微分方程模型[7-9]。由于基因在表达时受不同的基因调控，基因调控网络的结构是非规则的。随着信号处理理论的发展，图信号处理(graph signal processing,简称GSP)理论被用来处理非规则网络结构上的数据。此外，传统信号处理中一些重要的理论分析概念和方法也被拓展到图信号处理理论中，并衍生出了图傅里叶变换(graph Fourier transform,简称GFT)[10]、图采样[11]、频域分析[12]、图滤波器[13]、图滤波器组[13-15]等图信号处理理论分析工具。在图信号处理中，图模型可以刻画节点之间的相似性等关系，因此基因间的调控作用可通过图模型来刻画。若将基因作为图上节点，推断出基因调控网络可建模为图模型中的邻接矩阵，那么在选择具有高分类能力的基因时，可利用图滤波器等理论工具构建新的特征选择方法，使其不仅能选择出分类能力高的基因，也能保留基因表达时的调控关系。

为了在筛选分类能力强的基因时保留基因间的调控关系，提出了一种基于C3NET(conservative causal core，简称C3NET)和图滤波器的基因特征选择算法。基因之间的调控关系可用基因调控网络表示，因此利用C3NET算法推断出基因表达数据集的基因调控网络，以此保留基因间的调控关系。此外，相较于冗余基因，分类能力高的基因在不同的样本(病人)类别中的基因表达值差异较大。依据图信号处理理论，这些分类能力高的基因所携带的信息在图频域呈现高频特性，可利用高通滤波器得到分类能力高的基因。因此，将基因调控网络建模为图上邻接矩阵，同时将基因表达数据中的基因建模为图上节点，将基因数据建模为图信号。通过设计高通图滤波器对基因数据进行滤波，并根据图傅里叶变换提出了一种评估基因分类能力的指标Duk，筛选出滤波后分类能力高的基因。仿真实验结果表明，本算法筛选出的基因在不同的分类器中的分类准确率优于其他对比的算法。

1 图信号处理

给定一个无向图G=(V,E,A)，图信号f=[f1,f2，…，fN]T是由图上每个节点的信号值组成的N维向量。与传统信号处理类似，图信号处理理论中也有相应的图傅里叶变换和图滤波器。对于图信号f，其图傅里叶变换GFT定义为

(1)

其中，U=[u1,u2,…,uN]为L的特征向量矩阵。同时，逆-图傅里叶变换(inverse graph Fourier transform,简称iGFT)定义为

(2)

图滤波器有多种形式，常用的图滤波器为图拉普拉斯矩阵多项式的形式，即

(3)

其中，K为滤波器的阶数。由于Lk与L的特征向量相同，所以式(3)可写为

(4)

2 基因表达数据的图和图信号表示

一个基因表达数据集S∈RM×Q包含了M个样本(病人)的Q个基因数据，每个样本(病人)的类别信息用y∈RM×1表示，若数据集S包含了P个类别，则y的取值范围为[1,2,…,P]。

将样本(病人)的每个基因建模为图上节点，得到数据集S的基因图模型GS=(VS,ES,AS)，其中：VS={1,2,…,Q}为Q个节点(基因)集合，AS∈RQ×Q为图GS的邻接矩阵，ES为图GS上节点(基因)边的集合。目前，构建图模型的算法有很多种，如最近邻算法[16]、基于图学习的方法[17]等。图1为利用最近邻算法将Gastric数据集建模为图的示意图。

对于基因图模型GS=(VS,ES,AS)，将每个样本(病人)的基因数据建模为图信号，即xi=S(i,∶)，i=1,2,…,M，其中,S(i,∶)为基因表达数据集S的第i行，则可得到M个图信号。图2为将Gastric数据集的第一个样本(病人)x1建模为图信号的示意图。

图1 Gastric数据集图模型构建示意图

图2 Gastric数据集图信号建模示意图

3 基于C3NET和图滤波器的基因选择算法

基因表达数据具有高维度、小样本、冗余多的特点，如何从基因表达数据中筛选出分类能力较高的基因,对癌症的早期诊断具有重要意义。为此，提出了一种基于C3NET和图滤波器的基因特征选择算法。首先，利用C3NET算法推断基因表达数据集的基因调控网络；其次，将得到的基因调控网络作为基因图GS的邻接矩阵，计算其图拉普拉斯矩阵和图傅里叶变换，并定义评估基因分类能力的指标Duk;然后通过图滤波器对基因表达数据进行滤波;最后根据Duk的大小筛选出分类能力高的基因。

3.1 C3NET

C3NET是一种基于统计推断构建基因调控网络的算法，其基本思想是当2个基因之间的互信息至少是其中一个基因与其他所有基因的互信息的最大值时，2个基因才能相互连接[9]。C3NET算法主要分为2步。

第1步，计算基因之间互信息。对于2个随机变量X、Y，其互信息计算方式为

(5)

其中：ΩX、ΩY为随机变量X、Y的样本空间；p(x,y)为X，Y的联合概率分布；p(x)、p(y)分别为X、Y的边缘分布。实际上，互信息需要通过合适的估计器从数据中估计出来，使其接近总体的理论值，因此，使用参数高斯估计器估计互信息的值，

(6)

因此，对于一个基因表达数据集S∈RM×Q，利用式(6)计算任意2个基因之间的互信息，可得到一个互信息矩阵I∈RQ×Q，其元素I(i,j)表示第i和第j个基因的互信息值。

第2步，根据得到的互信息矩阵I，确定每个基因与其相连的邻居，以得到基因调控网络。给定一个全连接矩阵C∈RQ×Q，其所有元素C(i,j)均为1，给定阈值α,若I(i,j)<α，则令C(i,j)=0，将第i个基因的邻居集合定义为

NS(i)={j∶C(i,j)=1且j≠i}，

(7)

则基因表达数据集S的基因调控网络W∈RQ×Q可通过式(8)得到：

W(i,jc(i))=W(jc(i),i)=

(8)

其中，i=1,2,…,Q。

C3NET具体算法流程为

算法1C3NET算法

输入：全1矩阵C∈RQ×Q，全零矩阵W∈RQ×Q，阈值α；

输出：基因调控网络W；

根据式(7)计算任意2个基因之间的互信息，得到互信息矩阵I∈RQ×Q；

fori=1:Q

forj=1:Q

ifI(i,j)<α

C(i,j)=0

end

end

end；

fori=1:Q

Ns(i)={j:C(i,j)=1且j≠i}

ifNS(i)≠Ø

else

jc(i)=Ø

end

W(i,jc(i))=W(jc(i),i)=1

end；

return 基因调控网络W

3.2 基于C3NET和图滤波器的基因选择算法

首先，将C3NET算法得到的基因调控网络W建模为基因表达数据集S的基因图模型GS的邻接矩阵，即令AS=W。其次，计算拉普拉斯矩阵LS，并对LS进行特征分解，即LS=USΛSUST。然后，利用式(1)计算每个图信号的图傅里叶变换，得到所有病人的图傅里叶变换，并将其拼成矩阵

为了确定基因的分类能力，定义了计算基因分类能力的公式：

(9)

(10)

在图信号处理理论中，若图上节点的图信号与其邻居节点上的信号差异较大，则认为这是一个高频信号。与传统信号处理类似，若要保留图信号的高频信息，则需设计高频图滤波器对图信号进行滤波。由式(4)可知，图滤波器的频率响应为

(11)

(12)

因此，高通图滤波器的滤波器系数c可以通过求解如下优化问题得到:

(13)

其中：h=[λ0,λ1,…,λK]T；c=[c0,c1,…,cK]T。

在基因表达数据集中，具有较高分类能力的基因在不同样本(病人)类别中基因表达值差异较大，而分类能力较低的基因表达值在不同的类别中可能不会表现出明显的差异。因此，认为具有较高分类能力的基因是高频图信号，利用高通图滤波器过滤出分类能力高的基因。

本算法主要分为3步：第1步，利用C3NET算法推断基因表达数据集的基因调控网络；第2步，利用高通图滤波器对基因表达数据集进行滤波；第3步，根据Duk来筛选分类能力高的基因，基于C3NET和图滤波器的基因选择算法流程如下所示。

算法2基于C3NET和图滤波器的基因选择算法

输入：基因表达数据集S∈RM×Q，图滤波器的阶数K，筛选出的基因个数d；

输出：筛选后的基因表达数据集Y∈RM×d；

根据算法1得到基因表达数据集S∈RM×Q的基因调控网络W∈RQ×Q；

令AS=W；

计算归一化图拉普拉斯矩阵Lnor=I-D-1/2AD-1/2，并对其进行特征分解Lnor=UΛUT；

利用式(9)计算Duk,k=1,2,…,Q，筛选出最大的d个Duk值，并记录其序号k，组成集合index；

whilei≤ddo

end while

4 仿真实验结果分析

使用从公开数据库[18]中下载的2个基因表达数据集验证算法的有效性。数据集的具体信息如表1所示。

表1 基因数据集信息

在仿真实验中，分别用MATLAB自带的5个分类器native Bayes(NB)、SVM、random forest(RF)、KNN和discriminant analysis(DA)评估筛选出的基因子集的分类准确率。首先，为了验证图滤波器在基因选择时的有效性，分别对2种情况进行仿真：1)根据Duk大小，选择数据集中Duk最大的20个值所对应的基因；2)先使用高通图滤波器对数据集进行滤波，然后再筛选出Duk最大的20个值所对应的基因，其中，Gastric数据集中使用的高通图滤波器的阶数为K=5，Brain tumor数据集使用的高通图滤波器的阶数为K=10，实验结果如图3所示。

图3 经过滤波和未经滤波分类准确率对比

由图3可知，经过滤波后，根据Duk选择基因的分类准确率明显高于直接使用Duk，这是因为经过滤波后的图信号融合了其K阶邻居的信息，也就是说，经过滤波的基因，不仅包含其自身的数据信息，也包含了与其相关的基因的调控信息。如果一个基因已经发生了癌变，那么受其影响的基因也存在异常表达的可能性，而滤波的操作将这些信息聚合到已经发生癌变的基因上，使得发生癌变的基因与正常表达的基因的差异更加明显，区分度更高。因此，经过滤波后的基因的分类能力更高。

为了验证本算法的有效性，将本算法分别与NNG-GS[19]、MDG-GS[19]、CDG-GS[19]、LLE[20]、PCA[21]算法进行比较，表2、3分别为从Gastric数据集和Brain tumor数据集中筛选d=20个基因的实验结果。对于Gastric数据集，本算法的参数α=0.7，高通图滤波器的阶数K=5，对于Brain tumor数据集，本算法的参数α=0.7，高通图滤波器的阶数K=10，NNG-GS、MDG-GS、CDG-GS、LLE四种算法在2个数据集中的参数k均设置为k=3。

根据表2、3的仿真实验结果，对于Gastric数据集，本算法虽然在DA分类器中的分类准确率与NNG-GS算法相同，但在其他4个分类器中的分类准确率均是最高的。对于Brain tumor数据集，除了KNN分类器，本算法在其他4个分类器中的分类准确率也是最高的。此外，虽然在KNN分类器中的分类准确率较低，但本算法在5个分类器中的平均分类准确率为94.71%，不仅高于CDG-GS算法在KNN分类器中的分类准确率，而且在所有对比算法中平均分类准确率也是最高的。由于基因在表达时受不同基因调控，本算法利用高通图滤波器对基因数据集进行滤波，滤波后的基因获得了与其相关的基因调控信息，使得发生癌变的基因与正常表达的基因的差异更加明显，从图3的仿真对比结果也可看出，经过高通图滤波器滤波后的基因在不同分类器中的分类准确率更高。因此，相较于对比算法，高通滤波后的基因融合了更多基因信息，由此筛选出的基因具有更高的分类能力，可以达到较好的分类效果。

表2 Gastric数据集的分类准确率 %

表3 Brain tumor数据集的分类准确率 %

5 结束语

基因表达数据具有高维度、小样本、冗余多的特点，为了筛选出分类能力高的基因，提出了一种基于C3NET算法和图滤波器的基因特征选择算法。由于基因调控网络有助于分析基因间的调控作用，采用了C3NET算法推断基因表达数据集的基因调控网络。同时，将图信号处理应用到基因的特征选择问题中，将基因调控网络建模为图上邻接矩阵，基因表达数据建模为图信号，利用高通图滤波器对基因数据进行滤波，使得滤波后的基因融合了更多调控信息，提高了基因的分类能力，并提出了一种计算基因分类能力的方法。仿真实验结果表明，与对比算法相比，本算法筛选出的基因在不同分类器中分类准确率更高，区分能力更强。然而，本算法在KNN分类器中的分类准确率有待提高，接下来将考虑设计更合理的基因调控网络以提高算法的性能。