# Effective and scalable clustering of SARS-CoV-2 sequences

arXiv: https://arxiv.org/abs/2108.08143 · HTML: https://mlsanity.com/paper/2108.08143/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 49 references that are in the map.
- First posted on arXiv 18 Aug 2021.

## Builds on (most cited first, 15 of 15)

- [A k-mer Based Approach for SARS-CoV-2 Variant Identification](https://mlsanity.com/paper/2108.03465/) (2021)
- [Efficient Approximation Algorithms for String Kernel Based Sequence Classification](https://mlsanity.com/paper/1712.04264/) (2017)
- [Predicting Attributes of Nodes Using Network Structure](https://mlsanity.com/paper/1912.12264/) (2019)
- [Detecting DDoS Attack on SDN Due to Vulnerabilities in OpenFlow](https://mlsanity.com/paper/1912.12221/) (2019)
- [Effect of Analysis Window and Feature Selection on Classification of Hand Movements Using EMG Signal](https://mlsanity.com/paper/2002.00461/) (2020)
- [Short-Term Load Forecasting Using AMI Data](https://mlsanity.com/paper/1912.12479/) (2019)
- [Combinatorial Trace Method for Network Immunization](https://mlsanity.com/paper/1912.12070/) (2019)
- [A Multi-cascaded Model with Data Augmentation for Enhanced Paraphrase Detection in Short Texts](https://mlsanity.com/paper/1912.12068/) (2019)
- [Language Independent Sentiment Analysis](https://mlsanity.com/paper/1912.11973/) (2019)
- [Spectral Methods for Immunization of Large Networks](https://mlsanity.com/paper/1711.00791/) (2017)
- [Scalable Approximation Algorithm for Network Immunization](https://mlsanity.com/paper/1711.00784/) (2017)
- [A Multi-cascaded Deep Model for Bilingual SMS Classification](https://mlsanity.com/paper/1911.13066/) (2019)
- [Estimating Descriptors for Large Graphs](https://mlsanity.com/paper/2001.10301/) (2020)
- [Cache Replacement Algorithm](https://mlsanity.com/paper/2107.14646/) (2021)
- [Fair Allocation Based Soft Load Shedding](https://mlsanity.com/paper/2002.00451/) (2020)

## Built on by (most cited first, 15 of 15)

- [Spike2Vec: An Efficient and Scalable Embedding Approach for COVID-19 Spike Sequences](https://mlsanity.com/paper/2109.05019/) (2021)
- [PWM2Vec: An Efficient Embedding Approach for Viral Host Specification from Coronavirus Spike Sequences](https://mlsanity.com/paper/2201.02273/) (2022)
- [Efficient Approximate Kernel Based Spike Sequence Classification](https://mlsanity.com/paper/2209.04952/) (2022)
- [Robust Representation and Efficient Feature Selection Allows for Effective Clustering of SARS-CoV-2 Variants](https://mlsanity.com/paper/2110.09622/) (2021)
- [Reads2Vec: Efficient Embedding of Raw High-Throughput Sequencing Reads Data](https://mlsanity.com/paper/2211.08267/) (2022)
- [Efficient Analysis of COVID-19 Clinical Data using Machine Learning Models](https://mlsanity.com/paper/2110.09606/) (2021)
- [Benchmarking Machine Learning Robustness in Covid-19 Genome Sequence Classification](https://mlsanity.com/paper/2207.08898/) (2022)
- [Informative Initialization and Kernel Selection Improves t-SNE for Biological Sequences](https://mlsanity.com/paper/2211.09263/) (2022)
- [Efficient Classification of SARS-CoV-2 Spike Sequences Using Federated Learning](https://mlsanity.com/paper/2302.08688/) (2023)
- [Evaluating COVID-19 Sequence Data Using Nearest-Neighbors Based Network Model](https://mlsanity.com/paper/2211.10546/) (2022)
- [Characterizing SARS-CoV-2 Spike Sequences Based on Geographical Location](https://mlsanity.com/paper/2110.00809/) (2021)
- [Locally Weighted Mean Phase Angle (LWMPA) Based Tone Mapping Quality Index (TMQI-3)](https://mlsanity.com/paper/2109.08774/) (2021)
- [Information We Can Extract About a User From 'One Minute Mobile Application Usage'](https://mlsanity.com/paper/2207.13222/) (2022)
- [ViralVectors: Compact and Scalable Alignment-free Virome Feature Generation](https://mlsanity.com/paper/2304.02891/) (2023)
- [A Misclassification Network-Based Method for Comparative Genomic Analysis](https://mlsanity.com/paper/2412.07051/) (2024)

## Abstract (arXiv)

SARS-CoV-2, like any other virus, continues to mutate as it spreads, according to an evolutionary process. Unlike any other virus, the number of currently available sequences of SARS-CoV-2 in public databases such as GISAID is already several million. This amount of data has the potential to uncover the evolutionary dynamics of a virus like never before. However, a million is already several orders of magnitude beyond what can be processed by the traditional methods designed to reconstruct a virus's evolutionary history, such as those that build a phylogenetic tree. Hence, new and scalable methods will need to be devised in order to make use of the ever increasing number of viral sequences being collected. Since identifying variants is an important part of understanding the evolution of a virus, in this paper, we propose an approach based on clustering sequences to identify the current major SARS-CoV-2 variants. Using a k-mer based feature vector generation and efficient feature selection methods, our approach is effective in identifying variants, as well as being efficient and scalable to millions of sequences. Such a clustering method allows us to show the relative proportion of each variant over time, giving the rate of spread of each variant in different locations -- something which is important for vaccine development and distribution. We also compute the importance of each amino acid position of the spike protein in identifying a given variant in terms of information gain. Positions of high variant-specific importance tend to agree with those reported by the USA's Centers for Disease Control and Prevention (CDC), further demonstrating our approach.