Gene co-expression analysis is an important research problem in molecular biology that helps to identify co-occurring genes in potential biological function. Clustering methods have been widely employed for this problem and hierarchical clustering based gene expression analysis has made tremendous progress in the past years. However, these methods heavily rely on proximity measures used in the clustering process. One of the major issues of hierarchical clustering is their inability to detect arbitrary shaped clusters in high dimensional spaces. Another issue is their pre-requisite of distance matrix calculation, which is not computationally efficient for large datasets. To address these issues, this paper proposes approximate similarity measures based on local neighborhood representation using minimum spanning tree. The effectiveness of proposed similarity measures is tested using hierarchical clustering algorithm. Experimental results on microarray gene expression datasets reveal that the proposed similarity measures achieve improved results in terms of clustering accuracy as well as reduced time complexity as compared to conventional distance measures. © 2021 Elsevier Ltd