CosTaL: an accurate and scalable graph-based clustering algorithm for high-dimensional single-cell data analysis

Yijia Li, Jonathan Nguyen, David C. Anastasiu, Edgar A. Arriaga

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


With the aim of analyzing large-sized multidimensional single-cell datasets, we are describing a method for Cosine-based Tanimoto similarity-refined graph for community detection using Leiden's algorithm (CosTaL). As a graph-based clustering method, CosTaL transforms the cells with high-dimensional features into a weighted k-nearest-neighbor (kNN) graph. The cells are represented by the vertices of the graph, while an edge between two vertices in the graph represents the close relatedness between the two cells. Specifically, CosTaL builds an exact kNN graph using cosine similarity and uses the Tanimoto coefficient as the refining strategy to re-weight the edges in order to improve the effectiveness of clustering. We demonstrate that CosTaL generally achieves equivalent or higher effectiveness scores on seven benchmark cytometry datasets and six single-cell RNA-sequencing datasets using six different evaluation metrics, compared with other state-of-the-art graph-based clustering methods, including PhenoGraph, Scanpy and PARC. As indicated by the combined evaluation metrics, Costal has high efficiency with small datasets and acceptable scalability for large datasets, which is beneficial for large-scale analysis.

Original languageEnglish (US)
Article numberbbad157
JournalBriefings in Bioinformatics
Issue number3
StatePublished - May 1 2023

Bibliographical note

Publisher Copyright:
© The Author(s) 2023. Published by Oxford University Press. All rights reserved.


  • Clustering
  • Flow Cytometry
  • Graph-based clustering
  • Mass Cytometry
  • Single-cell RNA sequencing
  • k nearest neighbors

PubMed: MeSH publication types

  • Journal Article
  • Research Support, Non-U.S. Gov't
  • Research Support, N.I.H., Extramural


Dive into the research topics of 'CosTaL: an accurate and scalable graph-based clustering algorithm for high-dimensional single-cell data analysis'. Together they form a unique fingerprint.

Cite this