最小支撑树算法在基因表达数据聚类分析中的应用

聚类分析已成为对基因表达数据进行挖掘以提取生物医学信息的主要方法.本文提出了基于图论的最小支撑树(Minimum spanning tree,MST)聚类算法,用MST表示多维基因表达数据,可将数据的聚类转换为对最小支撑树的分割,相对于传统聚类方法,最小支撑树算法具有形象直观、对一些准则函数能产生全局最优解等优点;将MST算法分别与Memetic algorithm及人工免疫算法(Artificial immune network,aiNet)相结合,则产生更优化的聚类结果.对酵母基因表达数据的实验结果表明,最小支撑树聚类算法是一种有效的基因表达数据的聚类方法.

Clustering Gene Expression Data Using Minimum Spanning Trees

Clustering techniques are utilized to extract useful information from the tremendous amount of data produced by microarray.The application of minimum spanning tree(MST) algorithm is presented and a graph theory-based approach is used in data clustering.By representing the multi-dimensional gene expression data as nodes of a tree,MST algorithm can transform the data clustering to the partition of the minimum spanning tree.Each cluster of the gene expression data corresponds to one sub-tree of the MST.With the advantages of a simple structure of a tree and not depending on the geometric shape of a cluster,the MST-based clustering algorithm can overcome many problems faced by classical clustering algorithms and guarantee global optimization for some objective function.Combined with memetic algorithm(MA) or artificial immune network(aiNet),the MST algorithm can produce more optimal clusters.Experimental results on yeast Saccharomyces cerevisiae gene expression data show that the MST clustering algorithm is effective in clustering gene expression data.