Identifying Potential Biomarkers for Diseases Diagnosis Through Co-Expression Analysis: An Optimization Approach

Abstract

While gene function is dysregulated in cancer, detecting these abnormalities will assist in diagnosis. DNA microarray technology is a significant tool for conducting research in functional genomics. This technology has been developed to assess gene expression levels across different samples. It has been used extensively in cancer research, where mutations may switch off or increase gene expression level in malignant cells. Identifying clusters of co-expressed genes has emerged as a pivotal stage in comprehending functional genomics, as it aligns with the notion that genes with related functions often exhibit similar expression patterns across varied samples. The biologist starts by analyzing the known functions of genes within each cluster in order to infer the function of the entire cluster, this inferred function is then ascribed to all unknown genes within the respective cluster. High-dimensional clustering has proven to be a fruitful pursuit for identifying co-expressed genes. This optimization problem, which is non-convex in nature, has been demonstrated to be NP-hard. DNA microarray provides large amount of gene expression datasets, resulting in millions of measurements. Practically, when there is a greater quantity of datasets to cluster and a larger number of clusters to consider, the potential number of partitions increases significantly. Consequently, this presents a computationally intensive and time-consuming combinatorial challenge, exacerbated by the high-dimensional nature of the gene expression datasets. Despite the availability of numerous high-dimensional clustering algorithms, there remains room for improving quality and reducing running-time. Indeed, the selection of a clustering algorithm is contingent upon the specific attributes of the dataset. To that end, we have proposed an algorithm specifically tailored to deal with big and high-dimensional datasets that optimizes the computational complexity. By applying this algorithm several times, a set of clusters including genes that are grouped together across multiple runs, will emerge. The centroid of each emerged cluster will be used to identify the optimal partition. Empirical studies unequivocally demonstrate an average 48% improvement in quality and an average 60% reduction in running-time compared to the approaches outlined in the related-work section.