Motif Analysis in k-mer Networks: An Approach towards Understanding SARS-CoV-2 Geographical Shifts

Sourav Biswas, Suparna Saha, Sanghamitra Bandyopadhyay, Malay BhattacharyyabioRxiv 2020 · DOI

TL;DR

This paper introduces a novel approach using k-mer network motif analysis to predict the geographical origin of SARS-CoV-2 samples. By analyzing patterns in viral genomic sequences, the researchers demonstrate high accuracy in distinguishing between countries and even continents, suggesting that viral evolution is influenced by geographical factors.

What Problem Does This Paper Address?

The COVID-19 pandemic, caused by SARS-CoV-2, has spread globally, leading to a massive influx of viral genomic sequence data. While this data offers insights into the virus's evolution, understanding how these genomic changes correlate with geographical spread and origin has been a significant challenge. Existing methods often focus on sequence similarity or phylogenetic trees, but there's a need for approaches that can capture more subtle, localized patterns within the viral genome that might reflect geographical influences. This paper aims to bridge this gap by exploring whether specific genomic "motifs" within SARS-CoV-2 sequences can serve as a fingerprint for their geographical origin.

Methods

The core of this research lies in two main analytical techniques:

  • k-mer Distribution Analysis: This method involves breaking down viral genomic sequences into overlapping subsequences of a fixed length, known as k-mers. By analyzing the frequency of these k-mers, researchers can capture patterns in the viral genome. The paper uses k-mers of sizes 1, 2, and 3, resulting in 84 features after normalization.
  • Network Motif Analysis: This is the more novel aspect. The researchers construct "k-mer networks" where each node represents a SARS-CoV-2 sample, and edges represent similarity based on k-mer distributions. They then use a tool called FANMOD to identify "network motifs" – recurring subgraph patterns that appear more frequently than expected in random networks. These motifs are hypothesized to represent topological features of the sequence similarity network that are characteristic of specific geographical locations.

To handle the imbalanced nature of the dataset (with a disproportionately large number of samples from the USA), the researchers employed random stratified under-sampling to balance the data for classification tasks. They also used standard classification algorithms like kNN, Random Forest, and Naive Bayes, evaluating their performance using metrics like accuracy, precision, recall, F1 score, and AUC.

Datasets

The study utilized SARS-CoV-2 genomic sequences collected from the NCBI Virus portal. The primary dataset comprised over 8,000 sequences, which were then pre-processed to yield a dataset of 5,817 sequences with normalized k-mer values. For country-level classification, the top six countries with at least 80 samples were selected: Australia, China, India, Greece, France, and USA. For continent-level classification, data from all available countries (excluding Africa due to low sample count) was used. The study also analyzed temporal patterns by selecting samples from March and April 2020 for specific country classifications.

Key Insights and Ideas

  • Genomic Signatures of Geography: The most significant insight is that SARS-CoV-2 genomic sequences exhibit distinct patterns that can reliably predict their geographical origin. This suggests that environmental factors or transmission dynamics in different regions influence viral evolution.
  • k-mer Networks as Fingerprints: The study highlights that analyzing the topological structure of k-mer similarity networks, specifically through network motifs, provides a powerful way to capture these geographical signatures. These motifs act as a form of "genomic fingerprint" for the virus.
  • Motifs Reflect Evolutionary Divergence: The identified network motifs, particularly those with high degree or betweenness centrality, indicate a divergence in viral genomes across different regions, rather than convergence towards a single pattern. This supports the idea of geographically influenced evolutionary pathways.
  • Under-sampling is Crucial: The research underscores the necessity of data balancing techniques like under-sampling to achieve accurate classification, especially when dealing with highly imbalanced datasets like the SARS-CoV-2 genomic data.

Key Results

  • High Classification Accuracy: With proper under-sampling, k-mer distribution analysis achieved over 90% accuracy in predicting the geographical origin of SARS-CoV-2 samples at the country level.
  • Random Forest Dominance: The Random Forest classifier consistently outperformed other models (kNN, Naive Bayes) across various classification tasks (country, continent, and temporal) in terms of accuracy and other evaluation metrics.
  • Continent-Level Predictability: The approach also demonstrated success in classifying samples by continent, indicating broader geographical patterns in viral evolution.
  • Distinct Network Motifs: The study identified a range of network motifs (8-17 per country) in the k-mer networks, with some motifs being common across countries and others unique, further supporting geographical distinctiveness. For example, Greece showed a higher number of motifs (17) compared to other countries.
  • Hierarchical Clustering Reveals Groupings: Hierarchical clustering of motif z-scores revealed expected groupings (e.g., India and China together) and some surprising ones (e.g., USA and Greece), highlighting the complex interplay of factors influencing viral spread and evolution.

Limitations and Future Work

  • Data Imbalance: While under-sampling was employed, the inherent imbalance in available genomic data (especially from the USA) remains a challenge, and its impact on specific regional analyses might still be present.
  • Time Gaps in Data Publication: The paper acknowledges that different countries publish their sequence data with varying time lags after sample collection, making precise temporal classification challenging.
  • Limited Temporal Resolution: The study focused on classifying samples from March and April 2020. Future work could explore finer temporal resolutions and a wider range of time periods to better track evolutionary shifts.
  • Unknown Reasons for Similarities: The paper notes surprising similarities, such as between USA and Greece, and suggests that further investigation is needed to understand the underlying reasons for these patterns.
  • Genomic Fingerprinting Potential: The authors propose that this motif analysis approach could be developed into a "genomic fingerprinting" method for better understanding the virus's footprint and evolution. Future work could focus on refining this approach and applying it to other pathogens.

Summary updated

Abstract

Abstract With an increasing number of SARS-CoV-2 sequences available day by day, new genomic information is getting revealed to us. As SARS-CoV-2 sequences highlight wide changes across the samples, we aim to explore whether these changes reveal the geographical origin of the corresponding samples. The k -mer distributions, denoting normalized frequency counts of all possible combinations of nucleotide of size upto k , are often helpful to explore sequence level patterns. Given the SARS-CoV-2 sequences are highly imbalanced by its geographical origin (relatively with a higher number samples collected from the USA), we observe that with proper under-sampling k -mer distributions in the SARS-CoV-2 sequences predict its geographical origin with more than 90% accuracy. The experiments are performed on the samples collected from six countries with maximum number of sequences available till July 07, 2020. This comprises SARS-CoV-2 sequences from Australia, USA, China, India, Greece and France. Moreover, we demonstrate that the changes of genomic sequences characterize the continents as a whole. We also highlight that the network motifs present in the sequence similarity networks have a significant difference across the said countries. This, as a whole, is capable of predicting the geographical shift of SARS-CoV-2.
BibTeX
@misc{biswas2020motif,
  author = {Sourav Biswas and Suparna Saha and Sanghamitra Bandyopadhyay and Malay Bhattacharyya},
  title = {{Motif Analysis in k-mer Networks: An Approach towards Understanding SARS-CoV-2 Geographical Shifts}},
  year = {2020},
  doi = {10.1101/2020.10.04.325662},
  howpublished = {bioRxiv},
}
Figure