densityCut: an efficient and versatile topological approach for automatic clustering of biological data
Open accessThe DOI matches its Crossref record; 7 of the 7 references it cites were found in a registry or an index.
Abstract
Motivation : Many biological data processing problems can be formalized as clustering problems to partition data points into sensible and biologically interpretable groups. Results : 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. Availability and Implementation : Data and the densityCut R package is available from https://bitbucket.org/jerry00/densitycut_dev . Contact : condon@cs.ubc.ca or sshah@bccrc.ca or jiaruid@cs.ubc.ca Supplementary information: Supplementary data are available at Bioinformatics online.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Data-Driven Phenotypic Dissection of AML Reveals Progenitor-like Cells that Correlate with Prognosis
Levine, J. H., Simonds, E. F., Bendall, S. C., Davis, K. L., Amir, E.-A. D., Tadmor, M. D., Litvin, O., Fienberg, H. G., Jager, A., Zunder, E. R., et al. (2015) · Cell · doi:10.1016/j.cell.2015.05.047 · Cited by 2,303 · cited 1×
“…have drastically enhanced our abilities to generate various high-throughput datasets, there is a great need to develop efficient and robust 2567 clustering algorithms to analyze large N (number of data points), 2568 arbitrary shape clusters and automatically determine the number of clusters.”
BackgroundBendall, S. C., Simonds, E. F., Qiu, P., Amir, E.-A. D., Krutzik, P. O., Finck, R., Bruggner, R. V., Melamed, R., Trejo, A., Ornatsky, O. I., et al. (2011) · Science · doi:10.1126/science.1198704 · Cited by 2,279
Clonal evolution in relapsed acute myeloid leukaemia revealed by whole-genome sequencing
Ding, L., Ley, T. J., Larson, D. E., Miller, C. A., Koboldt, D. C., Welch, J. S., Ritchey, J. K., Young, M. A., Lamprecht, T., McLellan, M. D., et al. (2012) · Nature · doi:10.1038/nature10738 · Cited by 1,993
Pollen, A. A., Nowakowski, T. J., Shuga, J., Wang, X., Leyrat, A. A., Lui, J. H., Li, N., Szpankowski, L., Fowler, B., Chen, P., et al. (2014) · Nature Biotechnology · doi:10.1038/nbt.2967 · Cited by 920 · cited 1×
“As measurement technology advances have drastically enhanced our abilities to generate various high-throughput datasets, there is a great need to develop efficient and robust 2567 clustering algorithms to analyze large N (number of data points), 2568 arbitrary shape clusters and automatically…”
BackgroundKriegel, H., Kröger, P., Sander, J., & Zimek, A. (2011) · WIREs Data Mining and Knowledge Discovery · doi:10.1002/widm.30 · Cited by 900
Llorens-Bobadilla, E., Zhao, S., Baser, A., Saiz-Castro, G., Zwadlo, K., & Martin-Villalba, A. (2015) · Cell Stem Cell · doi:10.1016/j.stem.2015.07.002 · Cited by 778
Identification of cell types from single-cell transcriptomes using a novel clustering method
Xu, C., & Su, Z. (2015) · Bioinformatics · doi:10.1093/bioinformatics/btv088 · Cited by 559
Cited by
Probabilistic cell-type assignment of single-cell RNA-seq for tumor microenvironment profiling
Zhang, A. W., O’Flanagan, C., Chavez, E. A., Lim, J. L. P., Ceglia, N., McPherson, A., Wiens, M., Walters, P., Chan, T., Hewitson, B., et al. (2019) · Nature Methods · doi:10.1038/s41592-019-0529-1 · Cited by 375
Self-citationInterpretable dimensionality reduction of single cell transcriptome data with deep generative models
Ding, J., Condon, A., & Shah, S. P. (2018) · Nature Communications · doi:10.1038/s41467-018-04368-5 · Cited by 337
Self-citationXu, H., Ding, J., Porter, C. B. M., Wallrapp, A., Tabaka, M., Ma, S., Fu, S., Guo, X., Riesenfeld, S. J., Su, C., et al. (2019) · Immunity · doi:10.1016/j.immuni.2019.09.004 · Cited by 273
Self-citationAutomatic cell type identification methods for single-cell RNA sequencing
Xie, B., Jiang, Q., Mora, A., & Li, X. (2021) · Computational and Structural Biotechnology Journal · doi:10.1016/j.csbj.2021.10.027 · Cited by 66
“CellAssign evaluates the performance of unsupervised meth-ods (Seurat, SC3 [15], PhenoGraph [65], densityCut [66], dynamic-TreeCut [67]), eager learning methods (scmap-cluster, correlation-based [68]) and marker learning methods (SCINA) on simulated data.”
Method
Metadata
- Authors
- Ding, J., Shah, S., & Condon, A.
- Venue
- Bioinformatics
- Publisher
- Oxford University Press (OUP)
- Published
- 2016-04-23
- Volume
- 32
- Issue
- 17
- Pages
- 2567-2576
- ISSN
- 1367-4803 (ISSN-L)
- 1367-4811
- OpenAlex
- W2336477031
- Cited by
- 36
- References
- 7
- FWCI
- 2.49
- Type
- journal article
- Language
- en
- Open access
- hybrid
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: densityCut: an efficient and versatile topological approach for automatic clustering of biological data. https://app.cochat.ai/papers/10.1093/bioinformatics/btw227
- The paper
- Ding, J., Shah, S., & Condon, A. (2016). densityCut: an efficient and versatile topological approach for automatic clustering of biological data. Bioinformatics. https://doi.org/10.1093/bioinformatics/btw227
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.