title: densityCut: an efficient and versatile topological approach for automatic clustering of biological data.
abstract: 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.ca
  
  
  
  Supplementary data are available at Bioinformatics online.
authors.affiliation: Department of Computer Science, University of British Columbia, Vancouver, BC V6T 1Z4, Canada Department of Molecular Oncology, BC Cancer Research Centre, Vancouver, BC V5Z 1L3, Canada.
authors.forename: Jiarui
authors.initials: J
authors.lastname: Ding
authors.affiliation: Department of Computer Science, University of British Columbia, Vancouver, BC V6T 1Z4, Canada Department of Molecular Oncology, BC Cancer Research Centre, Vancouver, BC V5Z 1L3, Canada.
authors.forename: Sohrab
authors.initials: S
authors.lastname: Shah
authors.affiliation: Department of Computer Science, University of British Columbia, Vancouver, BC V6T 1Z4, Canada.
authors.forename: Anne
authors.initials: A
authors.lastname: Condon
mesh_terms: D000465:Algorithms; D016000:Cluster Analysis; D015870:Gene Expression; D020869:Gene Expression Profiling; D006801:Humans; D020411:Oligonucleotide Array Sequence Analysis