PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2608.18238v1cs.AIq-bio.QM

TL;DR

Conventional SARS-CoV-2 sequence analyses treat genomes as linear strings and do not capture contextual interdependencies. GenEx represents sequences as codon co-occurrence graphs, and MSCG achieved 98.75% classification accuracy while reducing pipeline runtime to 144.6 s.

  • Problem

    Conventional phylogenetic, mutation-frequency, and alignment methods assume linear, site-independent patterns and do not capture complex genomic interdependencies.

  • Method

    GenEx converts nucleotide sequences into codon co-occurrence graphs using LAPCG and MSCG, then extracts structural and spectral descriptors for variant classification.

  • Results

    98.75% accuracy was achieved by MSCG, which also completed the full pipeline in 144.6 s, the lowest runtime among compared graph-construction methods.

  • Takeaways & Limitations

    GenEx provides an alignment-free graph-based framework for classifying SARS-CoV-2 variants through distinct structural fingerprints.

Abstract

from arXiv · show

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.

I. INTRODUCTION … II. RELATED WORKS

GenEx addresses the limits of linear, site-independent genome analysis by representing viral genomes as codon co-occurrence graphs that capture contextual relationships and variant-specific structure. The paper introduces LAPCG, MSCG, and SVD-based spectral features, positioning GenEx as an interpretable, alignment-free framework for variant classification alongside related computational-biology approaches.

  • I. INTRODUCTION: Traditional phylogenetic, mutation-frequency, and alignment methods emphasize retrospective, stationary, site-independent patterns and miss complex genomic interdependencies.These limitations motivate a representation that models contextual relationships rather than treating sequences only as linear strings.
  • I. INTRODUCTION: Codon co-occurrence graphs represent codons as nodes and local relationships as edges, exposing neighborhood patterns and mutation tendencies hidden from traditional methods.The graph representation provides the structural basis for GenEx’s alignment-free analysis.
  • I. INTRODUCTION: GenEx models viral genomes as codon-level co-occurrence graphs and identifies variant-associated topological signatures and spectral properties for clade classification.It extracts features from direct-neighbor interactions across multiple co-occurrence scales and positional segment encodings.
  • A. Motivation:: The study seeks a generalizable, alignment-free model applicable to pathogens and higher organisms, supporting analysis of future pathogens, pandemics, and vaccines.This motivation extends beyond SARS-CoV-2 variant detection.
  • B. Contributions:: LAPCG and MSCG construct codon interaction networks with O(n) and O(n^2) complexity, respectively, while maintaining 98.75% accuracy.These algorithms constitute GenEx’s dual-paradigm graph-construction component.
  • B. Contributions:: GenEx introduces an SVD-based spectral framework that derives seven spectral features from squared singular values, σ^2.The squared-singular-value formulation is presented as the basis for spectral feature engineering.
  • II. RELATED WORKS: Prior work includes sequence deep learning, genome and pangenome graphs, GNNs, evolutionary models, explainable genomic AI, and gene-annotation pipelines, but these approaches generally do not learn codon-level evolutionary topology for variant classification.The reviewed methods are described as sequence-centric, static, post-hoc, assumption-dependent, or focused on annotation rather than codon co-occurrence topology.

III. DATASET · A. Dataset Collection Process:

The GenEx framework used publicly available SARS-CoV-2 genome sequences from NCBI’s Virus database for training, validation, and testing. Sequences for Beta, Delta, Gamma, and Omicron were retrieved with ncbi-datasets commands and organized into variant-specific CSV files.

  • III. DATASET: GenEx used publicly available SARS-CoV-2 genome sequence datasets from NCBI’s Virus database for training, validation, and testing.
  • A. Dataset Collection Process:: The SARS-CoV-2 genome sequences were retrieved using the ncbi-datasets command-line interface.
  • A. Dataset Collection Process:: Beta sequences were fetched with the command datasets download virus genome taxon SARS-CoV-2 --lineage B.1.351.
  • A. Dataset Collection Process:: Delta sequences were fetched with the command datasets download virus genome taxon SARS-CoV-2 --lineage B.1.617.2.
  • A. Dataset Collection Process:: Gamma sequences were fetched with the command datasets download virus genome taxon SARS-CoV-2 --lineage P.1.
  • A. Dataset Collection Process:: Omicron sequences were fetched with the B.1.1.529 lineage command, then 1,250 randomized sequences per variant were selected from CSV files, totaling 5,000 sequences.The extracted files were beta_sequences.csv, delta_sequences.csv, gamma_sequences.csv, and omicron_sequences.csv.

B. Dataset Characteristics and Structure: · C. Data Pre-processing

The datasets comprised sequence CSV files with standardized three-column records and 1,250 sequences per variant. Pre-processing retained accession identifiers and cDNA representation, cleaned sequence content, and yielded 20 thousand unique-accession sequences per variant.

  • B. Dataset Characteristics and Structure:: Each raw and extracted sequence CSV contained 3 columns: header, sequence, and sequence length, with 1250 sequences per variant.The header stored metadata, while the sequence and sequence length columns stored gene sequences and their integer lengths.
  • B. Dataset Characteristics and Structure:: The header column stored the NCBI accession ID, symptoms, virus name, Host/Carrier, and related information as a single string.The virus name was SARS-CoV-2.
  • B. Dataset Characteristics and Structure:: The sequence column contained gene sequences, and sequence length contained an integer representing each gene sequence’s length.These fields provided the sequence content and its corresponding length.
  • C. Data Pre-processing: Pre-processing began after the data were downloaded.This marked the start of the dataset preparation procedure.
  • C. Data Pre-processing: The first 10 characters of each header were retained because they constituted the accession ID, while the remaining header content was discarded.This reduced the header to the accession identifier used during preparation.
  • C. Data Pre-processing: Because the genomes were stored as cDNA sequences, the workflow retained A,T,G,C notation instead of converting to RNA A,T,U,C notation.The stated rationale was compatibility with the mainstream representation.
  • C. Data Pre-processing: Gene sequences were capitalized, and unnecessary sequences and irrelevant characters were removed.These operations were part of sequence cleaning for the current work.
  • C. Data Pre-processing: 20 thousand clean sequences with unique accession IDs were found from each variant.The processed collection was reported separately for each variant.

IV. METHODOLOGY … D. LAPCG: Linear-time Adjacency PMI Codon Graph

GenEx transforms SARS-CoV-2 nucleotide sequences into codon co-occurrence graphs, extracts graph descriptors, and applies statistical analysis and machine-learning classification. Its LAPCG strategy models adjacent codon interactions with linear complexity, while the pipeline also supports MSCG for multi-scale context modeling.

  • A. Overview: GenEx converts each SARS-CoV-2 nucleotide sequence into a codon graph, extracts structural and spectral descriptors, and uses them for variant-level analysis and classification.The pipeline uses LAPCG for fast local interactions and MSCG for multi-scale codon context modeling.
  • B. End-to-end Pipeline: The end-to-end workflow converts sequences into codons, builds a weighted LAPCG or MSCG graph, computes graph features, runs ANOVA, and benchmarks machine-learning models.Computed features include topological, path-based, centrality, and spectral descriptors.
  • C. Codon Segmentation: Codons are formed from non-overlapping fixed-frame nucleotide triplets, producing C = (c1, c2, . . . , c⌊L/3⌋).Each codon is defined as ci = (n3i−2, n3i−1, n3i).
  • C. Codon Segmentation: Ambiguous nucleotide symbols such as N are removed before graph construction.This preprocessing step occurs after codon segmentation and before graph generation.
  • D. LAPCG: Linear-time Adjacency PMI Codon Graph: LAPCG models only adjacent codon pairs (ci, ci+1), providing linear complexity in sequence length for large-scale data.The algorithm initializes codon-frequency and adjacent-pair maps, counts codons and unordered neighboring pairs, and creates vertices from unique codons.
  • D. LAPCG: Linear-time Adjacency PMI Codon Graph: LAPCG adds an edge between an observed codon pair only when PMI(u, v) > 0, assigning the edge the corresponding PMI weight.The resulting graph is undirected and weighted.
  • D. LAPCG: Linear-time Adjacency PMI Codon Graph: MSCG extends graph construction across multiple sequence scales by aggregating positive NPMI pair weights with scale-specific coefficients αs.For each scale s, the algorithm observes pairs (ci, ci+s), computes NPMI, accumulates αs · NPMI(u, v), and returns the weighted graph.

E. MSCG: Multi-Scale Codon Co-occurrence Graph

MSCG represents codon sequences as weighted undirected co-occurrence graphs by extending local adjacency across multiple codon distances. In the GenEx pipeline, MSCG uses normalized PMI across scales 1, 2, and 3 with decaying weights.

  • Multi-scale co-occurrence: MSCG captures codon co-occurrence across multiple distances, extending beyond local adjacency.The method models co-occurrence at multiple codon-distance scales rather than only immediate neighbors.
  • Multi-scale co-occurrence: The implementation uses scales s ∈{1, 2, 3}, decay weights (1.0, 0.5, 0.25), and normalized PMI.These settings define the multi-scale weighting and association measure used for MSCG construction.
  • GenEx framework: GenEx preprocesses sequences through quality filtering, codon segmentation, and alignment before constructing MSCG and LAPCG weighted undirected graphs.The framework begins with genome acquisition from NCBI GenBank and then derives graphs for downstream feature extraction.

F. Feature Extraction and Evaluation · V. RESULTS · A. Model Benchmarking

GenEx extracted structural and spectral graph features for significance testing, feature-importance analysis, and machine-learning benchmarking. In model benchmarking, MSCG achieved the strongest overall performance among baseline PMI, LAPCG, and MSCG.

  • F. Feature Extraction and Evaluation: Each graph yielded structural and spectral features spanning topology, centrality, energy, singular-spectrum components, flow, and matching.The extracted features included node and edge counts, density, diameter, radius, average shortest path length, Wiener index, transitivity, clustering, centrality scores, graph energy, top singular-spectrum components, max-flow, and matching number.
  • F. Feature Extraction and Evaluation: The extracted graph features supported ANOVA-based inter-variant significance analysis.
  • F. Feature Extraction and Evaluation: The pipeline also applied feature-importance analysis to the extracted graph features.
  • F. Feature Extraction and Evaluation: Model benchmarking evaluated performance across multiple machine-learning families.
  • A. Model Benchmarking: Table II compared the best-performing models for baseline PMI, LAPCG, and MSCG.
  • A. Model Benchmarking: MSCG achieved the strongest overall performance in the benchmark.

B. Computational Efficiency of Graph Construction … F. Cross-Variant Comparative Trend

GenEx combines efficient graph construction with strong variant-classification performance and statistically informative graph features. Its cross-variant profiles preserve shared structure while exposing variant-specific signatures, particularly for Omicron.

  • B. Computational Efficiency of Graph Construction: 144.6 s: MSCG completed the full pipeline fastest, delivering a 1.88× speedup over PMI, while LAPCG required 196.2 s and achieved a 1.39× speedup.MSCG’s efficiency came from single-pass NPMI computation and accumulated edge weighting; LAPCG operates in strict O(n) time.
  • B. Computational Efficiency of Graph Construction: Under 1 s: MSCG processed each genome on average, including graph construction, feature extraction, and ML classification, using a single non-parallelized CPU core.The measurement used the full SARS-CoV-2 genome sequence dataset.
  • C. Comparison with Gene Detection and Variant Classification Methods: 98.75% accuracy: GenEx MSCG achieved the highest reported accuracy among compared methods for its variant-classification task while improving efficiency over standard PMI construction.Gene annotation tools solve a structurally different gene-coordinate prediction problem and are not directly comparable by accuracy.
  • D. Feature Importance and Statistical Significance: Radius, average shortest path length, top eigenvalue, and number of edges showed strong between-variant separation, with radius reaching F = 69.74, p = 3.14 × 10−36.The highest-ranked features also included second eigenvalue and Wiener index.
  • E. Variant Structural Profiles: Figure 2 presents all four variant structural profiles in a compact 2×2 panel, enabling visual comparison without interrupting the text flow.
  • F. Cross-Variant Comparative Trend: Codon graph features evolved differently across variants while preserving an overall shared structural backbone, indicating conserved genome organization alongside variant-specific signatures.The parallel-coordinate view represents each genome sample as a polyline and uses color to encode variant class.
  • F. Cross-Variant Comparative Trend: Omicron samples sharply diverged in matching number and stable rank, whereas top eigenvalue and graph energy remained highly conserved across all four clades.

G. Interpretation · H. Structural Profiles of Individual Variants · 1) Beta (B.1.351):

GenEx represents four SARS-CoV-2 variants as genomic graphs with 22 computed properties, revealing distinct graph fingerprints. Beta combines a stable dense core with the dataset’s most extreme graph-level outliers.

  • G. Interpretation: Genomic graphs for Beta, Gamma, Delta, and Omicron were evaluated using 22 graphical properties and interpreted through variant profiles and structural comparisons.The analysis separates individual structural profiles from comparative similarities and differences.
  • H. Structural Profiles of Individual Variants: Each variant exhibits a distinct genomic graph fingerprint formed by conserved baseline properties and variant-specific outlier behavior.This fingerprint combines shared structural tendencies with deviations specific to individual variants.
  • 1) Beta (B.1.351):: Beta has a structurally stable median profile but the most extreme individual outliers across the dataset, making it the most internally volatile variant graph.Its stability describes the central profile, while volatility appears in exceptional sequences.
  • 1) Beta (B.1.351):: ∼0.97 median graph density indicates Beta networks are densely interconnected and tend to conserve the viral backbone.Transitivity and average clustering coefficients are about 0.96–0.97 across most Beta samples, indicating tightly triangulated local genomic neighborhoods.
  • 1) Beta (B.1.351):: ∼45,000 Wiener Index in at least one Beta sequence is roughly three times the typical ∼15,000, indicating elongated internal pathways associated with deletions or rearrangements.The extreme value reflects greater distances between genomic units than in typical samples from other variants.
  • 1) Beta (B.1.351):: Gamma displays the broadest intra-clade structural diversity, distributing variability across multiple graph properties and producing the dataset’s most heterogeneous genome-graph collection.Unlike Beta, whose outliers occur in selected features, Gamma’s variability spans several properties simultaneously.
  • 1) Beta (B.1.351):: ∼110 nodes make Gamma the highest-node outlier, versus a 65–70 median range for other variants; its largest connected component reaches ∼115 nodes.Gamma generally forms a single unfragmented interconnected giant graph rather than isolated subgraphs.

2) Gamma (P.1): · 3) Delta (B.1.617.2): · 4) Omicron (B.1.1.529):

Gamma exhibits highly variable, bridge-dominated, energy-rich graph structures, whereas Delta is compact, cohesive, and structurally conserved. Omicron shows the greatest modularity and dimensional complexity, with markedly elevated matching number, stable rank, and Frobenius norm.

  • 2) Gamma (P.1):: Gamma graph outliers reach physical elongation of 11.5 and betweenness centrality of ∼0.006, indicating bridge-like sites that connect distant genomic regions.These features imply that specific genomic sites control information flow between distant regions.
  • 2) Gamma (P.1):: Gamma graph energy reaches ∼175 versus a typical 115–120 range, while transitivity falls to ∼0.84 in outliers.The passage associates these values with altered eigenvalue distributions, greater structural complexity, and less-triangulated local neighborhoods.
  • 2) Gamma (P.1):: Gamma spans elongated, bridge-dominated, and energy-rich organizational forms, reflecting structural variation associated with insertion events in the P.1 lineage.The passage states that these insertion events create functional differences requiring further investigation.
  • 3) Delta (B.1.617.2):: Delta produces structurally consistent, compact, and well-clustered genome graphs, with tight distributions, low intra-clade variance, and few extreme outliers.Its networks typically contain 65-70 nodes and approximately 2,000 edges, while the Wiener index is close to 15,000.
  • 3) Delta (B.1.617.2):: Delta has no extreme condition-number or stable-rank outliers and maintains a matching number of ∼3, indicating cohesive, non-degenerate graph structure without independent modular components.The passage characterizes Delta’s adjacency matrices as consistently well-conditioned and structurally non-redundant.
  • 4) Omicron (B.1.1.529):: Omicron presents the dataset’s most structurally complex and modular genomic graph profile, with matching number reaching ∼55 versus ∼3 for other variants.The matching number is described as indicating structurally non-overlapping independent motifs and separate mutational events.
  • 4) Omicron (B.1.1.529):: Omicron stable rank reaches ∼1.75 versus 1.3–1.4 in other variants, indicating higher effective dimensionality and more complex graph spaces.The passage states that Omicron structures are not merely scale-ups of previous variants.
  • 4) Omicron (B.1.1.529):: Omicron also shows increased Frobenius norm, reaching ∼12.5 in some graphs and further evidencing structural diversification.The supplied passage reports the Omicron value but truncates the comparison that follows it.

I. Structural Similarities and Dissimilarities Across Variants … 3) Variant-Specific Structural Divergence:

Across Beta, Gamma, Delta, and Omicron, genomic graphs retain a highly conserved global small-world architecture while forming two structurally distinct clusters. Variant-specific divergence differs in mechanism, ranging from Beta’s heterogeneous outliers and Gamma’s coherent reorganization to Delta’s minimal departure and Omicron’s systematic transition.

  • I. Structural Similarities and Dissimilarities Across Variants: The comparison examines conserved global structure, hierarchical clustering, variant-specific divergence, and variant-specific spectral characteristics.
  • 1) Conserved Global Topology Across Variants:: Beta, Gamma, Delta, and Omicron share a highly consistent global small-world topology despite evolutionary pressure.Their graph distributions show near-identical median values across fundamental graph-theoretic features.
  • 2) Hierarchical Clustering:: Beta and Delta cluster at distance ∼5.7, while Gamma and Omicron cluster at distance ∼7.3 in hierarchical analysis.
  • 2) Hierarchical Clustering:: The Beta–Delta pairing indicates structural convergence despite independent origins, whereas Gamma–Omicron share structural similarity despite deeply divergent lineages.The reported grouping may reflect convergence, common mutational patterns, or similar selective forces.
  • 2) Hierarchical Clustering:: The Beta–Delta and Gamma–Omicron super-clusters merge at ∼9.6, indicating a substantial structural discontinuity between the groups.
  • 3) Variant-Specific Structural Divergence:: Beta shows intra-clade heterogeneity through independent extreme outliers in the Wiener index, condition number, and closeness centrality.The outliers do not consistently co-occur within the same samples, indicating multiple distinct disruption mechanisms.
  • 3) Variant-Specific Structural Divergence:: Gamma exhibits coherent structural reorganization, with larger diameter, higher betweenness centrality, greater graph energy, and lower transitivity occurring together.These changes may stem from the inclusion of genomic material, which elongates graphs, creates bridge positions, and disrupts local triangular structures.
  • 3) Variant-Specific Structural Divergence:: Delta’s divergence is minimal, consisting mainly of an extreme low-density outlier considered likely artifactual, while Omicron shows a systematic elevated matching number and stable rank.Delta remains closest to the cross-variant consensus; Omicron’s distribution-wide pattern reflects a genuine structural transition.

4) Spectral and Algebraic Divergence: · VI. CONCLUSION

GenEx combines codon-interaction graph benchmarking with spectral and algebraic analysis to distinguish conserved structural backbones from variant-specific graph fingerprints. Its LAPCG and MSCG algorithms provide complementary graph representations, with MSCG achieving 98.75% accuracy and LAPCG offering linear-time O(n) extraction.

  • 4) Spectral and Algebraic Divergence:: 4 × 10^10: Beta’s near-singular adjacency matrix has an outlying condition number, indicating brittle algebraic sensitivity to perturbations.Delta graphs are consistently well-conditioned, whereas Omicron graphs are described as structurally robust.
  • 4) Spectral and Algebraic Divergence:: 10.5: Frobenius norms remain relatively constant across variants, while Omicron has outliers reaching 12.5.The Omicron outliers indicate elevated overall adjacency-matrix magnitude.
  • 4) Spectral and Algebraic Divergence:: GenEx clustering differs from sequence-only phylogeny, showing that graph-theoretic analysis captures an additional, complementary axis of viral evolution.The paper summarizes this evolution as conserved structural backbones alongside variant-specific algebraic fingerprints.
  • VI. CONCLUSION: The unified pipeline analyzes Beta, Delta, Gamma, and Omicron at nucleotide and codon levels through graphical analysis of codon interaction networks.It introduces LAPCG and MSCG to address limitations of linear sequence analysis.
  • VI. CONCLUSION: 98.75%: MSCG using Normalized PMI and positional node encoding maintains this accuracy, establishing a robust alignment-free framework.LAPCG uses direct-neighbor approximation for graph extraction and feature computation with linear-time complexity O(n), whereas MSCG models multi-scale inter-context dependencies.
Loading 2608.18238v1…