UMAP-assisted K-means clustering of large-scale SARS-CoV-2 mutation datasets

Guo-Wei Wei, Yuta Hozumi, Rui Wang, Changchuan Yin, Guo-Wei Wei 0001Computers in Biology and Medicine 2021 · DOI

TL;DR

This paper tackles the challenge of analyzing the rapidly growing number of SARS-CoV-2 genome sequences by proposing a UMAP-assisted K-means clustering approach. They demonstrate that UMAP significantly improves clustering accuracy and visualization for large, high-dimensional genomic datasets, offering a more efficient and reliable method for understanding viral evolution and transmission.

What Problem Does This Paper Address?

The COVID-19 pandemic has led to an unprecedented surge in SARS-CoV-2 genome sequencing. Analyzing this massive and ever-increasing dataset for phylogenetic insights, mutation patterns, and transmission pathways is a significant computational challenge. Traditional phylogenetic methods struggle with scale, while standard K-means clustering can be computationally expensive and perform poorly on high-dimensional data, especially when using metrics like Jaccard distance, which can result in very large feature spaces. The authors aim to find an efficient and accurate dimensionality reduction technique that can be effectively combined with K-means clustering to handle these large-scale SARS-CoV-2 datasets.

Methods

The core of this work involves comparing three popular dimensionality reduction techniques – Principal Component Analysis (PCA), t-distributed Stochastic Neighbor Embedding (t-SNE), and Uniform Manifold Approximation and Projection (UMAP) – in conjunction with K-means clustering.

  • Dimensionality Reduction:
    • PCA: A linear method that finds directions of maximum variance.
  • t-SNE: A non-linear method that preserves local structures by modeling pairwise similarities.
  • UMAP: A non-linear manifold learning technique that aims to preserve both local and global data structure, often with better performance and scalability than t-SNE.
  • Clustering: K-means clustering is used as the downstream task. The authors adapt supervised classification problems by setting the number of clusters equal to the number of known classes to evaluate clustering accuracy.
  • Feature Representation: Two primary feature representations are used for SARS-CoV-2 data:
  • SNP position-based features: A binary representation indicating the presence or absence of a mutation at specific genomic positions.
  • Jaccard-based representation: A distance matrix derived from the Jaccard distance between sets of mutations in each genome, reflecting topological differences.

Datasets

The authors validate their approach using four benchmark datasets and then apply it to SARS-CoV-2 data:

  • Benchmark Datasets:
    • Coil 20: A dataset of 1440 grayscale images of 20 objects, each with 72 orientations.
  • Facebook Network: A page-page webgraph of verified Facebook sites.
  • MNIST: A dataset of handwritten digits.
  • Jaccard distanced-based MNIST: The MNIST dataset converted into a Jaccard distance-based representation to simulate positional mutation data.
  • SARS-CoV-2 Datasets:
    • World SARS-CoV-2 mutation dataset: Collected up to October 30, 2020, containing 89,627 sequences and 23,763 unique SNPs.
  • United States SARS-CoV-2 mutation dataset: A subset of the world data focusing on the US, with 10,279 unique mutations and 22,390 samples.
  • Previous SARS-CoV-2 datasets: Used for comparison and visualization.

Key Insights and Ideas

  • UMAP's Superiority for Large-Scale Genomic Data: UMAP consistently outperformed PCA and t-SNE in terms of clustering accuracy and reliability, especially for large, high-dimensional datasets like those derived from genomic sequences.
  • Jaccard Distance Benefits from UMAP: The Jaccard distance representation, which can lead to very high-dimensional feature spaces, showed significant improvements in clustering accuracy when combined with UMAP. This suggests UMAP is particularly well-suited for handling the sparsity and dimensionality of such biological data.
  • Improved K-means Performance: Dimension reduction, particularly with UMAP, significantly boosted the performance of K-means clustering, leading to higher accuracy and more meaningful cluster separation compared to using K-means directly on the raw, high-dimensional data.
  • Visualization Power: UMAP's ability to generate clear and elegant 2D visualizations of complex, high-dimensional data is crucial for understanding the relationships and structures within SARS-CoV-2 mutation patterns.
  • Stability and Reliability: UMAP demonstrated stable performance across various reduction ratios, making it a more robust choice than t-SNE, which can be sensitive to hyperparameter settings.

Key Results

  • Accuracy: UMAP-assisted K-means clustering achieved higher accuracy across multiple benchmark datasets and the SARS-CoV-2 datasets compared to PCA and t-SNE assisted methods. For instance, on the Jaccard distanced-based MNIST dataset, UMAP-assisted K-means achieved the highest accuracy (0.798 at a reduced dimension of 3).
  • Efficiency: While PCA was generally the fastest, UMAP showed better scalability with increasing sample sizes, making it more suitable for the large SARS-CoV-2 datasets. t-SNE was often the slowest, with some computations being prohibitively long.
  • SARS-CoV-2 Clustering: Applying UMAP-assisted K-means to the world SARS-CoV-2 dataset revealed 6 distinct clusters, and similar clustering was observed for the US-specific dataset. These clusters represent different evolutionary lineages or subtypes of the virus.
  • Visualization: 2D UMAP visualizations of the SARS-CoV-2 data provided clear and interpretable cluster structures, aiding in the understanding of viral evolution and geographic distribution.

Limitations and Future Work

  • UMAP's Data Size Requirement: The authors note that UMAP might require a suitable data size to perform optimally, suggesting it might not be as effective on very small datasets (e.g., Coil 20 with limited samples per class).
  • Automatic kmin Determination: For UMAP, there is currently no automatic method to determine the optimal number of neighbors (kmin), which can affect performance on non-uniform data distributions.
  • Computational Cost of t-SNE: t-SNE's computational cost can be extremely high, making it impractical for very large datasets or high-dimensional reductions.
  • Future Work: The authors suggest that the Jaccard distance representation, combined with UMAP, provides a strong foundation for future analyses of SARS-CoV-2 mutation datasets, potentially leading to new insights into transmission dynamics and the development of effective countermeasures. They also highlight the potential for using UMAP-assisted K-means to analyze previous SARS-CoV-2 datasets, offering a new perspective.

Summary updated

BibTeX
@article{wei2021umap,
  author = {Guo-Wei Wei and Yuta Hozumi and Rui Wang and Changchuan Yin and Guo-Wei Wei},
  title = {{UMAP-assisted K-means clustering of large-scale SARS-CoV-2 mutation datasets}},
  journal = {Computers in Biology and Medicine},
  year = {2021},
  doi = {10.1016/j.compbiomed.2021.104264},
}
Figure