A Cross-Vertex Embedding Approach toward Understanding SARS-CoV-2 Variability

ABSTRACT

A graph consists of a set of nodes representing some objects and a set of edges representing the interactions between those objects. An edge can be weighted, unweighted, directed or undirected depending on the problem. Generally, a node represents an object associated with a single feature. For example, in the historical 'Königsberg Bridge' problem, a node represents a piece of land, and an edge is a connecting bridge between two pieces of lands. In a complex network, a node may represent much more than a singular concept. 'Graph Embedding' is an approach to map an object of a graph into a fixed-length vector that captures many key features represented by the graph. In this article, we introduce a novel concept called 'Cross-Vertex Embedding' which is the reverse of graph embedding;it is a way to associate feature vectors of objects as nodes in a graph or a network, and then use graph-theoretic approaches for solving the problem at hand. We have applied this method for analysing geographical variations of Sars-CoV-2 strains, by mapping the kmer distribution of a virus sample as nodes and their similarities as edges. It is a generic computational method which may have many applications beyond the analysis of sars-CoV-2 data. © 2020 IEEE.