Introduction

Many biological data processing problems can be formalized as clustering problems to partition data points into sensible and biologically interpretable groups.This article introduces densityCut, a novel density-based clustering algorithm, which is both time- and space-efficient and proceeds as follows: densityCut first roughly estimates the densities of data points from a K-nearest neighbour graph and then refines the densities via a random walk. A cluster consists of points falling into the basin of attraction of an estimated mode of the underlining density function. A post-processing step merges clusters and generates a hierarchical cluster tree. The number of clusters is selected from the most stable clustering in the hierarchical cluster tree. Experimental results on ten synthetic benchmark datasets and two microarray gene expression datasets demonstrate that densityCut performs better than state-of-the-art algorithms for clustering biological datasets. For applications, we focus on the recent cancer mutation clustering and single cell data analyses, namely to cluster variant allele frequencies of somatic mutations to reveal clonal architectures of individual tumours, to cluster single-cell gene expression data to uncover cell population compositions, and to cluster single-cell mass cytometry data to detect communities of cells of the same functional states or types. densityCut performs better than competing algorithms and is scalable to large datasets.Data and the densityCut R package is available from https://bitbucket.org/jerry00/densitycut_dev: condon@cs.ubc.ca or sshah@bccrc.ca or jiaruid@cs.ubc.caSupplementary data are available at Bioinformatics online.

Publications

  1. densityCut: an efficient and versatile topological approach for automatic clustering of biological data.
    Cite this
    Ding J, Shah S, Condon A, 2016-09-01 - Bioinformatics (Oxford, England)

Credits

  1. Jiarui Ding
    Developer

    Department of Computer Science, University of British Columbia, Canada

  2. Sohrab Shah
    Developer

    Department of Computer Science, University of British Columbia, Canada

  3. Anne Condon
    Investigator

    Department of Computer Science, University of British Columbia, Canada

Community Ratings

UsabilityEfficiencyReliabilityRated By
0 user
Sign in to rate
Summary
AccessionBT001777
Tool TypeApplication
Category
Platforms
TechnologiesR
User InterfaceTerminal Command Line
Download Count0
Country/RegionCanada
Submitted ByAnne Condon