Analysis of gene expression profiles: an application of memetic algorithms to the minimum sum-of-squares clustering problem

Microarrays have become a key technology in experimental molecular biology since they allow monitoring of gene expression for more than 10,000 genes in parallel producing huge amounts of data. In the exploration of transcriptional regulatory networks, an important task is to cluster gene expression data to identify groups of genes with similar patterns and hence similar function. In this paper, memetic algorithms (MAs)—evolutionary algorithms incorporating local search—are proposed for minimum sum-of-squares clustering (MSSC). In a fitness landscape analysis, it is shown that the MSSC problem has correlation structure exploitable by MAs. The proposed MAs are shown to be superior to multi-start k-means as well as five other clustering algorithms from the bioinformatics literature including hierarchical algorithms and self-organizing maps. Although the fitness values of the different clustering solutions lie close together, it is shown that the solutions differ significantly from each other in terms of cluster memberships which is extremely important for the biological interpretation of the clustering results