How Algorithms Discover Cell Types from Gene Expression

Introduction

A human body holds roughly 37 trillion cells, yet for most of scientific history biologists could only study them in bulk. Grind up a tissue sample, extract its RNA, and you get an average — a blurry photo of millions of overlapping voices.

Single-cell RNA sequencing (scRNA-seq) changed that. Pioneered at scale by Macosko et al. in 2015, it captures the gene-expression profile of each cell individually — how loudly it is "speaking" each of its roughly 20,000 genes at the moment of capture. The result is a table with one row per cell and one column per gene, often tens of thousands of cells wide and tall.

The catch: nobody labels these cells in advance. You have raw numbers, no cell-type annotations. The question becomes purely algorithmic: can a computer look at those numbers and find structure? It turns out the answer is yes — and the key tool is a graph-based clustering algorithm. Related ideas appear in dimensionality reduction and graph coloring, both of which share the same high-dimensional geometry at their core.

Try It

Below is a simplified view of the pipeline. The demo generates synthetic cells with gene-expression profiles that secretly belong to a few types. The algorithm builds a k-nearest-neighbor (kNN) graph connecting each cell to its most similar peers, then runs Leiden community detection to partition the graph into clusters.

<!-- controls and canvas for the single-cell clustering demo -->
<div class="controls">
  <label>Neighbors k: <input type="range" id="kSlider" min="2" max="10" value="6"> <span id="kVal">6</span></label>
  <label>Cells: <input type="range" id="nSlider" min="30" max="120" value="60"> <span id="nVal">60</span></label>
  <button id="recluster" type="button">Recluster</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<canvas id="cv" width="480" height="320"></canvas>
<div id="status" class="status">Adjust sliders and click Recluster.</div>

/* styles for the single-cell clustering demo */
* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; background: #f5f7fa; padding: .6rem; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; align-items: center; margin-bottom: .5rem; }
label { font-size: .85rem; display: flex; gap: .3rem; align-items: center; }
input[type=range] { width: 80px; }
button { font: 600 13px system-ui; padding: .35rem .75rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 6px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; background: #fff; display: block; max-width: 100%; }
.status { margin-top: .4rem; font-size: .88rem; font-weight: 600; min-height: 1.2em; color: #444; }
.status.ok { color: #0a7d33; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// color palette — one color per discovered cluster
const PALETTE = ['#e63946','#457b9d','#2a9d8f','#e9c46a','#f4a261','#6a4c93','#43aa8b','#f77f00'];

// generate synthetic cells arranged in Gaussian blobs
function generateCells(n) {
  // five cluster centers in normalized [0,1] x [0,1] space
  const centers = [
    [0.2, 0.2], [0.75, 0.2], [0.5, 0.65],
    [0.2, 0.75], [0.8, 0.75]
  ];
  const cells = [];
  for (let i = 0; i < n; i++) {
    const c = centers[i % centers.length];
    // Box-Muller transform for Gaussian noise
    const u1 = Math.random(), u2 = Math.random();
    const z = Math.sqrt(-2 * Math.log(u1 + 1e-9)) * Math.cos(2 * Math.PI * u2);
    const w = Math.sqrt(-2 * Math.log(Math.random() + 1e-9)) * Math.cos(2 * Math.PI * Math.random());
    cells.push({ x: c[0] + z * 0.11, y: c[1] + w * 0.11, trueGroup: i % centers.length });
  }
  return cells;
}

// build a k-nearest-neighbor graph in 2D Euclidean space
function buildKNN(cells, k) {
  const n = cells.length;
  const adj = Array.from({ length: n }, () => []);
  for (let i = 0; i < n; i++) {
    const dists = [];
    for (let j = 0; j < n; j++) {
      if (i === j) continue;
      const dx = cells[i].x - cells[j].x, dy = cells[i].y - cells[j].y;
      dists.push({ j, d: dx * dx + dy * dy });
    }
    dists.sort((a, b) => a.d - b.d);
    for (let t = 0; t < k && t < dists.length; t++) {
      adj[i].push(dists[t].j);
      adj[dists[t].j].push(i);
    }
  }
  // deduplicate undirected edges
  return adj.map(a => [...new Set(a)]);
}

// simplified Leiden-style greedy modularity optimization
function leiden(adj) {
  const n = adj.length;
  let comm = Array.from({ length: n }, (_, i) => i);
  // iterate until no improvement or max passes reached
  let improved = true;
  const totalEdges = adj.reduce((s, a) => s + a.length, 0) / 2;
  const deg = adj.map(a => a.length);
  function gain(node, target, comm) {
    let k_in = 0;
    for (const nb of adj[node]) if (comm[nb] === target) k_in++;
    const sigma_tot = deg.filter((_, i) => comm[i] === target).reduce((a, b) => a + b, 0);
    return k_in / totalEdges - (sigma_tot * deg[node]) / (2 * totalEdges * totalEdges);
  }
  // greedy local move phase: move each node to the best neighbor community
  for (let pass = 0; pass < 20 && improved; pass++) {
    improved = false;
    for (let i = 0; i < n; i++) {
      const cur = comm[i];
      let bestG = 0, bestC = cur;
      const candidates = new Set(adj[i].map(nb => comm[nb]));
      candidates.delete(cur);
      for (const c of candidates) {
        const g = gain(i, c, comm) - gain(i, cur, comm);
        if (g > bestG) { bestG = g; bestC = c; }
      }
      if (bestC !== cur) { comm[i] = bestC; improved = true; }
    }
  }
  // relabel community ids to 0..numClusters-1
  const map = new Map();
  let next = 0;
  return comm.map(c => { if (!map.has(c)) map.set(c, next++); return map.get(c); });
}

const cv = document.getElementById('cv');
const ctx = cv.getContext('2d');
const kSlider = document.getElementById('kSlider');
const nSlider = document.getElementById('nSlider');
const kVal = document.getElementById('kVal');
const nVal = document.getElementById('nVal');
const status = document.getElementById('status');

let cells = [], comm = [], adj = [];

function draw() {
  const W = cv.width, H = cv.height;
  ctx.clearRect(0, 0, W, H);
  // draw kNN graph edges in light gray
  ctx.lineWidth = 0.5;
  ctx.strokeStyle = '#cdd9e3';
  for (let i = 0; i < cells.length; i++) {
    for (const j of adj[i]) {
      if (j > i) {
        ctx.beginPath();
        ctx.moveTo(cells[i].x * W, cells[i].y * H);
        ctx.lineTo(cells[j].x * W, cells[j].y * H);
        ctx.stroke();
      }
    }
  }
  // draw each cell dot colored by its cluster
  for (let i = 0; i < cells.length; i++) {
    const col = PALETTE[comm[i] % PALETTE.length];
    ctx.beginPath();
    ctx.arc(cells[i].x * W, cells[i].y * H, 5, 0, 2 * Math.PI);
    ctx.fillStyle = col;
    ctx.fill();
    ctx.strokeStyle = '#fff';
    ctx.lineWidth = 1;
    ctx.stroke();
  }
}

function run() {
  const k = +kSlider.value;
  const n = +nSlider.value;
  cells = generateCells(n);
  adj = buildKNN(cells, k);
  comm = leiden(adj);
  const nClusters = new Set(comm).size;
  draw();
  status.textContent = i18nFmt('Found %n% cluster(s) with k=%k% neighbors.', { n: nClusters, k: k });
  status.className = 'status ok';
}

kSlider.addEventListener('input', () => { kVal.textContent = kSlider.value; });
nSlider.addEventListener('input', () => { nVal.textContent = nSlider.value; });
document.getElementById('recluster').addEventListener('click', run);
document.getElementById('reset').addEventListener('click', () => {
  cells = []; comm = []; adj = [];
  ctx.clearRect(0, 0, cv.width, cv.height);
  status.textContent = 'Adjust sliders and click Recluster.';
  status.className = 'status';
});
run();

<!-- controls and canvas for the single-cell clustering demo -->
<div class="controls">
  <label>Neighbors k: <input type="range" id="kSlider" min="2" max="10" value="6"> <span id="kVal">6</span></label>
  <label>Cells: <input type="range" id="nSlider" min="30" max="120" value="60"> <span id="nVal">60</span></label>
  <button id="recluster" type="button">Recluster</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>
<canvas id="cv" width="480" height="320"></canvas>
<div id="status" class="status">Adjust sliders and click Recluster.</div>

/* styles for the single-cell clustering demo */
* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; background: #f5f7fa; padding: .6rem; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; align-items: center; margin-bottom: .5rem; }
label { font-size: .85rem; display: flex; gap: .3rem; align-items: center; }
input[type=range] { width: 80px; }
button { font: 600 13px system-ui; padding: .35rem .75rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 6px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; background: #fff; display: block; max-width: 100%; }
.status { margin-top: .4rem; font-size: .88rem; font-weight: 600; min-height: 1.2em; color: #444; }
.status.ok { color: #0a7d33; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// color palette — one color per discovered cluster
const PALETTE = ['#e63946','#457b9d','#2a9d8f','#e9c46a','#f4a261','#6a4c93','#43aa8b','#f77f00'];

// generate synthetic cells arranged in Gaussian blobs
function generateCells(n) {
  // five cluster centers in normalized [0,1] x [0,1] space
  const centers = [
    [0.2, 0.2], [0.75, 0.2], [0.5, 0.65],
    [0.2, 0.75], [0.8, 0.75]
  ];
  const cells = [];
  for (let i = 0; i < n; i++) {
    const c = centers[i % centers.length];
    // Box-Muller transform for Gaussian noise
    const u1 = Math.random(), u2 = Math.random();
    const z = Math.sqrt(-2 * Math.log(u1 + 1e-9)) * Math.cos(2 * Math.PI * u2);
    const w = Math.sqrt(-2 * Math.log(Math.random() + 1e-9)) * Math.cos(2 * Math.PI * Math.random());
    cells.push({ x: c[0] + z * 0.11, y: c[1] + w * 0.11, trueGroup: i % centers.length });
  }
  return cells;
}

// build a k-nearest-neighbor graph in 2D Euclidean space
function buildKNN(cells, k) {
  const n = cells.length;
  const adj = Array.from({ length: n }, () => []);
  for (let i = 0; i < n; i++) {
    const dists = [];
    for (let j = 0; j < n; j++) {
      if (i === j) continue;
      const dx = cells[i].x - cells[j].x, dy = cells[i].y - cells[j].y;
      dists.push({ j, d: dx * dx + dy * dy });
    }
    dists.sort((a, b) => a.d - b.d);
    for (let t = 0; t < k && t < dists.length; t++) {
      adj[i].push(dists[t].j);
      adj[dists[t].j].push(i);
    }
  }
  // deduplicate undirected edges
  return adj.map(a => [...new Set(a)]);
}

// simplified Leiden-style greedy modularity optimization
function leiden(adj) {
  const n = adj.length;
  let comm = Array.from({ length: n }, (_, i) => i);
  // iterate until no improvement or max passes reached
  let improved = true;
  const totalEdges = adj.reduce((s, a) => s + a.length, 0) / 2;
  const deg = adj.map(a => a.length);
  function gain(node, target, comm) {
    let k_in = 0;
    for (const nb of adj[node]) if (comm[nb] === target) k_in++;
    const sigma_tot = deg.filter((_, i) => comm[i] === target).reduce((a, b) => a + b, 0);
    return k_in / totalEdges - (sigma_tot * deg[node]) / (2 * totalEdges * totalEdges);
  }
  // greedy local move phase: move each node to the best neighbor community
  for (let pass = 0; pass < 20 && improved; pass++) {
    improved = false;
    for (let i = 0; i < n; i++) {
      const cur = comm[i];
      let bestG = 0, bestC = cur;
      const candidates = new Set(adj[i].map(nb => comm[nb]));
      candidates.delete(cur);
      for (const c of candidates) {
        const g = gain(i, c, comm) - gain(i, cur, comm);
        if (g > bestG) { bestG = g; bestC = c; }
      }
      if (bestC !== cur) { comm[i] = bestC; improved = true; }
    }
  }
  // relabel community ids to 0..numClusters-1
  const map = new Map();
  let next = 0;
  return comm.map(c => { if (!map.has(c)) map.set(c, next++); return map.get(c); });
}

const cv = document.getElementById('cv');
const ctx = cv.getContext('2d');
const kSlider = document.getElementById('kSlider');
const nSlider = document.getElementById('nSlider');
const kVal = document.getElementById('kVal');
const nVal = document.getElementById('nVal');
const status = document.getElementById('status');

let cells = [], comm = [], adj = [];

function draw() {
  const W = cv.width, H = cv.height;
  ctx.clearRect(0, 0, W, H);
  // draw kNN graph edges in light gray
  ctx.lineWidth = 0.5;
  ctx.strokeStyle = '#cdd9e3';
  for (let i = 0; i < cells.length; i++) {
    for (const j of adj[i]) {
      if (j > i) {
        ctx.beginPath();
        ctx.moveTo(cells[i].x * W, cells[i].y * H);
        ctx.lineTo(cells[j].x * W, cells[j].y * H);
        ctx.stroke();
      }
    }
  }
  // draw each cell dot colored by its cluster
  for (let i = 0; i < cells.length; i++) {
    const col = PALETTE[comm[i] % PALETTE.length];
    ctx.beginPath();
    ctx.arc(cells[i].x * W, cells[i].y * H, 5, 0, 2 * Math.PI);
    ctx.fillStyle = col;
    ctx.fill();
    ctx.strokeStyle = '#fff';
    ctx.lineWidth = 1;
    ctx.stroke();
  }
}

function run() {
  const k = +kSlider.value;
  const n = +nSlider.value;
  cells = generateCells(n);
  adj = buildKNN(cells, k);
  comm = leiden(adj);
  const nClusters = new Set(comm).size;
  draw();
  status.textContent = i18nFmt('Found %n% cluster(s) with k=%k% neighbors.', { n: nClusters, k: k });
  status.className = 'status ok';
}

kSlider.addEventListener('input', () => { kVal.textContent = kSlider.value; });
nSlider.addEventListener('input', () => { nVal.textContent = nSlider.value; });
document.getElementById('recluster').addEventListener('click', run);
document.getElementById('reset').addEventListener('click', () => {
  cells = []; comm = []; adj = [];
  ctx.clearRect(0, 0, cv.width, cv.height);
  status.textContent = 'Adjust sliders and click Recluster.';
  status.className = 'status';
});
run();

Result

Console

Each color is a cluster the algorithm found without ever seeing the true labels. Notice how tightening the neighborhood (fewer neighbors $k$ ) breaks big clusters apart, while loosening it merges them. The algorithm never minimizes a single global cost — it optimizes modularity, a score that rewards dense within-cluster edges and penalizes sparse between-cluster ones.

The Real Complexity

Clustering sounds simple: group similar things together. But optimal graph clustering is a different story.

Modularity maximization is NP-hard. The modularity score $Q$ rewards dense intra-cluster edges and penalizes inter-cluster ones: $ $Q = \frac{1}{2m}\sum_{ij}\!\left[A_{ij} - \frac{k_i k_j}{2m}\right]\delta(c_i, c_j)$ $ where $m$ is the number of edges, $k_i$ is the degree of node $i$ , and $\delta(c_i,c_j)$ equals 1 if nodes $i$ and $j$ share a cluster. Branchinowski & Meylan (2007) proved finding the exact maximum is NP-hard — the search space is the Bell number $B_n$ , which grows faster than any exponential.
Louvain (2008) made it tractable. The Louvain algorithm greedily moves nodes between communities to improve $Q$ , runs in roughly $O(n \log n)$ time, and scales to millions of cells. It became the default in single-cell pipelines.
Leiden (2019) fixed Louvain's flaw. Traag, Waltman and van Eck showed that Louvain can produce disconnected communities — nodes that share a label but have no path between them inside the cluster. Leiden adds a refinement phase that splits and merges sub-communities to guarantee connectivity while keeping the same near-linear runtime.
Resolution parameter $\gamma$ . Both algorithms have a tunable resolution that shifts the trade-off between many small clusters and few large ones. Choosing $\gamma$ is a form of non-convex optimization: the modularity landscape has many local maxima and no efficient way to find the global one.

Where It Matters

Single-cell clustering is not an academic curiosity — it is reshaping medicine and biology:

Cell-type atlases: The Human Cell Atlas project is using scRNA-seq and Leiden clustering to produce a reference map of every cell type in the human body. As of 2024 it has profiled over 100 million cells across dozens of tissues.
Cancer biology: tumors are mixtures of cell states. Clustering single-cell data from a tumor reveals rare subclones that resist treatment — the cells most important to target but least visible in bulk sequencing.
Drug discovery: identifying which cell type a gene is expressed in narrows the search for drug targets and predicts off-target effects. The same graph pipeline drives large-scale screens in pharmaceutical labs.
Neuroscience: the Allen Brain Cell Atlas, released in 2023, catalogued over 3,000 distinct cell types across the entire mouse brain using single-cell clustering — a number that surprised the field.
Developmental biology: following cells through differentiation is only possible cell by cell. Clustering across time points reveals the branching paths cells take as an embryo develops.

The algorithm at the center of all of this is the same Leiden community detection that finds communities in social networks and web graphs — a beautiful case of a general algorithm finding an unexpected home in molecular biology.

Conclusion

Single-cell clustering is one of biology's great algorithmic success stories. A problem that looks impossibly hard in the abstract — partition tens of thousands of high-dimensional points into meaningful groups, with no ground truth — turns out to be tractable in practice because biological cell types form genuine clusters in gene-expression space.

The Leiden algorithm exploits that structure: it cannot guarantee the optimal partition (that remains NP-hard), but it finds excellent ones fast enough to run on a laptop. The result is a map of cell types drawn entirely from numbers, with no human labeling required.

Whenever you hear that scientists "discovered a new cell type" or that a tumor has a "rare drug-resistant subpopulation," there is almost certainly a graph algorithm quietly drawing the boundaries behind the headline.

Comments

Loading comments...

https://www.kipuhub.com/en/article/single-cell-clustering/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Single-Cell Clustering

Finding cell types without ever being told what they are