Clustering Sparse Data With Feature Correlation With Application to Discover Subtypes in Cancer

Jipeng Qiang, Wei Ding, Marieke L. Kuijjer, John Quackenbush, Ping ChenIEEE Access 2020 · DOI

TL;DR

This paper introduces a novel "Feature Alignment Similarity" (FAS) metric that leverages gene interaction networks to cluster sparse, high-dimensional cancer mutation data. By projecting samples into a feature network, FAS can identify similarities even when patients share no common mutations, outperforming existing methods in cancer subtype discovery and revealing biologically significant subtypes missed by other algorithms.

What Problem Does This Paper Address?

Clustering high-dimensional, sparse data is a significant challenge, particularly in fields like genomics. Cancer mutation data exemplifies this problem: it's high-dimensional (thousands of genes) and sparse (most patients have mutations in only a small fraction of genes). Traditional similarity metrics struggle because they rely on shared features, which are rare in this type of data. This sparsity makes it difficult to accurately group patients into distinct subtypes, hindering our understanding of cancer biology and the development of targeted therapies. Existing methods often fail to capture the underlying biological relationships between mutated genes, leading to suboptimal subtype discovery.

Methods

The core contribution is a new similarity metric called Feature Alignment Similarity (FAS). Unlike traditional methods that directly compare samples, FAS first projects each sample (represented as a set of mutated genes) onto a feature interaction network (specifically, a gene interaction network in their application). This network captures the relationships between features (genes).

The FAS metric then calculates similarity by:

  1. Feature Alignment: It finds an optimal alignment between the features of two samples within the gene interaction network. This alignment determines how much each mutated gene in one sample "allocates" its weight to genes in the other sample.
  2. Network-based Similarity: The similarity between two genes is not just based on whether they are mutated together but also on their proximity and connectivity within the gene interaction network. Genes in similar network regions are considered more similar.
  3. Maximizing Similarity: The FAS metric aims to maximize the overall similarity between two samples by finding the best possible alignment of their features, even if they don't share any mutated genes directly. This is framed as an optimization problem.

To make this computationally feasible, they also propose a fast similarity computation method that uses relaxed optimization to provide an upper bound on the FAS similarity, significantly reducing computation time. The overall approach is termed Network-based Affinity Propagation (NetAP), where FAS is used as the similarity measure within the Affinity Propagation clustering algorithm.

Datasets

The authors evaluated their method on:

  • Synthetic Data: Generated to mimic the characteristics of cancer mutation data, specifically incorporating known network structures and varying driver mutation frequencies and network module sizes. This allowed for controlled testing of the algorithm's accuracy.
  • Real-World Data:
    • Uterine Cancer Dataset: Collected from The Cancer Genome Atlas (TCGA), containing somatic mutation data for 248 patients across 17,968 genes.
  • Lung Cancer Dataset: Also collected from TCGA, with somatic mutation data for 304 patients across 15,967 genes.

They also utilized three publicly available gene interaction networks:

  • PathwayCommons: Focuses on physical protein-protein interactions.
  • STRING: Integrates protein-protein interactions from expression data and medical literature.
  • HumanNet: Built using a modified Bayesian integration from multiple organisms.

Key Insights and Ideas

  • Leveraging Gene Networks is Crucial for Sparse Data: The paper strongly demonstrates that incorporating prior knowledge of gene interactions is essential for effectively clustering sparse mutation data. Without this, traditional methods perform poorly.
  • Similarity Beyond Direct Overlap: FAS's ability to find similarity between samples even without shared mutations is a key breakthrough. This aligns with biological reality where different mutations can affect the same pathway or network module.
  • NetAP Outperforms Baselines: The proposed NetAP method, using FAS, consistently shows superior performance in identifying cancer subtypes compared to established algorithms like NMF, LDA, and AP, especially on sparse mutation data.
  • PathwayCommons Network is Promising: The study found that the PathwayCommons gene network generally led to better NetAP performance for subtype discovery, suggesting its suitability for this task.

Key Results

  • Synthetic Data: NetAP accurately recovered subtypes across a wide range of driver mutation frequencies and network module sizes, outperforming AP, NMF, and LDA, particularly for larger network modules.
  • Real-World Data (Uterine Cancer): NetAP achieved significantly better results (e.g., ~30% improvement in AR metric over NBS) compared to NBS, AP, NMF, and LDA. It also identified subtypes that were more closely associated with histological classifications than those found by other algorithms.
  • Real-World Data (Lung Cancer): NetAP performed better than other methods across most metrics (AR, RI, Chi-square, P-value), with performance similar to NBS.
  • Comparison with Other Clustering Algorithms: When compared against algorithms like SparseNMF, Kmeans, PAM, and Hierarchical clustering, NetAP significantly outperformed them on uterine cancer data, highlighting the limitations of non-network-based methods for this data type.
  • Biological Significance: NetAP was able to identify subtypes that correlated better with observed clinical data (histological types) than other methods, suggesting it uncovers more biologically meaningful groupings.

Limitations and Future Work

  • Computational Complexity: While FAS is a novel approach, solving the exact FAS optimization problem for many samples can be computationally prohibitive. The paper addresses this with a faster, relaxed optimization method, but the exact solution's complexity remains a consideration.
  • Gene Network Choice: The performance of NetAP can vary depending on the gene interaction network used, as observed with PathwayCommons, STRING, and HumanNet. Identifying the optimal network for a given dataset is an ongoing area.
  • Future Work: The authors plan to integrate multiple layers of information beyond somatic mutations, such as copy number variations (CNVs) and transcriptome data, to further enhance subtype identification.

Summary updated

Abstract

In this paper, given data with high-dimensional features, we study this problem of how to calculate the similarity between two samples by considering feature interaction network, where a feature interaction network represents the relationship between features. This is different from some traditional methods, those of which learn similarities based on a sample network that represents the relationship between samples. Therefore, we propose a novel network-based similarity metric for computing the similarity between samples, which incorporates the knowledge of feature interaction network, in order to overcome the data sparseness problem. Our similarity metric uses a new Feature Alignment Similarity measure, which does not directly compute the similarities among samples, but projects each sample into a feature interaction network and measures the similarities between two samples using the similarities between the vertices of the samples in the network. As such, when two samples do not share any common features, they are likely to have higher similarity values when their features share the similar network regions. For ensuring that the metric is useful in a real-world application, we apply our metric to discover subtypes in tumor mutational data by incorporating the information of the gene interaction network. Our experimental results from using synthetic data and real-world tumor mutational data show that our approach outperforms the top competitors in cancer subtype discovery. Furthermore, our approach can identify cancer subtypes that cannot be detected by other clustering algorithms in real cancer data.
BibTeX
@inproceedings{qiang2020clustering,
  author = {Jipeng Qiang and Wei Ding and Marieke L. Kuijjer and John Quackenbush and Ping Chen},
  title = {{Clustering Sparse Data With Feature Correlation With Application to Discover Subtypes in Cancer}},
  booktitle = {IEEE Access},
  year = {2020},
  doi = {10.1109/access.2020.2982569},
}
Figure