Paper deep dive
GenEx: A Graph-Based Representational Paradigm for SARS-CoV-2 Variant Detection via Codon Co-occurrence Networks
Arefin Amin, Labiba Faiza Karim, M. Monir Uddin
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 8/20/2026, 4:08:44 AM
Summary
The paper introduces GenEx, a graph-based pipeline for SARS-CoV-2 variant detection that converts gene sequences into codon co-occurrence graphs using two algorithms: LAPCG (Linear-time Adjacency PMI Codon Graph) and MSCG (Multi-Scale Codon Co-occurrence Graph). It extracts over 25 topological and spectral features, utilizing Singular Value Decomposition (SVD) on squared singular values to enhance class separability. The method was benchmarked against 23 ML models, achieving 98.75% accuracy with MSCG, outperforming traditional alignment-based methods and other classification tools.
Entities (13)
Relation Signals (8)
LAPCG → achievesaccuracy → 96.25%
confidence 95% · LAPCG ... 96.25% accuracy
MSCG → achievesaccuracy → 98.75%
confidence 95% · MSCG also achieves the highest classification accuracy at 98.75%
GenEx → classifies → SARS-CoV-2
confidence 95% · GenEx: A Graph-Based Representational Paradigm for SARS-CoV-2 Variant Detection
Omicron → isvariantof → SARS-CoV-2
confidence 95% · SARS-CoV-2 variants: Beta, Gamma, Delta, and Omicron
Beta → isvariantof → SARS-CoV-2
confidence 95% · SARS-CoV-2 variants: Beta, Gamma, Delta, and Omicron
GenEx → uses → LAPCG
confidence 95% · Our two most prominent techniques for graph generation and feature extraction are MSCG ... and LAPCG
GenEx → uses → MSCG
confidence 95% · Our two most prominent techniques for graph generation and feature extraction are MSCG ... and LAPCG
Singular Value Decomposition → usedin → GenEx
confidence 90% · implementing a spectral graph feature extraction using Singular Value Decomposition (SVD)
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Genomic analysis on viruses such as SARS-CoV-2 variants: Beta, Gamma, Delta, and Omicron is heavily dominated by classical bioinformatics methods, including Sequence Alignment, Phylogenetic Analysis, and Mutation Frequency Statistics. These approaches use pairwise codon or nucleotide distance matrices to analyze gene sequences, treating them as linear strings rather than capturing their complex contextual interdependencies. We proposed GenEx, a pipeline that converts raw gene sequences into codon co-occurrence graphs and extracts more than 25 graph features. Our two most prominent techniques for graph generation and feature extraction are MSCG (Multi-Scale Codon Co-occurrence Graph) and LAPCG (Linear-time Adjacency PMI Codon Graph). Using these algorithms, we treated codon sequences as structured symbolic vocabularies interpretable to codon co-occurrence graph analysis, a representational paradigm borrowed from computational linguistics. Another major contribution includes implementing a spectral graph feature extraction using Singular Value Decomposition (SVD), using the squared singular value ($\sigma^2$) instead of the traditionally used eigenvalue, which helped us to amplify the separation between dominant and subdominant spectral components, thereby enhancing inter-class separability in downstream classification. And to further demonstrate that our method works, we trained 23 benchmarked ML models against the latest SARS-CoV-2 variants, achieving remarkable results in detecting all SARS-CoV-2 variants.
Tags
Links
- Source: https://arxiv.org/abs/2608.18238v1
- Canonical: https://arxiv.org/abs/2608.18238v1
Trouble viewing inline? Open PDF directly →
Full Text
46,022 characters extracted from source content.
Expand or collapse full text
GenEx: A Graph-Based Representational Paradigm for SARS-CoV-2 Variant Detection via Codon Co-occurrence Networks Arefin Amin ECE Department North South University Dhaka, Bangladesh arefin.amin@northsouth.edu Labiba Faiza Karim ECE Department North South University Dhaka, Bangladesh labiba.karim@northsouth.edu M. Monir Uddin Department of Math. & Phy. North South University Dhaka, Bangladesh monir.uddin@northsouth.edu Abstract Genomic analysis on viruses such as SARS-CoV-2 variants: Beta, Gamma, Delta, and Omicron is heavily dominated by classical bioinformatics methods, including Sequence Alignment, Phylogenetic Analysis, and Mutation Frequency Statistics. These approaches use pairwise codon or nucleotide distance matrices to analyze gene sequences, treating them as linear strings rather than capturing their complex contextual interdependencies. We proposed GenEx, a pipeline that converts raw gene sequences into codon co-occurrence graphs and extracts more than 25 graph features. Our two most prominent techniques for graph generation and feature extraction are MSCG (Multi-Scale Codon Co-occurrence Graph) and LAPCG (Linear-time Adjacency PMI Codon Graph). Using these algorithms, we treated codon sequences as structured symbolic vocabularies interpretable to codon co-occurrence graph analysis, a representational paradigm borrowed from computational linguistics. Another major contribution includes implementing a spectral graph feature extraction using Singular Value Decomposition (SVD), using the squared singular value (σ2σ^2) instead of the traditionally used eigenvalue, which helped us to amplify the separation between dominant and subdominant spectral components, thereby enhancing inter-class separability in downstream classification. And to further demonstrate that our method works, we trained 23 benchmarked ML models against the latest SARS-CoV-2 variants, achieving remarkable results in detecting all SARS-CoV-2 variants. Index Terms: Sequence Alignment, Phylogenetic Analysis, Multi-Scale Codon Co-occurrence Graph, Computational linguistics, Spectral graph features. I Introduction Understanding viral genome evolution is a fundamental problem in computational biology, with direct implications for evolutionary studies and vaccine monitoring. While the SARS-CoV-2 pandemic has enabled the collection of large-scale big data on viral genome sequences, conventional methods: phylogenetic tree reconstruction, mutation frequency statistics, and multiple sequence alignment (MSA), heavily focus on retrospective evolutionary events, stationarity, site-independence, and a linear mutation process; thus, failing to capture the complex relationships and interactions within genomic sequences. To resolve these bottlenecks, we propose shifting from the static linear analysis to structural graph models that capture the topological structure of genetic sequences. By constructing codon co-occurrence graphs, where nodes and edges represent codons and their local relationships, respectively, we can capture neighborhood patterns and mutation tendencies that are invisible to traditional approaches. We propose GenEx, a novel Graph-Based Representation framework that models viral genomes as codon-level co-occurrence graphs and identifies distinct topological signatures and spectral properties associated with different viral variants. GenEx extracts spectral and topological features by computing direct-neighbor interactions, generalizing these associations across multiple co-occurrence scales and positional segment encodings; a data-driven graph paradigm for clade classification that prioritizes mathematical explainability and computational efficiency over black-box modeling. This architecture treats variant detection as a measurable task within graph theory, providing a robust, data-driven methodology for classifying viral evolution. We initially focused on SARS-CoV-2 because large-scale genomic sequences were available. This proposed framework will be designed to be adaptable, thus it can extend to other viral families and higher organisms. I-A Motivation: The motivation for this study originated from the following reasons: 1. Limitations of existing genome analysis methods: Traditional gene analysis methods, such as phylogenetic and statistical mutation models, are often constrained by assumptions of linear, site-independent mutation patterns and fail to capture the complex contextual interdependencies within the genomic sequences. 2. Need for “Alignment-Free” Surveillance: With the exponentially growing viral data, alignment-free frameworks are needed to characterize variants through their topological signatures, which enables rapid identification of emerging Variants of Concern (VOC) without bottlenecks. 3. Preparation for Future Pathogens: The research provides a mathematical foundation for the evolution of future pathogens, pandemics, and vaccines by developing a generalizable, alignment-free model applicable to pathogens and higher organisms. I-B Contributions: Our work concentrates on the following aspects: 1. Dual-Paradigm Graph Construction Algorithms: We proposed two novel algorithms, LAPCG and MSCG, to extract codon interaction networks from linear gene sequences with (n)O(n) and (n2)O(n^2) complexity, respectively, while maintaining a 98.75% accuracy. 2. Spectral Feature Engineering and Mathematical Framework: We introduced a Singular Value Decomposition (SVD) based framework that derives seven distinct spectral features from squared singular values (σ2σ^2), providing a numerically stable representation of genomic interaction systems with high inter-class separability. 3. Mathematical Explainability and Biological Interpretation: We were able to provide a rigorous interpretation of viral clades by correlating their biological interpretations with numerical graph properties; thus, we can view the structural mechanisms of viral evolution and variant-specific interaction dynamics. I Related Works Recent progress in computational biology has made genome analysis faster and more scalable. This section briefly reviews the work streams most relevant to GenEx. • Sequence-based Deep Learning Models. CNN- and Transformer-based models treat genomes as linear nucleotide strings for regulatory and mutational prediction [16, 1]. They are effective for sequence pattern recognition, but usually ignore codon-level structure and rely on post-hoc explanation. • Genome Graphs and Pangenome Representations. Genome and pangenome graphs encode population variation with sequence-segment nodes and variant-path edges [4]. These frameworks are useful for representation, but are often non-learning, mostly static, and not built for codon-level mutation feature learning. • Graph Neural Networks in Bioinformatics. GNNs perform well on molecular graphs, protein–protein interaction networks, and gene regulation tasks [17, 5]. However, most studies are static and rarely model codon-level evolutionary dynamics directly. • Evolutionary and Phylogenetic Models. Classical tools such as PAM [3] and BLOSUM [6] are biologically interpretable and foundational. Their limitation is dependence on assumptions such as stationarity and site independence, which can miss nonlinear mutation behavior. • Explainable Genomic AI. Attribution methods (e.g., DeepLIFT [13]) and attention analysis are widely used for interpretability. In practice, most are sequence-centric and post-hoc, giving limited structural insight into codon relationships. • Ab initio and Pipeline-based Gene Annotation. Systems including GENSCAN [2], GeneMark [10], AUGUSTUS [14], GlimmerHMM [11], BRAKER2 [7], MAKER2 [8], and Helixer [15] are strong annotation tools. Their objective, however, is gene-structure annotation, not variant classification through codon co-occurrence topology. • Our Approach (GenEx). GenEx models each genome as a codon co-occurrence graph, where nodes are codons and edges encode positional/mutational coupling. We then classify variants using graph-derived features, yielding interpretable structure-aware signals that can be extended to amino-acid and structure-level graphs. TABLE I: Comparison of Prior Work and Proposed Method Aspect Prior Work Our Method Biological unit Nucleotide / segment Codon Representation Sequence / static graph Co-occurrence graph Temporal modeling No Yes Learning framework CNN / Transformer / rules ML on graph features Explainability Post-hoc Intrinsic (graph-based) Multi-task reuse Limited Yes I Dataset We used the following publicly available SARS-CoV-2 genome sequence datasets from the National Center for Biotechnology Information (NCBI)[12] Virus database to train, validate, and test the GenEx framework: I-A Dataset Collection Process: The SARS-CoV-2 genome sequence data for this research were retrieved using the ncbi-datasets command-line interface. We used the following fetch commands to fetch the variants in ZIP format: • Beta: datasets download virus genome taxon SARS-CoV-2 --lineage B.1.351[12] • Delta: datasets download virus genome taxon SARS-CoV-2 --lineage B.1.617.2[12] • Gamma: datasets download virus genome taxon SARS-CoV-2 --lineage P.1[12] • Omicron: datasets download virus genome taxon SARS-CoV-2 --lineage B.1.1.529[12] After fetching the ZIP files, we extracted beta_sequences.csv, delta_sequences.csv, gamma_sequences.csv, and omicron_sequences.csv. From each CSV file, we selected 1250 randomized sequences, yielding 5000 viral genome sequences in total. I-B Dataset Characteristics and Structure: Each raw CSV file and the extracted sequence CSV files (1250 sequences per variant) had 3 columns: header, sequence, and sequence_length. • header: Contained the NCBI accession ID for the respective genome sequence, the symptoms, virus name (SARS-CoV-2), Host/Carrier, etc., as a single string. • sequence: Contained gene sequences. • sequence_length: Contained an integer representing the length of each gene sequence. I-C Data Pre-processing After downloading the data, we began our pre-processing - • First we took first 10 character deicarding the rest from the header column of the datasets as those first 10 characters made up the accession ID. • The Gnomes are officially stored as cDNA (A,T,G,C) sequences even though SARS-CoV-2 is an RNA (A,T,U,C) virus. Thus, to ensure compatibility with the main stream we avoided unnecessary conversion and maintained the cDNA sequences. • Next, we capitalized the Gene sequences and removed unnecessary sequences and characters that are not relevant to our current work. • We found 20 thousand clean sequences with unique accession ID from each of these variants. IV Methodology IV-A Overview GenEx converts each SARS-CoV-2 nucleotide sequence into a codon graph, extracts structural and spectral descriptors, and then uses these descriptors for variant-level statistical analysis and machine learning classification. We used two graph construction strategies: LAPCG for fast local codon interactions and MSCG for multi-scale codon context modeling. IV-B End-to-end Pipeline 1. Convert each sequence into codons using fixed-frame triplets. 2. Build a weighted codon graph using either LAPCG or MSCG. 3. Compute graph features (topological, path-based, centrality, and spectral). 4. Run significance tests (ANOVA) across variants. 5. Benchmark ML models on extracted feature vectors. Fig. 1: Overview of the GenEx framework for SARS-CoV-2 variant detection using a graph-based approach. The pipeline begins with genome sequence acquisition from NCBI GenBank, followed by preprocessing steps including quality filtering, codon segmentation into triplets, and sequence alignment. Codon co-occurrence graphs are then constructed using two methods—LAPCG (linear-time adjacency-based) and MSCG (multi-scale co-occurrence)—to form weighted undirected graphs. From these graphs, both topological and spectral features are extracted to create high-dimensional feature vectors. These features are used to train and evaluate multiple machine learning models for variant classification. The framework outputs include high-accuracy variant predictions, feature importance analysis, statistical validation, structural graph insights, and evolutionary pattern comparisons. IV-C Codon Segmentation Given a nucleotide sequence S=(n1,n2,…,nL),S=(n_1,n_2,…,n_L), we form codons as non-overlapping triplets: C=(c1,c2,…,c⌊L/3⌋),ci=(n3i−2,n3i−1,n3i).C=(c_1,c_2,…,c_ L/3 ), c_i=(n_3i-2,n_3i-1,n_3i). Ambiguous symbols (e.g., N) are removed before graph construction. IV-D LAPCG: Linear-time Adjacency PMI Codon Graph LAPCG models only adjacent codon pairs (ci,ci+1)(c_i,c_i+1), which provides linear complexity in sequence length and works well for large-scale data. Algorithm 1 LAPCG Graph Construction 0: Codon sequence C=(c1,…,cN)C=(c_1,…,c_N) 0: Undirected weighted graph G=(V,E,W)G=(V,E,W) 1: Initialize node-frequency map F and adjacent-pair map M 2: for i=1i=1 to N do 3: F(ci)←F(ci)+1F(c_i)← F(c_i)+1 4: end for 5: for i=1i=1 to N−1N-1 do 6: u←ci,v←ci+1u← c_i,\;v← c_i+1 7: M(u,v)←M(u,v)+1M(u,v)← M(u,v)+1 unordered pair 8: end for 9: V←V← unique codons in C 10: for all pairs (u,v)(u,v) with M(u,v)>0M(u,v)>0 do 11: p(u,v)←M(u,v)N−1p(u,v)← M(u,v)N-1, p(u)←F(u)Np(u)← F(u)N, p(v)←F(v)Np(v)← F(v)N 12: PMI(u,v)←log(p(u,v)p(u)p(v))PMI(u,v)← \! ( p(u,v)p(u)p(v) ) 13: if PMI(u,v)>0PMI(u,v)>0 then 14: Add edge (u,v)(u,v) with weight PMI(u,v)PMI(u,v) 15: end if 16: end for 17: return G=(V,E,W)G=(V,E,W) IV-E MSCG: Multi-Scale Codon Co-occurrence Graph MSCG extends local adjacency by capturing co-occurrence across multiple codon distances. In our setup, we used scales s∈1,2,3s∈\1,2,3\ with decay weights (1.0,0.5,0.25)(1.0,0.5,0.25) and normalized PMI (NPMI). Algorithm 2 MSCG Graph Construction 0: Codon sequence C=(c1,…,cN)C=(c_1,…,c_N), scales =(s,αs)S=\(s, _s)\ 0: Multi-scale weighted graph G=(V,E,W)G=(V,E,W) 1: Initialize node statistics and empty edge accumulator AeA_e 2: V←V← unique codons in C 3: for all (s,αs)∈(s, _s) do 4: for i=1i=1 to N−sN-s do 5: Observe pair (ci,ci+s)(c_i,c_i+s) and update pair counts 6: end for 7: for all observed pairs (u,v)(u,v) do 8: Compute PMI(u,v)PMI(u,v) and NPMI(u,v)=PMI(u,v)−logp(u,v)NPMI(u,v)= PMI(u,v)- p(u,v) 9: if NPMI(u,v)>0NPMI(u,v)>0 then 10: Ae(u,v)←Ae(u,v)+αs⋅NPMI(u,v)A_e(u,v)← A_e(u,v)+ _s·NPMI(u,v) 11: end if 12: end for 13: end for 14: for all pairs (u,v)(u,v) in AeA_e do 15: Add edge (u,v)(u,v) with accumulated weight Ae(u,v)A_e(u,v) 16: end for 17: return G=(V,E,W)G=(V,E,W) IV-F Feature Extraction and Evaluation From each graph we extracted structural and spectral features, including number of nodes/edges, density, diameter, radius, average shortest path length, Wiener index, transitivity, clustering, centrality scores, graph energy, top singular-spectrum components, max-flow, and matching number. These were used for: • ANOVA-based inter-variant significance analysis, • feature-importance analysis, • model benchmarking across multiple ML families. V Results V-A Model Benchmarking Table I summarizes the best-performing models for baseline PMI, LAPCG, and MSCG. MSCG achieved the strongest overall performance in our benchmark. TABLE I: Benchmark summary: accuracy and runtime across graph construction methods. Method Best Model(s) Accuracy Runtime (s) PMI baseline CatBoost 96.25% 272.3 LAPCG LightGBM, Grad. Boost 96.25% 196.2 MSCG MLP, Bagging Classifier 98.75% 144.6 V-B Computational Efficiency of Graph Construction A critical practical advantage of our proposed methods is their computational efficiency relative to standard PMI-based graph construction. The PMI baseline, which computes global co-occurrence statistics over the entire sequence, requires 272.3 s to complete the full pipeline. LAPCG reduces this to 196.2 s (a 1.39× speedup) by restricting edge computation to adjacent codon pairs, operating in strict O(n)O(n) time. MSCG, despite modeling three co-occurrence scales simultaneously, achieves the lowest runtime of 144.6 s—a 1.88× speedup over the PMI baseline—because the NPMI computation and accumulated edge weighting are implemented as a single-pass accumulation rather than a global normalization step. Crucially, this efficiency gain is not purchased at the cost of accuracy: MSCG also achieves the highest classification accuracy at 98.75%, demonstrating that multi-scale structural modeling of codon co-occurrence is both faster and more discriminative than traditional PMI. These runtime measurements were obtained on the full SARS-CoV-2 genome sequence dataset on a single CPU core, without parallelization. The MSCG pipeline—including graph construction, feature extraction, and ML classification—processes each genome in under 1 s on average, making it suitable for real-time variant surveillance at scale. V-C Comparison with Gene Detection and Variant Classification Methods Table I situates GenEx within the broader landscape of genomic sequence analysis tools. We distinguish two categories: (i) traditional gene annotation tools that predict gene structure from raw sequence (e.g., AUGUSTUS, GeneMark), and (i) variant classification methods that assign a class label to a given genome. Our GenEx falls into the second category. Accuracy figures for gene annotation tools are reported in terms of nucleotide-level sensitivity/specificity, while classification accuracy for variant detection methods corresponds to multi-class labeling performance. TABLE I: Comparison of GenEx with gene annotation tools and SARS-CoV-2 variant classification methods. Gene annotation accuracies reflect nucleotide-level sensitivity; variant classification accuracies reflect multi-class accuracy. † Whole-genome support assumes availability of a closely related reference. Method Type Task Accuracy (reported) Whole Genome Reference GENSCAN Ab initio HMM Gene annotation ∼ 70 - 80% (protein-level) ✓ [2] GeneMark-ES/ET Ab initio (self-train) Gene annotation 35.7 – 75.8% (nucleotide) ✓ [10] SNAP Ab initio HMM Gene annotation 77 - 80% (nucleotide) ✓ [9] GlimmerHMM Ab initio HMM Gene annotation ∼ 9 – 43% (some datasets) ✓ [11] MAKER2 Annotation pipeline Gene annotation 68.60% (nucleotide) ✓ [8] AUGUSTUS Ab initio + evidence Gene annotation 82–92% (gene-level) ✓ [14] BRAKER2 Hybrid (RNA-seq + HMM) Gene annotation >>AUGUSTUS (++2–3%) ✓ [7] Helixer (DL) Deep learning Gene annotation 86.8% (reported) ✓ [15] k-mer + SVM Traditional ML Variant classification ∼ 92.01% ✓ Various CNN-LSTM Deep learning Variant classification ∼ 95–97% Partial Various GenEx LAPCG (Ours) Graph + ML (O(n)O(n)) Variant classification 96.25% ✓ This work GenEx MSCG (Ours) Graph + ML (multi-scale) Variant classification 98.75% ✓ This work GenEx MSCG achieves the highest reported accuracy among all compared methods for its classification task, while also improving computational efficiency over standard PMI-based construction. It is important to note that gene annotation tools address a structurally different problem—predicting gene coordinates in an unannotated genome—and are therefore not directly comparable in terms of accuracy numbers. Nevertheless, placing GenEx alongside these tools provides useful context: our 98.75% accuracy is achieved on a whole-genome, alignment-free basis without any reference sequence or transcriptomic data, which contrasts favorably with the reference-dependent or transcript-dependent nature of hybrid pipeline methods such as BRAKER2 and EVidenceModeler. V-D Feature Importance and Statistical Significance MSCG emphasized both path-based and spectral properties. The highest ranked features were second eigenvalue, average shortest path length, Wiener index, top eigenvalue, and radius. ANOVA analysis further showed strong between-variant separation for radius (F=69.74F=69.74, p=3.14×10−36p=3.14× 10^-36), average shortest path length (F=60.19F=60.19, p=4.43×10−32p=4.43× 10^-32), top eigenvalue (F=47.82F=47.82, p=2.14×10−26p=2.14× 10^-26), and number of edges (F=33.52F=33.52, p=2.51×10−19p=2.51× 10^-19). V-E Variant Structural Profiles Figure 2 summarizes all four variant structural profiles in a single 2×2 panel, so the visual comparison remains compact and the text flow stays uninterrupted. Fig. 2: Individual and Combined structural profiles for Beta, Gamma, Delta, and Omicron V-F Cross-Variant Comparative Trend The parallel-coordinate view (Fig. 3) highlights how graph-derived features evolve differently across variants while preserving an overall shared structural backbone. Each polyline represents one genome sample; color encodes the variant class. This supports the idea that codon graph topology captures both conserved genome organization and variant-specific signatures simultaneously. Note how features such as matching number and stable rank sharply diverge for Omicron samples (visible in the upper and lower rows of the plot), while spectral measures such as top eigenvalue and graph energy remain highly conserved across all four clades. Fig. 3: Parallel-coordinate comparison of ten structural graph features across four SARS-CoV-2 variants of concern (Beta, Oct 2020; Gamma, Nov 2020; Delta, Apr 2021; Omicron, Nov 2021). Each polyline represents one variant; color encodes variant class. The ten axes correspond to: second eigenvalue (sev), average shortest path length (aspl), Wiener index (wi), top eigenvalue (tev), radius (r), graph energy (ge), diameter (d), average clustering coefficient (aclu), average closeness centrality (aclo), and transitivity (t). All values are min–max normalised to [0,1][0,1]. Omicron consistently occupies the highest band across spectral and centrality axes (ge, aclu, aclo), while Delta remains near the minimum on most features, highlighting a sharp structural divergence between these two variants. V-G Interpretation This section presents a biological and structural interpretation of the graph theoretic features extracted from the genome sequences of four SARS-CoV-2 variants: Beta (B.1.351), Gamma (P.1), Delta (B.1.617.2), and Omicron (B.1.1.529).[12] Each genome sequence was represented as a graph, and 22 graphical properties were computed. The interpretation is organized into two subsections: (i) structural profile for each variant, (i) comparative analysis of structural similarities and dissimilarities across the four variants. V-H Structural Profiles of Individual Variants Each variant yields a distinct genomic graph fingerprint, defined by a combination of conserved baseline properties and variant-specific outlier behavior. V-H1 Beta (B.1.351) The Beta variant is characterized by a structurally stable median profile, combined with the most extreme individual outliers observed across the entire dataset, making it the most internally volatile variant at the graph level. From the graphs generated, it can be observed that the beta variants’ genomic sequences produce dense interconnected networks with nearly complete graphs. This is reflected in the median graph density of ∼0.97 0.97, which also indicates strong tendencies to conserve the viral backbone. Similarly, transitivity and average clustering coefficient values are about 0.96–0.97 across most Beta samples, confirming that local genomic neighborhoods are tightly triangulated. The average shortest path length and the median diameter of nearly 6.2 and 9.5, respectively, establish that the Beta genome graph exhibits a compact, small-world organization in which any genomic region is reachable from any other within a limited number of steps. Regardless of the stable core, Beta sequences exhibit volatile-periphery anomalies, with several extreme outliers. From the graphical feature extraction, we have observed that at least one Beta sequence generates a Wiener Index of ∼45,000 45,000, roughly thrice the typical value (vs. typical ∼15,000 15,000) for other variants, indicating greater distances between genomic units. This longer genomic distance indicates extensive deletions or structural rearrangements, which elongated the internal pathways of the graph. Another similar phenomenon can be observed where one Beta sample produced a value of ∼4×1010 4× 10^10 (the highest in the dataset). Furthermore, a beta sequence dropped its average closeness centrality to 0.6, while the remaining clade clusters were near 0.98–0.99, indicating structurally remote regions of the graph from a connectivity-severing deletion. Finally, Beta’s maximum flow distribution is the widest of all four variants (spanning about 9.2 to 10.0), showing highly variable capacity for parallel information propagation. V-H2 Gamma (P.1) Among the four variants, Gamma displays the broadest intra-clade structural diversity within its clade. While the outlying values for the Beta variant are found in only certain graphical features, Gamma distributes its structural variability across multiple graph properties simultaneously, producing the most heterogeneous collection of genome graphs in the dataset. Gamma has ∼110 110 nodes (an upward outlier), the highest in the dataset, compared to the average median of 65–70 across other variants, making Gamma a diverse and insertion-rich sample; the largest connected component of a Gamma sample reaches ∼115 115 nodes, the highest amongst all variants. This variant tends not to form isolated subgraphs; rather, it forms a single, unfragmented, interconnected giant graph. Furthermore, Gamma has the widest and highest diameter distribution among the variants, with outliers reaching up to 11.5. This physical elongation, along with the high betweenness centrality of Gamma, with outliers reaching up to ∼0.006 0.006, implies that specific sites in the genomic sequences act as bridge notes controlling the information flow between distant genomic regions. In addition, the graph energy of Gamma outliers reaches up to ∼175 175, much higher than the typical 115–120 range. The higher structural complexity suggests a different eigenvalue distribution and indicates recombinant or heavily mutated genome sequences. Moreover, Gamma displays the lowest transitivity across the variants, outliers dropping to ∼0.84 0.84, which suggests that local neighborhood structures are less triangulated and the otherwise conserved co-occurrence relationships have been disrupted. Overall, Gamma shows signs of extensive evolutionary development; the graphs span the widest range of organizational forms: elongated, bridge-dominated, and energy-rich structures. This structural variation depicts the different insertion events of the P.1 lineage, creating functional differences that require further investigation. V-H3 Delta (B.1.617.2) Delta is the most structurally disciplined variant in this dataset, producing genome graphs that are structurally consistent, compact, and well-clustered. Across almost every graph measure among the variants, Delta has the tightest distributions, intra-clade variance, and fewest extreme outliers, demonstrating the highest structural conservation. It yielded small and consistent networks with a median size of 65-70 nodes and approximately 2,000 edges, reflecting a marked degree of uniformity in structural magnitude. The distribution of its Wiener index is close to 15,000, indicating that the Delta genome graph is highly cohesive and replicable. Furthermore, Delta has a clustering coefficient with a median of ∼0.955 0.955 (marginally lower than Beta and Gamma). The slight relaxation in triplet formation within this genomic network is consistent with the double-mutation feature of Delta (L452R and T478K), in which each region becomes slightly less mutually dependent on the others. Additionally, its spectral gap is the lowest among all four variants at ∼81.0 81.0, indicating marginally less algebraic connectivity robustness. In particular, Delta has no extreme outliers in either its condition number or its stable rank, which results in yielding a consistently well-conditioned adjacency matrix with linearly independent, non-redundant, and non-degenerate structural motifs. Moreover, Delta also maintains an extremely low value for its matching number at ∼3 3, which indicates that the genomic sequences of these variants’ mutations do not produce independent modular components, keeping the genome a single, tightly integrated graph body. The sole exception is a single extreme-low-density outlier at ∼0.3 0.3 (the typical value is ∼0.97 0.97). This anomaly depicts a highly sparse graph with fewer edges; probably caused by sequencing artifact, highly defective genome, or large-scale deletion events rather than true mutation biology. Except for this outlier, Delta’s profile can be defined by maximum conservation, achieving dominance by consolidating and optimizing a single, efficient genomic organization. V-H4 Omicron (B.1.1.529) The Omicron variant presents the most structurally complex and structurally modular genomic graph profile in this dataset. The most prominent graphical feature of Omicron is the matching number, which reaches up to ∼55 55, whereas the other variants have a value of ∼3 3, 18 times lower than Omicron. As the matching number indicates the size of an independent maximum edge set, this extreme escalation indicates that the genome graph contains a vast array of structurally non-overlapping, independent motifs. From a biological perspective, this is explained by the fact that Omicron has accumulated more than 30 spike protein mutations located at distinct independent sequence sites. This framework measures the independent evolutionary landscape of Omicron and depicts that its mutations are not clustered but are separate events. Moreover, the structural diversification is evident in the increased stable rank, reaching ∼1.75 1.75 for some Omicron sequences, whereas in other variants it lies in the 1.3–1.4 range. Stable rank indicates a higher effective dimensionality, which proves that Omicron graph structures occupy more complex and higher-dimensional spaces rather than being mere scale-ups of previous variants. This diversity is also shown by the increased Frobenius norm in Omicron graphs, which is ∼12.5 12.5 (compared to the typical ∼10.5 10.5), indicating greater structural mass and expansion in genomic connections. However, the modularity does not hinder global coherence as Omicron has the highest median average closeness centrality of ∼0.985 0.985, ensuring that the nodes are well integrated and efficiently traversable. Omicron has the highest median spectral gap, along with Beta (∼81.5 81.5), and indicates the widest overall spread; this indicates a high algebraic strength, which will enable its functionality even when certain epitope-coding regions are disrupted. Overall, with transitivity and average clustering remaining around 0.96, except for one downward outlier, Omicron achieves a unique change. It maximizes structural modularity while keeping global resilience intact. V-I Structural Similarities and Dissimilarities Across Variants After identifying the unique structural identities of the four variants individually, this section presents the comparative patterns that emerged across the variants. The comparative analysis has been categorized into four points: (i) conserved global structure, (i) structural clustering through hierarchical analysis, (i) patterns of divergence in specific variants, and (iv) the spectral characteristics unique to each variant. V-I1 Conserved Global Topology Across Variants One of the most prominent cross-variant observations is the presence of strong conservation, with a highly consistent global small-world topological architecture regardless of the strong evolutionary pressure. For all the variants used in this study, Beta, Gamma, Delta, and Omicron, the genomic graphs demonstrate near-identical median values across fundamental graph theoretical features: median density of ∼0.95 0.95–0.970.97, mean shortest path length of ∼6.2 6.2, median diameter of ∼9.5 9.5, and transitivity and average clustering coefficient ∼0.96 0.96–0.970.97. Average betweenness centrality remains consistently low at around 0.001 across all variants, thus implying the absence of any dominant bottleneck in globally yet locally strongly connected graphs. This convergence of topological characteristics is supported by similar spectral clustering results, including the largest eigenvalue ∼85 85–8686, graph energy ∼115 115–120120, and consistency in the second eigenvalue around 5.3 across all four variants. This consistency of spectral graph features depicts that the structural complexity and graph energy remain unchanged even with the emergence of new mutations on the surface, thus indicating that the eigenvalue spectrum controls the functionality and dynamics of the genome, such as synchronization and diffusion within the SARS-CoV-2 genome. V-I2 Hierarchical Clustering Hierarchical clustering on the full set of graph-theoretic features produces a dendrogram that reveals two distinct structural clusters: Beta and Delta cluster together at a distance of approximately 5.7, while Gamma and Omicron cluster together at a distance of approximately 7.3. The two super-clusters merge at a distance of approximately 9.6, indicating a substantial structural divide between the two groups. The Beta–Delta (distance ∼5.7 5.7) pairing is notable for its disparity between phylogenetic classification based on nucleotide sequence data and clustering of structures, which classify Beta and Delta as the most structurally related pair, regardless of arising independently from separate regions and lineages. Thus, it can be said that Beta and Delta converged on a similar genomic graph through independent evolution; this phenomenon of convergence is probably driven by identical functional constraints and features: higher binding affinity with the ACE2 receptor and immunity evasions. This Beta, Delta cluster represents an evolutionary strategy of structural consolidation, characterized by tighter distributions and fewer outlier events. The Gamma—Omicron (distance ∼7.3 7.3) pair is also noteworthy as Gamma and Omicron share more structural similarity with each other than with Beta or Delta, despite Gamma emerging from the B.1.1.28 lineage in Brazil and Omicron emerging in South Africa and representing a deeply diverged lineage of uncertain ancestral origin. The grouping of these two strains could indicate convergence, common mutational patterns affecting genomically similar regions, or similar selective forces leading to structural convergence toward a similar set of structural features relevant to immune avoidance or transmission capabilities. The Gamma, Omicron cluster follows an evolutionary path of growing structural complexity and divergence, with greater structural diversity and outlier events. Eventually, the two super-clusters Beta, Delta and Gamma, Omicron merge at ∼9.6 9.6, representing a substantial structural discontinuity between the two. Fig. 4: Hierarchical Clustering of SARS-CoV-2 Variants by Graph Features. The ten features in x-axis correspond to: second eigenvalue (sev), average shortest path length (aspl), Wiener index (wi), top eigenvalue (tev), radius (r), graph energy (ge), diameter (d), average clustering coefficient (aclu), average closeness centrality (aclo), and transitivity (t). All values are min–max normalised to [0,1][0,1]. Omicron consistently occupies the highest band across spectral and centrality axes (ge, aclu, aclo), while Delta remains near the minimum on most features, highlighting a sharp structural divergence between these two variants. V-I3 Variant-Specific Structural Divergence While the conserved global topology unifies all four variants at the median level, each variant diverges from the others in distinct ways that are specific to its graph-theoretic profile. Beta diverges primarily through extreme outlier events in the Wiener index, condition number, and closeness centrality. These outliers occur independently and are not consistently co-occurring within the same samples, suggesting that Beta harbors multiple distinct mechanisms of structural disruption at the sublineage level. Beta’s structural divergence is therefore characterized by intra-clade heterogeneity rather than a systematic shift of the entire clade away from the median. Gamma diverges when multiple structural complexity features are simultaneously increased, including larger diameter, higher betweenness centrality, greater graph energy, and lower transitivity. These properties may all stem from a shared cause: the inclusion of genomic material. This elongates the graphs, creates bridge positions, raises the eigenvalue-based complexity, and disrupts local triangular structures. Thus, the divergence in Gamma is more structurally coherent than that of Beta: it shows a systematic structural reorganization in a subset of sequences rather than unrelated isolated changes. Delta diverges minimally and specifically. Its only major cross-variant departure is the extreme low-density outlier, which is likely artifactual. In all other respects, Delta’s distributions are the closest to the cross-variant consensus of any clade. Delta’s structural divergence is negligible at the clade level, reinforcing its identity as the most evolutionarily conservative variant from a graph-theoretic perspective. Omicron’s matching number provides its clearest and most consistent divergence. Unlike the outlier events in Beta and Gamma, which are visible in only a fraction of samples, Omicron’s elevated matching number is a systematic property that distinguishes the entire high end of the Omicron distribution from all other variants. Combined with its elevated stable rank, Omicron’s divergence reflects a genuine structural transition—a qualitative change in the type of genome graph produced—rather than quantitative extremes within an otherwise familiar structural framework. V-I4 Spectral and Algebraic Divergence Spectral and algebraic analysis adds a second comparative layer. Although the top eigenvalue is extremely conserved across all variants at a range of ∼85 85–8686, which indicates a strong global structural similarity, the spectral gap (measures algebraic connectivity robustness) differs significantly: both Beta and Omicron have the highest median values at about 81.5, Delta possesses the smallest at ∼81.0 81.0, and Gamma falls between them. Condition number demonstrates the most divergent algebraic structure from the rest; while being relatively small and stable for all other variants, the outlying condition number of a near-singular Beta adjacency matrix approaches an astronomical value of roughly 4×10104× 10^10, suggesting a very brittle, algebraically sensitive graph prone to big perturbations. This creates a sharp contrast with the consistently well-conditioned Delta graphs and structurally robust Omicron graphs. Furthermore, while the Frobenius norm (reflects the overall magnitude of the adjacency matrix) remains relatively constant for all variants at about 10.5, Omicron displays its own set of outliers reaching 12.5. This elevated structural mass further corroborates Omicron’s unique matching number and stable rank, reinforcing that it represents a quantitatively distinct, complex structural state at the algebraic level. In summary, viral graph evolution appears to follow two concurrent trends: the conservation of structural backbone and variant-specific algebraic fingerprints. The clustering achieved by the GenEX pipeline differs from that of sequence-only phylogeny, indicating that graph-theoretic analysis captures an additional axis of viral evolution that complements sequence-based methods. VI Conclusion Here, we presented a unified benchmarking pipeline for the structural analysis of SARS-CoV-2 variants: Beta, Delta, Gamma, and Omicron, at the nucleotide and codon level, through graphical analysis of the codon interaction network system. We introduced two novel algorithms to overcome the limitations of linear sequence analysis, currently used in genome sequence analysis: (i) Linear-time Adjacency PMI Codon Graph (LAPCG) and (i) Multi-Scale Codon Co-occurrence Graph (MSCG). By representing genomic sequences as interaction networks and extracting spectral and topological features, we demonstrated that variants possess unique structural fingerprints that can be accurately classified using machine learning models such as Random Forests, Extra Trees, and LightGBM. The structural interpretation of these networks provided critical insights into the virus’s evolutionary trajectory. LAPCG is a well-optimized algorithm for graph extraction and feature computation that uses direct-neighbor approximation to achieve linear-time complexity O(n). In contrast, MSCG is a mathematically principled approach with the capability to model complex inter-context dependencies at multiple co-occurrence scales. Based on our results, MSCG (utilizing Normalized PMI and positional node encoding) has maintained an accuracy of 98.75%, hence establishing a robust, alignment-free framework for genomic analysis. Although currently focused on codon transition patterns, this work identifies vital topological biomarkers and explainability of viral genome sequences across clades and generations, using mathematical and graphical models. Future research will focus on integrating protein structural data and time-aware viral genomic evolution, and on extending this pipeline to other viruses and higher organisms. References [1] Ž. Avsec, V. Agarwal, D. Visentin, et al. (2021) Effective gene expression prediction from sequence by integrating long-range interactions. Nature Methods 18, p. 1196–1203. External Links: Document, Link Cited by: 1st item. [2] C. Burge and S. Karlin (1997) Prediction of complete gene structures in human genomic dna. Journal of Molecular Biology 268 (1), p. 78–94. External Links: Document Cited by: 6th item, TABLE I. [3] M. O. Dayhoff, R. M. Schwartz, and B. C. Orcutt (1978) A model of evolutionary change in proteins. In Atlas of Protein Sequence and Structure, M. O. Dayhoff (Ed.), Vol. 5, p. 345–352. Cited by: 4th item. [4] E. Garrison, J. Sirén, A. M. Novak, G. Hickey, J. M. Eizenga, E. T. Dawson, W. Jones, S. Garg, C. Markello, M. F. Lin, B. Paten, and R. Durbin (2018) Variation graph toolkit improves read mapping by representing genetic variation in the reference. Nature Biotechnology 36 (9), p. 875–879. External Links: Document Cited by: 2nd item. [5] J. Gilmer, K. T. Schüt, P. Glawe, G. Klambauer, A. Smola, and M. Welling (2017) Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning, ICML. External Links: Link Cited by: 3rd item. [6] S. Henikoff and J. G. Henikoff (1992) Amino acid substitution matrices from protein blocks. Proceedings of the National Academy of Sciences of the United States of America 89 (22), p. 10915–10919. External Links: Document Cited by: 4th item. [7] K. J. Hoff, A. Lomsadze, M. Borodovsky, and M. Stanke (2019) Whole-genome annotation with BRAKER. In Methods in Molecular Biology, Vol. 1962, p. 65–95. External Links: Document Cited by: 6th item, TABLE I. [8] C. Holt and M. Yandell (2011) MAKER2: an annotation pipeline and genome-database management tool for second-generation genome projects. BMC Bioinformatics 12, p. 491. External Links: Document, Link Cited by: 6th item, TABLE I. [9] I. Korf (2004) Gene finding in novel genomes. BMC Bioinformatics 5, p. 59. External Links: Document Cited by: TABLE I. [10] A. Lomsadze, V. Ter-Hovhannisyan, Y. O. Chernoff, and M. Borodovsky (2005) Gene identification in novel eukaryotic genomes by self-training algorithm. Nucleic Acids Research 33 (20), p. 6494–6506. External Links: Document Cited by: 6th item, TABLE I. [11] W. H. Majoros, M. Pertea, and S. L. Salzberg (2004) TigrScan and GlimmerHMM: two open source ab initio eukaryotic gene-finders. Bioinformatics 20 (16), p. 2878–2879. External Links: Document Cited by: 6th item, TABLE I. [12] National Center for Biotechnology Information (2026) NCBI. Note: https://w.ncbi.nlm.nih.gov/Accessed: 2026-02-22 Cited by: 1st item, 2nd item, 3rd item, 4th item, §I, §V-G. [13] A. Shrikumar, P. Greenside, and A. Kundaje (2019) Learning important features through propagating activation differences. External Links: 1704.02685, Link Cited by: 5th item. [14] M. Stanke, M. E. Diekhans, R. Baertsch, and D. Haussler (2008) Using native and syntenically mapped cDNA alignments to improve de novo gene finding. Bioinformatics 24 (5), p. 637–644. External Links: Link Cited by: 6th item, TABLE I. [15] F. Stiehler, M. Steinborn, S. Scholz, D. Dey, A. P. M. Weber, and A. K. Denton (2021) Helixer: cross-species gene annotation of large eukaryotic genomes using deep learning. Bioinformatics 36 (22-23), p. 5291–5298. External Links: Document, Link, ISSN 1367-4803 Cited by: 6th item, TABLE I. [16] J. Zhou and O. Troyanskaya (2015) Predicting effects of noncoding variants with deep learning–based sequence model. Nature Methods 12, p. 931–934. External Links: Document, Link Cited by: 1st item. [17] M. Zitnik, M. Agrawal, and J. Leskovec (2018) Modeling polypharmacy side effects with graph convolutional networks. Bioinformatics 34 (13), p. i457–i466. External Links: ISSN 1367-4811, Link, Document Cited by: 3rd item.