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

Data Clustering Algorithm for DNA Microarray Based on Graph Theory

作　　者：宋佳[1,2] 许力[1] 孙洪[2] 

机构地区：[1]浙江大学电气工程学院,杭州310027 [2]苏州市职业大学电子信息工程系,江苏苏州215104

出　　处：《计算机工程》2014年第5期36-40,共5页Computer Engineering

基　　金：江苏省自然科学基金资助项目(BK2011319);苏州市职业大学青年基金资助项目(SZDQ09L02)

摘　　要：传统的聚类算法用于DNA微阵列数据分析时,多数只能生成一种聚类结果,无法识别出与多组不同基因表达模式相类似的基因。针对该问题,提出一种基于图论的聚类算法,采用一个有向无权图来描述需要分析的DNA微阵列数据,分别计算该图具有最小割权值和第二小割权值的图割。测试结果表明,该算法可以有效地探测聚类结果空间并输出一组可能性较高的聚类结果,与Fuzzy-Max、Fuzzy-Alpha、Fuzzy-Clust等聚类算法相比具有更高的准确性。Clustering is an effective and practical method to mine the huge amount of DNA microarray data to gain important genetic and biological information. However, most traditional clustering algorithms can only provide a single clustering result, and are unable to identify distinct sets of genes with similar expression patterns. This paper presents an algorithm that can cluster DNA microarray data with a graph theory based algorithm. In particular, a DNA microarray dataset is represented by a graph whose edges are weighted, then an algorithm which can compute the minimum weighted and second minimum weighted graph cuts is applied to the graph respectively. Test results show that this approach can achieve improved clustering accuracy, compared with other clustering methods such as Fuzzy-Max, Fuzzy-Alpha, Fuzzy-Clust.

关 键 词：微阵列 基因表达数据 聚类分析 图割 图论 最小割 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]