Method and system for subsampling of cells from single-cell genomics dataset
The present disclosure relates to a computer-implemented method of extracting a subsample of cells from a plurality of cells in a single-cell genomics dataset, the method comprising the steps of: obtaining a single-cell genomics dataset represented in at least two dimensions, 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; dividing the cells in the cell-cell neighborhood graph into seed cells and non-seed cells; assigning at least one first prize to the seed cells and at least one second prize to the non-seed cells in the cell-cell neighborhood graph; and traversing the cell-cell neighborhood graph using a prize collecting steiner tree algorithm to obtain a subsample of cells. The present disclosure further relates to a computer system for extracting a subsample of cells from a plurality of cells in a single-cell genomics dataset.
1 . A computer-implemented method of down-sampling a single-cell genomics dataset having an original manifold by extraction of a subsample of cells from a plurality of cells in a single-cell genomics dataset, the method comprising the steps of:
obtaining a single-cell genomics dataset represented in at least two dimensions, 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, wherein the step of generating the cell-cell neighborhood graph from the single-cell genomics dataset comprises performing a k nearest neighbors algorithm, wherein the k nearest neighbors algorithm comprises identifying k nearest neighbors of each cell, wherein k is a positive integer, and creating a cell-cell neighborhood graph wherein the cells are represented as vertices and the vertices are connected via edges if at least one of the vertices is a k nearest neighbor of the other one;
dividing the cells in the cell-cell neighborhood graph into computational seed cells and non-seed cells, wherein the seed cells are selected to capture a heterogeneity of the cells;
assigning at least one first prize to the seed cells and at least one second prize to the non-seed cells in the cell-cell neighborhood graph; and traversing the cell-cell neighborhood graph using a prize collecting steiner tree algorithm, wherein the algorithm is configured to include as many seed cells as possible and as few non-seed cells as possible, to obtain a subsample of cells preserving the original manifold.
2 . The method according to claim 1 , wherein the step of clustering the cells in the cell-cell neighborhood graph comprises limiting the number of cells within each cluster to a minimum and a maximum number of cells.
3 . The method according to claim 1 , wherein the step of dividing the cells in the cell-cell neighborhood graph into seed cells and non-seed cells comprises calculating a first metric representative of a density of the connections around a given node in the graph.
4 . The method according to claim 1 , wherein the step of dividing the cells in the cell-cell neighborhood graph into seed cells and non-seed cells comprises calculating a second metric representative of a neighbourhood connectedness indicating a degree of which connections are shared between many or few nodes.
5 . The method according to claim 1 , wherein the step of dividing the cells in the cell-cell neighborhood graph into seed cells and non-seed cells comprises selecting a least one cell from each cluster of cells, randomly or based on how central the cell is in the cluster of cells.
6 . The method according to claim 1 , wherein the step of clustering the cells in the cell-cell neighborhood graph converts the cell-cell neighborhood graph to a dendrogram structure, wherein each cell is represented as a leaf node and the leaves are connected to each other through branch point nodes in the dendrogram structure, wherein the step of clustering the cells in the cell-cell neighborhood graph comprises the step of ranking each cell based on how many branch point nodes that are between the cell and a root node of the dendrogram structure and clustering based on the ranking.
7 . The method according to claim 1 , wherein the step of clustering the cells in the cell-cell neighborhood graph converts the cell-cell neighborhood graph to a dendrogram structure, wherein each cell is represented as a leaf node and the leaves are connected to each other through branch point nodes in the dendrogram structure, wherein the step of clustering the cells in the cell-cell neighborhood graph comprises the step of partitioning the leaf nodes and branch point nodes into groups of cells, the groups having an upper bound and a lower bound.
8 . The method according to claim 7 , wherein the upper bound is smaller than, or equal to, 300, preferably smaller than, or equal to, 200, even more preferably smaller than, or equal to, 100.
9 . The method according to claim 1 , wherein the step of clustering the cells in the cell-cell neighborhood graph comprises the step of performing a first partitioning and for each partition of the first partitioning determining a number of sub-partitions based on a measure of strength of inter-connectivity of cells with each partition of the first partitioning.
10 . The method according to claim 9 , further comprising the step of performing sub-partitioning within the partitions of the first partitioning.
11 . The method according to claim 10 , wherein the step of performing sub-partitioning comprises the step of converting the cells within each partition of the first partitioning to a dendrogram structure indicating a hierarchical relationship between the cells.
12 . The method according to claim 1 , wherein a single first prize is higher than a single second prize, preferably wherein the second prize is 0, or wherein the at least one first prize and the at least one second prize are individually configurable prizes for the individual seed-cells and non-seed cells.
13 . The method according to claim 1 , further comprising the step of assigning penalties to edges between the vertices, wherein the penalties represent a degree of dissimilarity between the cells of the vertices.
14 . The method according to claim 1 , comprising the step of performing single-cell genomics sequencing to obtain the single-cell genomics dataset represented in at least two dimensions.
15 . The method according to claim 1 , comprising the step of performing a single-cell isolation.
16 . The method according to claim 1 , comprising the step of loading the single-cell genomics dataset represented in at least two dimensions into a digital medium of a computer system.
17 . A non-transitory computer readable medium for storing computer instructions which, when executed by at least one processor causes the at least one processor to perform the method of extracting a subsample of cells from a plurality of cells in a single-cell genomics dataset according to claim 1 .
18 . A computer 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, wherein the step of generating the cell-cell neighborhood graph from the single-cell genomics dataset comprises performing a k nearest neighbors algorithm, wherein the k nearest neighbors algorithm comprises identifying k nearest neighbors of each cell, wherein k is a positive integer, and creating a cell-cell neighborhood graph wherein the cells are represented as vertices and the vertices are connected via edges if at least one of the vertices is a k nearest neighbor of the other one;
dividing the cells in the cell-cell neighborhood graph into computational seed cells and non-seed cells, wherein seed cells are selected to capture a heterogeneity of the cells;
assigning at least one first prize to the seed cells and at least one second prize to the non-seed cells in the cell-cell neighborhood graph; and traversing the cell-cell neighborhood graph using a prize collecting steiner tree algorithm, wherein the algorithm is configured to include as many seed cells as possible and as few non-seed cells as possible, to obtain a subsample of cells.
19 . The computer system according to claim 18 , further comprising a display, wherein the processing unit is configured to display a graphical representation of the subsample of cells on the display.