基于点的代数连通强度和非负矩阵分解的肿瘤基因分类

王 年，宋 豪，汪沁紫

（安徽大学 计算机智能与信号处理教育部重点实验室，安徽 合肥 230039）

随着基因表达谱技术的进步，对肿瘤基因的识别与分类的研究已经成为生物信息学的研究热点.如果能够对肿瘤基因做出正确的识别和判断，挖掘出有用的信息和知识，对推动肿瘤学的基础研究和肿瘤的临床诊断和治疗，进而研究肿瘤的致病机制都有至关重要的作用.

近些年来，为了解决基因表达谱数据样本少、维数高和冗余基因多等问题，研究者们提出了诸多方法.自从1999年Golub等［1］提出一种以“信噪比”为指标对白血病的两个亚型样本进行分类研究以来，随着后人对基因分类技术的不断发展与改善，基因的特征可以在更大程度上被挖掘出来.相关研究有2009年Ghoula等［2］提出的多层神经网络算法，该算法可以解决聚类数目估计问题；Mishra等［3］于2011年对信噪比方法进行改进，使得该方法的分类效果进一步提高；2012年，秦传东等［4］提出一种肿瘤基因的支持向量机的分类方法.在基因子集的选取方面，多种传统方法得到运用，如T检验［5］，相对熵［6］和基因调控概率［7］.这些方法都是基于基因的重要性进行记分，以此选取重要的特征基因子集.然而经已有相关研究表明，被保留的基因子集间仍然有大量信息冗余存在，进而学者们对此进一步进行特征提取，其常用方法有主成分分析［8］、独立成分分析［9］和非负矩阵分解［10］等，其中非负矩阵分解作为近来一种新的矩阵分解方法，由Lee和Seung［11］于1999年在《Nature》上提出.该方法在对矩阵进行分解时，对矩阵以及分解后的子矩阵都施以严格的非负性约束，这样能够通过少量的基向量的正加性组合来表征原矩阵的数据，且非负性约束的引入，可以保证原数据特征不会被削弱，实现原数据的纯加性描述，使数据的结构变得更加清晰，基于上述优点，非负矩阵分解在数据处理中得到了越来越广泛的运用.

然而这些早期常用的方法是运用某种记分准则对一系列基因进行重要性打分，以便度量每个基因含有肿瘤信息的多少，从而选取少量的特征基因子集达到降维和去噪的目的，然而记分准则方法易受异常值、污染值影响，使之不能客观反映选取的基因的重要性，因此作者在该文中采用点的代数连通强度与非负矩阵分解来对肿瘤基因进行识别和分类.首先通过点的代数连通强度得到基因的客观表达，再通过修订的特征计分准则进行筛选，得到相应的基因子集，最后利用非负矩阵分解进一步提取基因表达特征，从而对肿瘤基因进行分类.经真实数据实验及其他方法的对比，验证文中方法的有效性.

1 点的代数连通强度

图中点的代数连通强度定义［12］：设完全图F中有N个顶点V（F）＝｛v1，v2，…，vN｝，相应边被赋予权值wi，j表示边的两个端i，j∈｛1，2，…，N｝点下标，对其任意结点vi，计算与其相邻K个邻接结点的边权值之和，记，则Sum（vi）记为vi点的代数连通强度（the algebraic connectivity strength of point，简称ACSP）.图中点的代数连通强度可以很好地反映图中某点与其他点的关联程度，所得到的信息可以反映图的基本特征信息，有助于找到更加有效的、客观的点信息.

对于每一个基因gi，则视该基因在同一类所有样本中的表达值为点信息，构建一个完全图，其边缘权值定义如下

其中：Num表示同类中的样本个数，因此记每个gi对应一个点集为：valuei＝｛value1i，value2i，…，valueNumi｝，当邻近点的数目K≈T×Num，这里T是一个参数且T∈［0，1］.计算

首先，确定最大值Sum（valueji）

然后将与Summax对应的valueji看做中心点.基因gi在同种类别中表达水平的均值和方差可以通过分析T×Num个相邻的valueji来获得（包括valueji）.同样原理，基因在不同类别中表达水平的均值和方差也可以用相同方法得到.最后，利用修订的特征记分准则对基因gi进行计分.

2 非负矩阵分解

由于高维数据的数据量非常庞大，对矩阵进行直接操作效率很低，甚至不可行，因此需要对矩阵进行分解，降低矩阵的维数，压缩数据，从而找到矩阵的关键信息，而非负矩阵分解（Non－negative Matrix Factorization，简称NMF）就是其中一种有效的分解方法，即对于给定的n×m的非负矩阵V，通过寻找两个低秩的非负矩阵

使得

非负矩阵的算法是对W和H进行不断地迭代更新，使得目标函数最小.其目标函数是由Lee等提出的一种基于V与W、H两者乘积之间的欧氏距离的目标函数，定义如下

相应的迭代规则为

3 分类方法与实验验证

3.1 分类方法

作者对急性白血病和结肠癌两类公开的基因表达谱数据集进行了实验，其中白血病数据集含有52个样本（24个为急性淋巴性白血病——ALL，28个为急性粒性白血病——AML），每个样本有12 564个基因；结肠癌数据集中含有62个样本，其中22个为正常样本，40个为结肠癌样本，每个样本中包含2 000个基因.通过上述分析，其分类方法和步骤如下：

（1）导入基因表达谱数据，记为G＝（gij）N×M，gij为第j个基因在第i个样本中的表达水平，N、M分别为样本数与基因数；

（2）对于每个基因，在T＝0.8时，利用点的代数连通强度选取基因在各类所有样本中的更客观的、真实的表达值，消去各种外界因素导致的出格点，即突变值；

（3）对M个基因都进行（2）处理，运用修正的特征记分准则（revised feature score criterion，简称RFSC）［13］对所有基因进行重要性记分并按降序排列，得到特征基因子集G′＝（g′sk）N×L，L＜M；

（4）通过G＇的选取，基于NMF理论，对该子集进行非负矩阵分解得到样本的低维表达，获得子矩阵Wn×r和Hr×L，则W的每行代表了原样本在H＝｛h1，h2，…，hr｝低维空间中的特征表示；

（5）最后以W的行作为样本的特征数据输入SVM分类器，对3组公开的基因表达谱数据进行分类验证并给出分析.

3.2 实验验证与结果分析

作者首先对白血病数据集进行了实验，通过点的代数连通强度算法，保留了ALL类和AML类中客观的基因表达值，同时剔除了一些异常值（即出格点），再获取基因特征子集，通过NMF方法的变换，将白血病样本映射到一个低维特征空间，其实验结果如图1所示.

当基因子集规模分别在Gene－Subset＝50，90，…，290时，通过NMF方法将其映射到维数为r＝2，3，…，9的低维空间中，图1显示了不同基因子集规模下及不同低维空间的分类正确率，可以发现，分类正确率都在95%以上，其中在Gene－Subset＝290时，随着r的递增，分类识别率达到100%且很稳定，当Gene－Subset缩减到50时，也能达到客观的效果；另一方面，在寻找较优的及较稳定的低维度时，r＝6相对于其他情况能提供更好和稳定的正确率.

按同样思路给出结肠癌数据的实验结果，图2显示：分别在不同的Gene－Subset境况下，结合NMF方法，实现了正常样本与癌症样本的识别.

结肠癌数据分类在图2的8个子图中均在90%附近，通过异常点的消除、信息量小的基因的舍弃，以及NMF对信息基因间的冗余信息的压缩，使不同类别得到有效识别.图2中，在Gene－Subset＝90的子图中，对于公认的正负样本规模不平衡、难以很好识别的结肠癌数据集，其最高识别率达到91.94%，说明了文中方法是有效的、可行的.

将Sigh等［14］以“信噪比”作提取特征基因指标以及阮晓刚等［15］提出的CLUSTER－S2N方法提取特征基因等方法与该文方法进行比较，结果如表1所示.

表1 实验结果比较Tab.1 Comparison of experiment results

在相同分类器SVM的情况下，对比识别效果，可以发现该文方法在识别精度上具有一定优势，表明利用文中方法处理白血病和结肠癌数据时，由于对实验数据预处理时，使用将受外界影响较大的点的代数连通强度的数据剔除，使得基因表达值更加客观，在获取特征基因子集后，进一步利用NMF将数据样本映射到低维的特征空间，使得数据可分性加强，因此白血病样本分类正确率达到100%；而对于公认比较难分类的结肠癌样本，利用该文方法进行试验的正确率也非常可观.

4 结束语

利用DNA微阵列数据对肿瘤基因数据进行分类识别是当前生物信息学研究的主要方向之一.作者提出了基于点的代数连通强度和非负矩阵分解相结合的方法，经过实验验证了该方法对肿瘤类型识别的可行性与有效性.由于文中的方法利用了非负矩阵分解，而NMF的复杂度与初始矩阵W的选取有很大关系，因此在选取合适的初始矩阵方面，该方法有待改善.

［1］Golub T R，Slonim D K，Tamayo P，et al.Molecular classification of cancer：class discovery and class prediction by gene expression monitoring［J］.Science，1999，286（5439）：531－537.

［2］Ghouila A，Yahia S B，Malouche D，et al.Application of multi－SOM clustering approach to macrophage gene expression analysis［J］.Infection，Genetics and Evolution，2009，9（3）：328－336.

［3］Mishra D，Sahu B.Feature selection for cancer classification：a signal－to－noise ratio approach［J］.International Journal of Scientific ＆ Engineering Research，2011，2（4）：1－7.

［4］秦传东，刘三阳，张市芳.一种肿瘤基因的支持向量机提取方法［J］.西安电子科技大学学报：自然科学版，2012，39（1）：191－196.

［5］Jafari P，Azuaje F.An assessment of recently published gene expression data analyses：reporting experimental design and statistical factors［J］.BMC Med Inform Decis Mak，2006，6（1）：27.

［6］Chang G，Wang T.Weighted relative entropy for alignment－free sequence comparison based on Markov model［J］.Journal of Biomolecular Structure and Dynamics，2011，28（4）：545－555.

［7］Wang H Q，Huang D S.A gene selection algorithm based on the gene regulation probability using maximal likelihood estimation［J］.Biotechnol Lett，2005，27（8）：597－603.

［8］陈乐，王年，苏亮亮，等.基于邻接谱主分量分析的肿瘤分类方法［J］.安徽大学学报：自然科学版，2011，35（4）：86－91.

［9］Esposito F，Goebel R.Extracting functional networks with spatial independent component analysis：the role of dimensionality，reliability and aggregation scheme［J］.Current Opinion in Neurology，2011，24（4）：378－385.

［10］叶爱霞，王年，苏亮亮.基于非负矩阵分解和Normal－Matrix的肿瘤基因分类［J］.安徽大学学报：自然科学版，2012，36（3）：90－94.

［11］Lee D D，Seung H S.Learning the parts of objects by non－negative matrix factorization［J］.Nature，1999，401（6755）：788－791.

［12］Wang N，Su L L，Tang J，et al.Informative gene selection using the algebraic connectivity strength of point and scoring criteria［J］.Chinese Science Bulletin，2013，58（6）：657－661.

［13］李颖新，阮晓钢.基于支持向量机的肿瘤分类特征基因选取［J］.计算机研究与发展，2006，42（10）：1796－1801.

［14］Singh D，Febbo P G，Ross K，et al.Gene expression correlates of clinical prostate cancer behavior［J］.Cancer Cell，2002，1（2）：203－209.

［15］阮晓钢，晁浩.肿瘤识别过程中特征基因的选取［J］.控制工程，2007，14（4）：373－375.