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

cs.AIAug 18, 2026

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

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

Organizations: ECE Department North South University Dhaka, Bangladesh · Department of Math. & Phy. North South University Dhaka, Bangladesh

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$ ) 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.

Figures & tables

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

TABLE I: Comparison of Prior Work and Proposed Method

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.

\mathrm{NPMI}(u,v)=\frac{\mathrm{PMI}(u,v)}{-\log p(u,v)}

Algorithm 2 MSCG Graph Construction

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

TABLE II: Benchmark summary: accuracy and runtime across graph construction methods.

Method	Type	Task	Accuracy (reported)	Whole Genome	Reference
GENSCAN	Ab initio HMM	Gene annotation	$\sim$ 70 - 80% (protein-level)	✓	[ 9 ]
GeneMark-ES/ET	Ab initio (self-train)	Gene annotation	35.7 – 75.8% (nucleotide)	✓	[ 10 ]
SNAP	Ab initio HMM	Gene annotation	77 - 80% (nucleotide)	✓	[ 17 ]
GlimmerHMM	Ab initio HMM	Gene annotation	$\sim$ 9 – 43% (some datasets)	✓	[ 12 ]
MAKER2	Annotation pipeline	Gene annotation	68.60% (nucleotide)	✓	[ 14 ]
AUGUSTUS	Ab initio + evidence	Gene annotation	82–92% (gene-level)	✓	[ 11 ]

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.

\dagger

Whole-genome support assumes availability of a closely related reference.

Panel of Figure 6 — Fig. 2: Individual and Combined structural profiles for Beta, Gamma, Delta, and Omicron

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.

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.

Genomics

Genomics uses computational and experimental methods to study genomes, genetic variation, gene regulation, and their links to traits and disease.

See all 126 papers

Mining Negative Sequential Patterns to Improve Viral Genomic Feature Representation and Classification
Apr 28, 2026Wenxi Zhu, Wensheng Gan, Zhenlian QiGenomics Sequence Modeling
College of Information Science and Technology, Jinan University, Guangzhou 510632, China · College of Cyber Security, Jinan University, Guangzhou 510632, China · Guangdong Eco-Engineering Polytechnic, Guangzhou 510520, China
ViroGym: Realistic Large-Scale Benchmarks for Evaluating Viral Proteins
Mar 6, 2026Yichen Zhou, Jonathan Golob, Amir Karimi +2Protein Language Models Protein Fitness Prediction
GlaxoSmithKline · Technical University of Munich · University of Washington +1
When Genomic Masking Priors Fail to Transfer: Strong Variant Prediction, Weak Functional Generation
Sep 4, 2026Susu Hu, Preetam Gattogi, Jens Lehmann +3Masked Diffusion Models Genomic Foundation Models
Translational Surgical Oncology, National Center for Tumor Diseases (NCT/UCC), Dresden, Germany · Faculty of Medicine and University Hospital Carl Gustav Carus, TU Dresden, Germany · Helmholtz-Zentrum Dresden-Rossendorf (HZDR), Dresden, Germany +8

Apr 28, 2026J/K move · Enter open · S save

Mining Negative Sequential Patterns to Improve Viral Genomic Feature Representation and Classification

Wenxi Zhu, Wensheng Gan, Zhenlian Qi

College of Information Science and Technology, Jinan University, Guangzhou 510632, China · College of Cyber Security, Jinan University, Guangzhou 510632, China · Guangdong Eco-Engineering Polytechnic, Guangzhou 510520, China

Genomics Sequence Modeling

Open paper AskPDF arXiv

Viruses represent the most abundant biological entities on Earth and play a pivotal role in microbial ecosystems, yet, as prominent human pathogens, they are closely linked to human morbidity and mortality. Accurate identification of viral sequences from viral genome sequences is therefore essential, but existing genome-based classification models that largely relying on composition- or frequency-based subsequence features often suffer from limited interpretability and reduced accuracy, particularly on complex or imbalanced datasets. To address these limitations, we propose GeneNSPCla (Genomic Negative Sequential Pattern-based Classification), a novel viral classification framework based on Negative Sequential Patterns (NSPs) that extracts discriminative absence-based features from nucleotide sequences of RNA viral genomes. By transforming these NSPs into numerical feature vectors and integrating them into multiple supervised classifiers, GeneNSPCla effectively captures both presence and absence signals in viral sequences. Furthermore, we propose a negative pattern mining algorithm adapted for processing genomic data: GONPM+, which can discover longer and more biologically meaningful negative sequential patterns. The experimental results demonstrate that the average accuracy of GONPM+ in 8 classifiers has improved by 10.03% compared to the original negative pattern mining algorithm and by 24.75% compared to the positive pattern mining algorithm. These findings highlight the effectiveness of incorporating absence-based sequential information, providing a new and complementary perspective for viral genome analysis and classification.

Abstract

Genomics

Explore similar work

Mining Negative Sequential Patterns to Improve Viral Genomic Feature Representation and Classification

ViroGym: Realistic Large-Scale Benchmarks for Evaluating Viral Proteins

When Genomic Masking Priors Fail to Transfer: Strong Variant Prediction, Weak Functional Generation