Clustering algorithm based on DINNSM and its application in gene expression data analysis

2.1Datasets

We performed experimental validation on five gene expression datasets, as detailed in Table 1. The Yeast1 dataset, created by Cho et al. [15], which used cDNA microarrays to track gene expression changes during the cell cycle of the yeast genome. The dataset contains an expression value of 416 genes at 17 time points. Yeung et al. [16] selected 384 genes that exhibited peak expression at the four single time points. The dataset can be accessed at http://faulty.washington.edu/kayee/cluster. The Yeast2 dataset originated from the Department of Molecular Biology at Stanford University. It contains 552 genes and has been included in the R language’s internal datasets (in the Kohonen package) [17]. The Escherichia coli dataset originated from a comprehensive assessment of the gene expression data module detection method performed by Saelens et al. [8]. We selected four functional gene categories: cell motility (114 genes), coenzyme transport and metabolism (122 genes), inorganic ion transport and metabolism (305 genes), and secondary metabolite biosynthesis, transport, and catabolism (36 genes). After removing outliers and normalizing the data, the final E. coli dataset consisted of 573 genes and 814 samples. The three datasets were selected for our experiments because they offered accurate gene classifications.

The hypertension (HT) (GSE75360) dataset and gastric cancer (GC) (GSE54129) dataset from the Gene Expression Omnibus (GEO) database (http://www.ncbi.nlm. nih.gov/geo/) were used to validate our algorithm. The HT dataset included 21 samples, and the GC dataset had 132 samples. Probe transformation, missing-value removal, duplicate-gene elimination, and normalization were performed on both datasets using R (version 4.2.1). Differential analysis was conducted using the limma package, with significant differentially expressed genes identified based on the P value and logFC criteria. The final HT dataset contained 788 genes, whereas the GC dataset included 652 genes.

2.2Dual-Index Nearest Neighbor Similarity Measure (DINNSM)

The DINNSM algorithm was used to construct a similarity matrix by combining PC and SPC similarity measurement methods with the nearest neighbor concept. The principle of the algorithm was as follows.

Suppose dataset A is a gene expression dataset with n genes and m experimental conditions. The initial step of the algorithm involved calculating the similarity between Gi and gene Gj using Eq. (1). This generated a symmetric similarity matrix Disim with dimensions n×n.

Where di is the difference in rank values of the i-th pair of genes.

The Disim had higher accuracy compared with that of similarity matrices constructed solely based on PC or PSC. The high-dimensional nature of the data space resulted in the nontransitive similarity measure. To address this issue, we used the concept of nearest neighbors to improve the accuracy of the similarity measure.

The knearest neighbor table refers to a table of k genes most similar to a given gene. That is, k genes that are most similar to di,1 were selected in each row of the matrix Disim. Each gene had its own nearest neighbor table. The similarity between genes was measured by the number of shared genes in their nearest neighbor tables and the positions of these shared genes. More shared genes and closer positions in the nearest neighbor tables indicated greater similarity. The similarity matrix was generated using Eq. (2)

where T⁢(G⁢i) is the nearest neighbor table of gene Gi. Gn is the number of shared genes between gene Gi and gene Gj. PGn,T⁢(Gi) is the position of shared genes in table T⁢(G⁢i).

Finally, clustering was performed using the similarity matrix generated using Eq. (2).

This method addressed the limitations of PC in calculating the similarity between genes with nonlinear relationships and overcame the nontransitivity of similarity in high-dimensional data spaces. We constructed Constrsim() and Constrodsnn() functions and performed parallel operations using the foreach package due to the high computational complexity of the DINNSM [18]. The foreach package allowed for parallel computation across multiple Central Processing Unit cores, leading to a significant reduction in the runtime of the algorithm.

2.3Clustering algorithms

WGCNA is a popular algorithm used for detecting gene modules [19]. It describes gene relationships using a network model, and the gene network follows a scale-free distribution. The similarity matrix is typically constructed using PC, which is then converted into an adjacency matrix. The adjacency matrix is further transformed into a topological matrix using the TOMsimilarity() function. Finally, gene modules are identified using the dynamic tree-cutting method.

The K-means clustering is a widely used iterative algorithm [20]. The process includes randomly selecting k samples (genes) as initial clustering centers, calculating the distance between each sample and each clustering center, assigning each sample to the nearest center, and recalculating the cluster centers based on the current samples. The process continues until a termination condition is met.

FCM clustering is a popular fuzzy clustering algorithm based on objective functions [12]. It is used to calculate a membership matrix for the samples (genes) and assign samples with the highest degree of similarity to the same cluster. This allows the same data to belong to multiple classes.

Hierarchical clustering is an effective method for exploring the nested relationships [12, 20]. It generates a nested hierarchical clustering tree by calculating the similarity between data points in different categories. The most common approach to clustering is agglomerative hierarchical clustering, which includes three linking methods: single linkage, complete linkage, and average linkage. We used the average linkage method

2.4Evaluation measures

This study used SI, CHI, and DBI as internal evaluation measures [21, 22, 23]. Among these, the SI ranges from -1 to 1, with higher values indicating better clustering. The CHI has no range limit, with higher values indicating improved clustering. The DBI has no range limit, with lower values indicating better clustering performance. SI is a particularly effective metric for evaluating the performance of clustering algorithms. We used it as the main internal criterion for judgment. We used AMI, ARI, and ABHI as external evaluation metrics. Among these, the ranges of AMI and ARI are from 0 to 1 and from -1 to 1, respectively. They are both higher values indicating better clustering performance. We used AMI as the primary external judgment criterion. ABHI is an improvement we made over the BHI.

BHI assesses the biological significance of clustering by considering gene functional classes. If two genes in the same clustering category also belong to the same functional class, they are given a higher weight. We found that the evaluation value of BHI was too high when certain clusters in the clustering results had less than five genes. We proposed the ABHI to address this issue.

Given a set of gene functional classes B={B1,B2,…,BF} and a statistical clustering partition C={C1,C2,…,CF}, the ABHI is defined as:

where K is the number of clusters. nk=n⁢(Ck∩B) is the number of functionally annotated genes in cluster Ck. I(B(i)=B(j)) is an indicator variable, assigned 1 if B⁢(i) and B⁢(j) match, and 0 otherwise. n⁢(C) is the total count in each cluster. ABHI values range from 0 to 1, with higher values indicating greater biological significance.

2.5Biological significance

Functional enrichment analysis is a commonly used method in bioinformatics research. It can be conducted on genes within the same cluster using Gene Ontology (GO) terms. We can interpret the biological significance of the clustering results by comparing the gene sets obtained from clustering analysis to known gene functions. Studies have shown that the three most important GO terms can effectively reflect the biological relevance of clustering [12]. We conducted GO enrichment analysis on the gene sets obtained from clustering analysis using the clusterProfiler package. The P value (P< 0.05) was used to determine statistical significance.

3.1Cluster quality analysis

Table 2 shows the internal evaluation results for different WGCNA methods across all datasets. WGCNA using DINNSM as a similarity measure obtained the best evaluation results in all datasets. The results of the external evaluation are shown in Table 3. The DINNSM as a similarity measure also obtained the best evaluation results in all datasets, except for the ARI in the E. coli dataset.

Figure 1.

(a) Comparison of SI metrics obtained by K-means clustering based on different similarity measurement methods on all gene expression datasets. (b) Comparison of AMI metrics obtained by K-means clustering based on different similarity measurement methods on three gene expression datasets.

The DINNSM algorithm was also applied to K-means, FCM, and hierarchical clustering methods to verify the applicability of the algorithm. The internal and external evaluation results of K-means clustering based on six different similarity measurement methods (PC, SPC, ED, MIC, DC, and DINNSM) are shown in Fig. 1a and b. DINNSM outperformed other similarity measures regarding SI and AMI values across all datasets.

Figure 2.

(a) Comparison of SI metrics obtained by FCM clustering based on different similarity measurement methods on all gene expression datasets. (b) Comparison of AMI metrics obtained by FCM clustering based on different similarity measurement methods on three gene expression datasets.

The internal and external evaluation results of FCM clustering based on the six different similarity measurement methods are shown in Fig. 2a and b. The DINNSM method achieved the highest SI values in all datasets, except the HT dataset. Meanwhile, DINNSM obtained the most significant AMI values in all datasets, except the E. coli dataset.

The internal and external evaluation results of hierarchical clustering based on the six different similarity measurement methods are shown in Fig. 3a and b. DINNSM achieved the highest SI values in all datasets except the HT dataset and had the highest AMI values in all datasets.

Figure 3.

(a) Comparison of SI metrics obtained by hierarchical clustering based on different similarity measurement methods on all gene expression datasets. (b) Comparison of AMI metrics obtained by hierarchical clustering based on different similarity measurement methods on three gene expression datasets.

Figure 4.

(a) Comparison of the runtime with and without parallel computing for the MIC measurement method. (b) Comparison of the runtime with and without parallel computing for the DC measurement method. (c) Comparison of the runtime with and without parallel computing for the DINNSM measurement method. (d) Comparison of the runtime with different numbers of threads for three similarity measurement methods on the E. coli dataset.

3.2Speed analysis

We performed parallel computation using the foreach package. As the MIC and DC methods have high time complexity, we also implemented parallel computation. We conducted 10 runs of each method without parallel processing and with parallel computation using 10 threads to compare the time difference (in seconds) between running the MIC, DC, and DINNSM measurement methods with and without parallel computation. We observed the average times on the Yeast1, Yeast2, HT, and GC datasets. As shown in Fig. 4a–c, parallel computation led to a significant decrease in the runtime. We compared the runtime of the MIC, DC, and DINNSM methods using 10, 20, and 30 threads on the E. coli dataset, as shown in Fig. 4d, to investigate the effect of varying thread numbers on the runtime. The results showed that using an appropriate number of parallel threads could significantly reduce the program execution time.

3.3Biological significance

We conducted module detection on the Yeast1 dataset to demonstrate the biological significance of the clusters generated by our proposed method. We performed GO analysis on the clustering modules. Table 4 presents the top three molecular function terms and their corresponding P values. The analysis indicated that different clustering categories had distinct biological functions, with all P values less than 0.05.