Variant evolution graph: Can we infer how SARS-CoV-2 variants are evolving?

Abstract

The SARS-CoV-2 virus has undergone extensive mutations over time, resulting in considerable genetic diversity among circulating strains. This diversity directly affects important viral characteristics, such as transmissibility and disease severity. During a viral outbreak, the rapid mutation rate produces a large cloud of variants, referred to as a viral quasispecies. However, many variants are lost due to the bottleneck of transmission and survival. Advances in next-generation sequencing have enabled continuous and cost-effective monitoring of viral genomes, but constructing reliable phylogenetic trees from the vast collection of sequences in GISAID (the Global Initiative on Sharing All Influenza Data) presents significant challenges. We introduce a novel graph-based framework inspired by quasispecies theory, the Variant Evolution Graph (VEG), to model viral evolution. Unlike traditional phylogenetic trees, VEG accommodates multiple ancestors for each variant and maps all possible evolutionary pathways. The strongly connected subgraphs in the VEG reveal critical evolutionary patterns, including recombination events, mutation hotspots, and intra-host viral evolution, providing deeper insights into viral adaptation and spread. We also derive the Disease Transmission Network (DTN) from the VEG, which supports the inference of transmission pathways and super-spreaders among hosts. We have applied our method to genomic data sets from five arbitrarily selected countries - Somalia, Bhutan, Hungary, Iran, and Nepal. Our study compares three methods for computing mutational distances to build the VEG, sourmash, pyani, and edit distance, with the phylogenetic approach using Maximum Likelihood (ML). Among these, ML is the most computationally intensive, requiring multiple sequence alignment and probabilistic inference, making it the slowest. In contrast, sourmash is the fastest, followed by the edit distance approach, while pyani takes more time due to its BLAST-based computations. This comparison highlights the computational efficiency of VEG, making it a scalable alternative for analyzing large viral data sets.

Fig 1. Pipeline for generating edit-distance matrix using pairwise edit distances between the variant genomes.

Fig 2. The whole pipeline of building VEG.

The edit distance computation in this pipeline is separately shown in Fig 1.

Fig 3. A sample set of six genomes.

(a) The set of six variant genomes, A, B, C, D, E, and F, and their corresponding collection dates. (b) The workflow of Algorithm 1 on the distance matrix, M.

Fig 4. The workflow of Algorithm 2 with the example in

Fig 3.

Fig 5. Count of genomes filtered based on the percentage of Ns, τ, in the genomes.

The x-axis shows the threshold values and the y-axis shows the count of filtered genomes. The plots are of (a) Somalia, (b) Bhutan, (c) Iran, and (d) Nepal data sets.

Fig 6. Average count of Ns in the genome sequences vs the coding regions in five data sets.

Fig 7. (a) VEGS (b) VEGE, and (c) VEGP of Bhutan data set (graph viewed using Cytoscape 3.10.2).

Fig 8. A maximum likelihood phylogenetic tree of the Bhutan data set.

Fig 9. Venn diagrams showing parent-child relationships among the VEGs derived from sourmash, pyani, and edit distance.

(a) Bhutan, (b) Hungary, (c) Nepal, and (d) Iran data sets.

Fig 10. The DTN is inferred from the VEG of the Bhutan data set (edit distance).

Here, the nodes are the hosts, and the edges represent the direction and day differences of the inferred transmissions.