Identifying most relevant non-redundant gene markers from gene expression data using PSO-based graph -theoretic approach

A graph-theoretic approach for non-redundant gene marker selection from microarray gene expression data has been presented in this article. The sample versus gene data presented by microarray data is first converted into a weighted undirected complete feature-graph where the nodes represent the genes having gene´s relevance as node weights and the edges are weighted according to the similarity value (correlation) among the genes. Then the densest subgraph having minimum average edge weight (similarity) and maximum average node weight (snr value) is identified from the original feature-graph. To find the densest subgraph, binary particle swarm optimization has been applied for minimizing the average edge weight and maximizing the average node weigh through a single objective function. Thus an optimized reduced subgraph is found which contains final selected genes for which average correlation is very less and average gene relevance is very high. The proposed method is compared with SFS, T-test and Ranksum test in terms of sensitivity, specificity, accuracy, fscore, Area Under ROC Curve (AUC) and average correlation on several real-life data sets.