Graph Algorithm Assigns Exclusive Functional Signatures to Human Genes

Researchers Gleb Buzanov and Vsevolod Makeev have introduced VOL-Gene, a computational framework designed to resolve one of the most persistent bottlenecks in modern genomics: interpreting small or poorly characterized sets of marker genes. In contemporary biological investigations, experimental screens and association studies frequently highlight only a handful of candidate genes, yielding lists that are far too small to be evaluated through standard gene set enrichment analysis. Traditional statistical enrichment tools rely on expansive gene collections, leaving researchers with limited avenues when attempting to interpret isolated markers. To address this computational limitation, the investigators developed a graph-based algorithm that partitions the human genome into mutually exclusive, non-overlapping functional categories. By grouping all genes into discrete classes, VOL-Gene systematically assigns a single, primary biological role to each gene, enabling scientists to rapidly infer the functions of uncharacterized loci by examining their tightly connected neighborhood peers.

The conceptual foundation of VOL-Gene rests upon the modular organization of cellular systems, where coordinated expression among ensembled genes underpins critical developmental events, disease progression, and physiological adaptations to external stimuli. In computational biology, these functional associations are cataloged in specialized repositories such as MSigDB and GenSigDB, which store extensive libraries of co-expressed modules and biological signatures. Modern integrative platforms like Enrichr further aggregate curated gene signatures from multiple public databases, including the Gene Ontology, Reactome pathways, and Kyoto Encyclopedia of Genes and Genomes. However, existing collections present a substantial analytical challenge: individual signatures frequently contain hundreds of genes, while a single gene may be annotated across dozens of disparate functional categories. This multi-signature redundancy dilutes biological specificity, making it exceptionally difficult to determine which pathway should be prioritized when a genome-wide association study uncovers understudied genetic loci with ambiguous functional affiliations.

To establish a structured and exclusive functional taxonomy, the researchers constructed a unified graph representation using the comprehensive collection of signatures available in Enrichr. To eliminate nomenclature ambiguities and synonymous designations across disparate experimental datasets, all gene identifiers were systematically standardized against the official NCBI database, after which the compiled signatures were partitioned into training and validation sets at a two-to-one volume ratio. Within this mathematical formulation, each biological signature containing multiple genes is converted into a fully connected clique, wherein every constituent gene pair is joined by an edge. When all signature cliques are overlaid into a single global supergraph, the number of parallel connections between any two vertices reflects their shared co-membership frequency. The authors then transformed this supergraph into a weighted graph, calculating each pairwise link weight by dividing the joint signature count by the sum of both genes’ degrees, effectively downweighting ubiquitous hub genes.

At the core of the clustering pipeline is an adaptation of the OpenOrd graph layout algorithm, which reformulates network organization as a physical interaction simulation based on the classic Fruchterman-Reingold framework. The algorithm determines the optimal spatial distribution of vertices across a continuous two-dimensional plane by iteratively minimizing the overall potential energy of the physical system. In this energetic landscape, vertices experience attractive forces along connecting edges that increase proportionally with link weight and spatial separation, countered by repulsive forces that scale with the local two-dimensional node density according to an inverse square relationship. Importantly, the authors clarify that the resulting planar coordinates do not represent semantic or biological dimensions, nor is the two-dimensional plane equivalent to projection-based dimensionality reduction techniques like principal component analysis or uniform manifold approximation and projection. Instead, the spatial plane functions strictly as a computational scaffold that positions densely connected functional cliques into localized clusters.

The physical layout optimization is executed across a five-stage simulated annealing schedule encompassing fifteen hundred iterations, mirroring the temperature-controlled cooling phases established in the original OpenOrd architecture. The annealing protocol allocates computational time across five consecutive stages: a liquid phase consuming five percent of total time, an expansion phase spanning twenty-five percent, a cooldown phase occupying sixty percent, and final crunch and simmer phases requiring five percent each. During this progressive thermal reduction, the temperature parameter steadily contracts, systematically dampening the magnitude of vertex displacement and enabling nodes to freeze into quasi-optimal structural configurations. The investigators verified that higher dimensions offer no functional advantage; pilot tests conducted in three dimensions produced structural clusters that, when projected onto two dimensions, were virtually indistinguishable from planar results. Because high-dimensional force calculations incur prohibitive computational overhead, the two-dimensional framework provides an ideal balance of computational tractability and topological accuracy.

Once the simulated annealing process settles the network into an energy-minimized configuration, VOL-Gene applies the KMeans clustering algorithm to identify dense spatial groupings across the two-dimensional plane. Rather than interpreting raw Cartesian coordinates, the clustering step operates directly on the emergent spatial density patterns generated by the layout, exploiting the algorithm’s intrinsic capacity to co-locate tightly connected graph subgraphs. To establish the most biologically meaningful number of functional groups, the authors systematically optimized cluster partitioning by maximizing the silhouette score across multiple clustering iterations. This evaluation measures the relationship between the average distance among nodes within the same cluster and the minimal average distance to external clusters. The resulting clusters define an entirely mutually exclusive functional landscape, wherein every analyzed gene is assigned to exactly one discrete functional class, thereby converting diffuse, overlapping pathway memberships into unambiguous functional units.

Implementing graph clustering on full-scale genomic datasets presents severe computational hurdles, as the complete Enrichr database encompasses approximately twenty thousand genes, yielding an adjacency matrix containing nearly half a billion elements. To maintain algorithmic tractability, the researchers examined two complementary dimensionality reduction strategies: filtering edges below selected weight thresholds of zero, five hundredths, one tenth, and two tenths, alongside pruning genes that appeared infrequently within the original signature repository. While filtering rare genes introduces an inherent bias toward heavily researched disease pathways such as cancer, retaining the five thousand most frequent genes enabled stable calculations even at low thresholds. Crucially, when processing the complete unpruned network where the threshold equals zero, VOL-Gene operated at least ten times faster than existing clustering algorithms, successfully resolving dense network structures that caused alternative computational approaches to fail entirely due to memory exhaustion or excessive processing time.

To rigorously quantify the specific benefits of simulated annealing, the authors benchmarked VOL-Gene against five established clustering algorithms that operate directly on raw graph topologies without layout preprocessing: spectral clustering, k-medoids, agglomerative hierarchical clustering, affinity propagation, and HDBSCAN. When evaluated across the independent validation signature split using network assortativity and a synthetic Jaccard index, the VOL-Gene pipeline demonstrated distinct performance advantages. At moderate pruning thresholds, VOL-Gene consistently outperformed alternative methods in network assortativity, measuring the structural propensity of functionally related nodes to interconnect, while delivering validation accuracy on par with HDBSCAN under synthetic Jaccard metrics. Although agglomerative clustering exhibited higher assortativity under minimal pruning constraints, its performance deteriorated dramatically under stricter edge pruning and reduced gene counts. Furthermore, competing methods proved computationally incapable of processing datasets larger than five thousand genes, leaving VOL-Gene uniquely capable of evaluating full-scale genomic data.

When applied to the complete unpruned human gene set of eighteen thousand nine hundred ninety-five genes at a threshold of zero, VOL-Gene partitioned the entire genome into approximately eighty distinct functional clusters. Cross-validation against the independent GeneSigDB database revealed that these exclusive clusters encompassed up to eighty percent of curated reference signatures, demonstrating that the exclusive partitioning preserved genuine biological relationships. Cluster identities were confirmed by isolating well-known marker genes and annotating the remaining cluster members with Metascape to prevent circularity. For instance, a cluster centered on TP53 contained one hundred eleven genes enriched for cell cycle regulation and apoptosis, including canonical cancer drivers such as EGFR, VEGFA, and CDKN1A. Similarly, an IL6-associated cluster brought together three hundred nineteen inflammation-related genes, including seventy-nine cytokines, sixty-nine chemokine markers, and regulators like SRC, TNF, and STAT3, while an MYH2 cluster captured skeletal muscle contractile machinery.

The primary practical utility of VOL-Gene lies in annotating poorly characterized genes by leveraging their assigned network context, as demonstrated through systematic analyses of genetic loci prioritized in large-scale genome-wide association studies of schizophrenia. When mapped across VOL-Gene partitions, schizophrenia risk loci showed pronounced statistical enrichment in clusters governing chemical synaptic transmission, synaptic signaling modulation, neuron projection development, and postsynaptic membrane potential regulation. Notably, cluster seventy-seven, which is primarily linked to angiogenesis, contained understudied schizophrenia risk loci ANKRD44 and DGCR6 alongside established disease-associated genes HNF1B and FUT8. In an independent example, cluster eighty-four grouped poorly annotated genes MYEOV and PSORS1C2 into a cohesive module characterized by skin development, sphingolipid metabolism, cytokine signaling, and dermatological pathologies including ichthyoses, keratoderma, and squamous cell carcinoma, illustrating how network positioning generates precise, testable mechanistic hypotheses for previously unannotated genes.

To support multi-scale biological investigations, the authors implemented a hierarchical aggregation framework capable of contracting primary clusters into higher-order nodes and executing secondary OpenOrd annealing cycles. Across up to three hierarchical tiers, this multi-layered architecture constructs broader hyperfunctions, such as uniting specialized immune functions beneath an overarching inflammation module. However, the researchers cautioned that at high aggregation levels, hyperclusters occasionally group biologically unrelated genes due to small signatures within Enrichr that trigger artificial node merging. Although the greedy nature of the layout optimization produces minor variations of twenty to fifty genes between replicates, core cluster memberships remain remarkably stable, exhibiting less than one percent variation across trials. While VOL-Gene deliberately sacrifices multi-functional granularity in favor of computational speed and clear interpretation, it provides an efficient, complementary exploratory tool for genomic screening, systems biology pipelines, and machine learning applications.

Subject of Research: Graph-based partitioning of human gene signatures into mutually exclusive functional classes

Article Title: Exclusive functional signatures for gene annotation with vast OpenOrd layout

Article References: Buzanov, G., & Makeev, V. (2025). Exclusive functional signatures for gene annotation with vast OpenOrd layout. Algorithms for Molecular Biology, 20(1), Article 17. https://doi.org/10.1186/s13015-025-00290-w

Image Credits: AI Generated

DOI: 10.1186/s13015-025-00290-w

Keywords: computational biology, gene annotation, graph clustering, OpenOrd algorithm, simulated annealing, bioinformatics, gene signatures, systems biology, Exclusive, functional, signatures, gene