GenEx: A Graph-Based Representational Paradigm for SARS-CoV-2 Variant Detection via Codon Co-occurrence Networks

arXiv:2608.182382026-08-20

Turning viral gene sequences into codon relationship maps to tell coronavirus variants apart

Older methods for distinguishing COVID-19 variants (Beta, Gamma, Delta, Omicron) treated gene sequences as flat strings and compared them letter by letter, missing complex internal relationships. The researchers built a pipeline called GenEx that splits gene sequences into codons (three-letter units) and builds a graph—a network of dots and connecting lines—showing how codons relate to their neighbors. From these graphs they extracted more than 25 structural features and trained 23 machine learning models, reaching up to 98.75% accuracy at telling the variants apart.

METAL MEDIA explanatory visual

Turning viral gene sequences into codon relationship maps to tell coronavirus variants apart

01Gene sequences were cut into codons, then turned into graphs two ways: LAPCG links each codon only to its immediate neighbor, while MSCG links codons that appear together across multiple distances.
02From each graph they pulled over 25 features, including basic structural measures like node count, shortest path length, and density, plus spectral (eigenvalue-based) properties.
03They used squared singular values (σ²) from singular value decomposition instead of standard eigenvalues, which made the differences between variants stand out more clearly.
04Tested across 23 machine learning models, the MSCG method performed best, hitting 98.75% accuracy while also running 1.88 times faster than the standard PMI-based approach.
05Each variant showed its own distinct graph fingerprint—for example Omicron's matching number was 18 times higher than other variants, while Delta had the most stable, consistent structure—revealing evolutionary patterns invisible to sequence-only phylogenetics.

An explanatory diagram made by METAL MEDIA, not a figure supplied by the paper's authors.

What they did

Gene sequences were cut into codons, then turned into graphs two ways: LAPCG links each codon only to its immediate neighbor, while MSCG links codons that appear together across multiple distances.
From each graph they pulled over 25 features, including basic structural measures like node count, shortest path length, and density, plus spectral (eigenvalue-based) properties.
They used squared singular values (σ²) from singular value decomposition instead of standard eigenvalues, which made the differences between variants stand out more clearly.
Tested across 23 machine learning models, the MSCG method performed best, hitting 98.75% accuracy while also running 1.88 times faster than the standard PMI-based approach.
Each variant showed its own distinct graph fingerprint—for example Omicron's matching number was 18 times higher than other variants, while Delta had the most stable, consistent structure—revealing evolutionary patterns invisible to sequence-only phylogenetics.

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.

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

Fig. 2: Individual and Combined structural profiles for Beta, Gamma, Delta, and Omicron

TABLE II: 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

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]. 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.

TABLE III: 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))	Variant classification	96.25%	✓	This work
GenEx MSCG (Ours)	Graph + ML (multi-scale)	Variant classification	98.75%	✓	This work

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]. 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.

Why it matters

This approach can classify large-scale viral genome data quickly without needing a reference sequence or alignment step, making it practical for near real-time surveillance of new variants as they emerge. It also offers a framework that could extend beyond COVID-19 to other viruses and organisms, adding a structural lens to genomic analysis.

Terms in this paper

Codon · a set of three nucleotide letters that encodes one amino acid
PMI (Pointwise Mutual Information) · a measure of how much more often two items appear together than expected by chance
Singular Value Decomposition (SVD) · a mathematical technique that breaks a matrix into components to reveal its core structure
ANOVA · a statistical test for whether differences between group averages are significant
Matching number · the size of the largest set of non-overlapping connections in a graph

Original abstract (English)

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.

Authors · Arefin Amin, Labiba Faiza Karim, M. Monir Uddin

Read on arXiv

Latest papers

All papers →

Latest from METAL MEDIA

NCT 127 drop BLINGY, their first full album in two years

Figures: Arefin Amin et al., arXiv:2608.18238, CC BY 4.0