基于图论的DNA微阵列数据聚类算法.pdf

《基于图论的DNA微阵列数据聚类算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第40卷第5期计算机工程2014年5月V_01．40NO．5ComputerEngineeringMay2014·先进计算与数据处理·文章编号：1000—3428(2014)05—0036—05文献标识码：A中图分类号：TP309基于图论的DNA微阵列数据聚类算法宋佳，许力，孙洪(1．浙江大学电气工程学院，杭州310027；2．苏州市职业大学电子信息工程系，江苏苏州215104)摘要：传统的聚类算法用于DNA微阵列数据分析时，多数只能生成一种聚类结果，无法识别出与多组不同基因表达模式相类似的基因。针对该问题，提出一种基于图论的聚类算法，采用一个有向无权图来描

2、述需要分析的DNA微阵列数据，分别计算该图具有最小割权值和第Zd,割权值的图割。测试结果表明，该算法可以有效地探测聚类结果空间并输出一组可能性较高的聚类结果，与Fuzzy—Max、Fuzzy—Alpha、Fuzzy—Clust等聚类算法相比具有更高的准确性。关键词：微阵列；基因表达数据；聚类分析；图割；图论；最小割DataClusteringAlgorithmforDNAMicroarrayBased0nGraphTheorySoNGJia．XULi．SUNHong‘(1．ElectricalEngineeringCollege，Zh~iangUnivers

3、ity,Hangzhou310027，China；2．DepartmentofElectronicandInformationEngineering，SuzhouVocationalUniversity,Suzhou215104，China)[Abstract]ClusteringisanefectiveandpracticalmethodtominethehugeamountofDNAmicroarraydatatogainimportantgeneticandbiologicalinformation．However，mosttraditionalclu

4、steringalgorithmscanonlyprovideasingleclusteringresult，andareunabletoidentifydistinctsetsofgeneswithsimilarexpressionpatterns．ThispaperpresentsanalgorithmthatcanclusterDNAmicroarraydatawithagraphtheorybasedalgorithm．Inparticular,aDNAmicroarraydatasetisrepresentedbyagraphwhoseedgesa

5、reweighted，thenanalgorithmwhichcancomputetheminimumweightedandsecondminimum~veightedgraphcutsisappliedtothegraphrespectively．Testresultsshowthatthisapproachcanachieveimprovedclusteringaccuracy,comparedwithotherclusteringmethodssuchasFuzzy—Max，Fuzzy—Alpha，Fuzzy—Clust．[Keywords]micro

6、array；geneexpressiondata；clusteringanalysis；graphcut；graphtheory；minimumcutDOh10．3969d．issn．1000—3428．2014．05．008效果直接影响后续的表达谱数据分析性能。1概述聚类算法可以分为有监督的聚类算法(或分类，classifi·DNA微阵列技术的发展使得研究人员可以同时监测并cation)、无监督的聚类算法和混合聚类算法。在有监督的聚获得各种环境下成千上万个基因的表达水平，产生了海量类中，聚类基于一个给定的参考方向集或类别集；在无监的基因表达谱数据⋯，从而深

7、入地认识诸多生物过程的本督聚类中，聚类分析预先不知道类别信息，没有训练集；质，如基因功能、发育、癌症、衰老和药理等。因此，建混合聚类通常先进行无监督聚类，确定一些类，再用神经立能够准确处理和分析DNA微阵列数据集的方法是目前网络或支持向量机这些可以学习数据类别之间决策边界的生物信息学发展的一个重要方向。聚类算法就是用于查找分类器，将新基因归到不同的类内。基因表达阵列实验尚功能相关的基因和疾病新子群的主要方法之一。聚类算法处于早期阶段，无监督聚类算法仍是最常用的。根据目标研究对象的属性数值，采用数学方法对其进行分目前，已有大量的无监督聚类算法和软件被开发出来类

8、和整理，将具有相似属性的事物聚为一类，使得同一类并用