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

Data Clustering Algorithm for DNA Microarray Based on Graph Theory

传统的聚类算法用于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.