Method and system for extracting a subsample of cells from a single-cell genomics dataset using balanced dendrogram clustering

A computer system for extracting a subsample of cells from a plurality of cells in a single-cell genomics dataset, the system comprising:

• a memory;
• and
• a processing unit configured to perform the steps of:
• loading a single-cell genomics dataset represented in at least two dimensions into the memory, wherein information about each cell is represented in a first dimension and information about genomic features is represented in a second dimension;
• generating a cell-cell neighborhood graph from the single-cell genomics dataset, the cell-cell neighborhood graph providing information about similarities of the genomic features of the cells, wherein the cells are represented as vertices in the cell-cell neighborhood graph;
• converting the cell-cell neighborhood graph to a dendrogram structure, wherein each cell is represented as a leaf node and the leaf nodes are connected to each other through branch point nodes, the branch point nodes joining upstream into a root node;
• partitioning the cells in the dendrogram structure into clusters by:
• (a) ranking each cell based on how many branch point nodes are between the cell and the root node of the dendrogram structure;
• (b) aggregating cells into clusters starting from a cell having a highest rank and traversing upstream through branch point nodes, wherein a cluster is frozen when including an upstream branch point node would increase a size of the cluster to more than a predetermined upper bound on the number of cells;
• and
• (c) merging clusters having fewer cells than a predetermined lower bound with a cluster sharing a most recent common ancestor in the dendrogram structure;
• choosing at least one cell from each cluster and categorizing the chosen cells as seed cells, the seed cells capturing a heterogeneity of the cells in the single-cell genomics dataset;
• and
• extracting a subsample of cells from the cell-cell neighborhood graph based on the seed cells, the subsample preserving an original manifold of the single-cell genomics dataset.