diff options
| author | Pjotr Prins <pjotr.public01@thebird.nl> | 2026-11-16 17:17:11 +0000 |
|---|---|---|
| committer | Pjotr Prins <pjotr.public01@thebird.nl> | 2026-11-16 17:17:11 +0000 |
| commit | ea3dd926211e8db4a0d7d3739a606440b888e8b0 (patch) | |
| tree | 31b58cd0126960e70a76e45dc2c3b7c9a1c6d0b6 /src | |
| parent | 33e837e771e07936c808fb3aeb3540525691718c (diff) | |
| download | genenetwork4-main.tar.gz | |
`"cluster": true` adds `heatmap: {order, merges, max_height}` to the matrix
reply and `POST /plot/heatmap` draws it: the r matrix in that order, the
dendrogram that produced it, and a diverging scale with blue negative and red
positive. A reader can see *why* two traits are neighbours instead of trusting
an ordering.
Clustering decisions, all recorded because an unrepeatable clustering is worse
than none:
* distance `1 - r` -- the usual choice for correlations, and it keeps
anti-correlated traits apart, which is what a heatmap of correlations should
show;
* **average linkage (UPGMA)** -- single linkage chains along a gradient and
complete linkage makes one flat blob out of noisy traits; average is the
compromise GN1's R heatmaps used too;
* **deterministic ties and leaf order** (lower index first), so two runs on one
matrix produce the same picture and plots stay diffable;
* a matrix with a **gap is refused** rather than clustered: an unknown distance
treated as 1 would invent a structure, and the reply's note says to drop
those traits and ask again.
Pairing with the PCA work this is the visual half of a collection: scree plot
for how much structure there is, clustered heatmap for where it is.
Monitor, as asked: `compute-correlation-heatmap` (order must be a permutation
with n-1 merges), `plot-heatmap`, and the plot endpoints that had no check at
all -- `plot-gemma` and `plot-bnw`, each posting a real compute result back.
Plots tier is now five checks, all ok; full run 47 ok, 0 failed, 1 skipped.
Diffstat (limited to 'src')
| -rw-r--r-- | src/config.rs | 8 | ||||
| -rw-r--r-- | src/heatmap.rs | 214 | ||||
| -rw-r--r-- | src/lib.rs | 2 | ||||
| -rw-r--r-- | src/routes/correlation_matrix.rs | 29 | ||||
| -rw-r--r-- | src/routes/plot.rs | 97 |
5 files changed, 350 insertions, 0 deletions
diff --git a/src/config.rs b/src/config.rs index a4a078c..c6a1553 100644 --- a/src/config.rs +++ b/src/config.rs @@ -173,6 +173,8 @@ pub struct Config { pub bnw_plotter: String, /// Script that draws the scree plot of a correlation-matrix PCA (PCA_PLOTTER). pub pca_plotter: String, + /// Script that draws the clustered heatmap of a correlation matrix (HEATMAP_PLOTTER). + pub heatmap_plotter: String, /// Directory holding BNW's worked example datasets (`BNW_EXAMPLES_DIR`), /// served by `/compute/bnw/examples`. Empty means the endpoint reports /// that no examples are configured. @@ -413,6 +415,10 @@ impl Config { "PCA_PLOTTER".to_string(), "scripts/plot-pca.py".to_string(), ); + values.insert( + "HEATMAP_PLOTTER".to_string(), + "scripts/plot-heatmap.py".to_string(), + ); // Per-user baskets: one SQLite file each (src/baskets.rs). Never // MariaDB -- a user's edited column is theirs. values.insert( @@ -480,6 +486,7 @@ impl Config { "BASKET_DIR", "GENOTYPE_PLOTTER", "PCA_PLOTTER", + "HEATMAP_PLOTTER", "BNW_CMD", "BNW_BIN_DIR", "BNW_CACHE_DIR", @@ -546,6 +553,7 @@ impl Config { bnw_cache_dir: values["BNW_CACHE_DIR"].clone(), bnw_plotter: values["BNW_PLOTTER"].clone(), pca_plotter: values["PCA_PLOTTER"].clone(), + heatmap_plotter: values["HEATMAP_PLOTTER"].clone(), bnw_examples_dir: values["BNW_EXAMPLES_DIR"].clone(), bulklmm_cmd: values["BULKLMM_CMD"].clone(), bulklmm_env: values["BULKLMM_ENV"].clone(), diff --git a/src/heatmap.rs b/src/heatmap.rs new file mode 100644 index 0000000..f179980 --- /dev/null +++ b/src/heatmap.rs @@ -0,0 +1,214 @@ +//! Clustered ordering of a correlation matrix, for a heatmap. +//! +//! The matrix is symmetric, so one ordering serves both axes: cluster the +//! traits, then draw the r matrix in that order and a neighbour is a trait that +//! actually looks like its neighbour. +//! +//! Decisions, all stated because a clustering nobody can reproduce is worse +//! than no clustering: +//! +//! * **Distance is `1 - r`**, so a pair at r = 1 sits at 0 and a pair at +//! r = -1 at 2. That is the usual choice for correlation matrices and it +//! keeps anti-correlated traits far apart, which is what a reader expects +//! from a heatmap of *correlations*. +//! * **Average linkage (UPGMA).** Single linkage chains along a gradient and +//! complete linkage makes one huge flat cluster from anything with noise in +//! it; average is the compromise that behaves on real expression traits. It +//! is also what GN1's heatmaps used (R's `hclust(method="average")`). +//! * **Deterministic ties**: when two merges have the same height the lower +//! index wins, and the leaf order comes out of the tree by always placing the +//! earlier-clustered side first. Two runs on the same matrix give the same +//! order, which is what makes the plot diffable. +//! +//! The algorithm is the textbook O(n^3) one: n is at most `MAX_PCA_TRAITS`, and +//! clarity beats a faster distance-update scheme that has to be trusted. + +/// One merge in the tree, enough to draw a dendrogram. +#[derive(Debug, Clone, serde::Serialize, utoipa::ToSchema)] +pub struct Merge { + /// Cluster ids 0..n-1 are the traits themselves; n and up are merges, in + /// the order they appear in this list. + pub left: usize, + pub right: usize, + /// Distance at which the two were joined (`1 - r`, so 0 is identical). + pub height: f64, +} + +/// The clustered order and the tree that produced it. +#[derive(Debug, Clone, serde::Serialize, utoipa::ToSchema)] +pub struct Clustering { + /// Trait indices in drawing order (row and column order both). + pub order: Vec<usize>, + pub merges: Vec<Merge>, + /// Largest distance seen, so a plotter can scale the dendrogram. + pub max_height: f64, +} + +/// Average-linkage clustering of a correlation matrix. +/// +/// Returns `None` for a matrix that is not square, is larger than the cap, or +/// has a cell that is not a number -- a gap means the two traits' distance is +/// unknown, and quietly treating it as 1 would invent a structure. +pub fn cluster(r: &[Vec<Option<f64>>], cap: usize) -> Option<Clustering> { + let n = r.len(); + if n < 2 || n > cap || r.iter().any(|row| row.len() != n) { + return None; + } + let mut distance = vec![vec![0.0; n]; n]; + for i in 0..n { + for j in 0..n { + let value = r[i][j]?; + if !value.is_finite() { + return None; + } + distance[i][j] = 1.0 - value; + } + } + + // Active clusters: members and the merge tree. + let mut members: Vec<Vec<usize>> = (0..n).map(|index| vec![index]).collect(); + let mut active: Vec<bool> = vec![true; n]; + let mut sizes: Vec<usize> = vec![1; n]; + let mut dist = distance; + let mut merges: Vec<Merge> = Vec::new(); + let mut max_height = 0.0_f64; + + for _ in 1..n { + // Nearest pair of active clusters, lowest index pair on a tie. + let mut best = (f64::INFINITY, 0usize, 0usize); + for i in 0..dist.len() { + if !active[i] { + continue; + } + for j in (i + 1)..dist.len() { + if !active[j] { + continue; + } + let d = dist[i][j]; + if d < best.0 { + best = (d, i, j); + } + } + } + let (height, left, right) = best; + if !height.is_finite() { + return None; + } + max_height = max_height.max(height); + // Ids in this array ARE the tree ids: traits are 0..n-1 and merge m is + // n+m, created in this order, so the pair can be recorded as it stands. + let new_id = dist.len(); + merges.push(Merge { left, right, height }); + + // Average linkage: the new distance is the size-weighted mean. + let mut row = vec![0.0; new_id + 1]; + for k in 0..new_id { + if !active[k] || k == left || k == right { + continue; + } + row[k] = (dist[left][k] * sizes[left] as f64 + dist[right][k] * sizes[right] as f64) + / (sizes[left] + sizes[right]) as f64; + } + // Grow the matrix to new_id + 1 rows before writing into the new row: + // pushing the row first is what makes dist[new_id] exist. + for existing in dist.iter_mut() { + existing.push(0.0); + } + dist.push(row.clone()); + for k in 0..new_id { + dist[new_id][k] = row[k]; + dist[k][new_id] = row[k]; + } + + active[left] = false; + active[right] = false; + active.push(true); + sizes.push(sizes[left] + sizes[right]); + members.push(Vec::new()); + let mut merged = members[left].clone(); + merged.extend(members[right].iter().copied()); + members[new_id] = merged; + } + + // Leaf order: walk the tree, earlier-clustered side first (deterministic). + let mut order = Vec::with_capacity(n); + fn walk(id: usize, n: usize, merges: &[Merge], order: &mut Vec<usize>) { + if id < n { + order.push(id); + return; + } + let index = id - n; + let merge = &merges[index]; + walk(merge.left, n, merges, order); + walk(merge.right, n, merges, order); + } + walk(dist.len() - 1, n, &merges, &mut order); + if order.len() != n { + return None; + } + Some(Clustering { + order, + merges, + max_height, + }) +} + +#[cfg(test)] +mod tests { + use super::*; + + fn matrix(values: &[&[f64]]) -> Vec<Vec<Option<f64>>> { + values + .iter() + .map(|row| row.iter().map(|v| Some(*v)).collect()) + .collect() + } + + #[test] + fn two_blocks_are_ordered_together() { + // 0 and 1 correlate strongly with each other and with nothing else; + // same for 2 and 3. A good ordering keeps each pair adjacent. + let r = matrix(&[ + &[1.0, 0.9, 0.0, 0.1], + &[0.9, 1.0, 0.1, 0.0], + &[0.0, 0.1, 1.0, 0.85], + &[0.1, 0.0, 0.85, 1.0], + ]); + let clustering = cluster(&r, 300).expect("4x4"); + let order = clustering.order; + let position = |trait_index: usize| order.iter().position(|x| *x == trait_index).unwrap(); + assert_eq!(position(0).abs_diff(position(1)), 1, "0 and 1 adjacent: {order:?}"); + assert_eq!(position(2).abs_diff(position(3)), 1, "2 and 3 adjacent: {order:?}"); + assert_eq!(order.len(), 4); + assert_eq!(clustering.merges.len(), 3); + // The first merges are the within-block ones, so they are the closest. + assert!(clustering.merges[0].height < 0.2); + assert!(clustering.merges[2].height >= clustering.merges[0].height); + } + + #[test] + fn the_order_is_reproducible() { + let r = matrix(&[ + &[1.0, 0.4, -0.2], + &[0.4, 1.0, 0.1], + &[-0.2, 0.1, 1.0], + ]); + let first = cluster(&r, 300).expect("3x3"); + let second = cluster(&r, 300).expect("3x3"); + assert_eq!(first.order, second.order); + assert_eq!(first.merges.len(), second.merges.len()); + } + + #[test] + fn a_gap_refuses_rather_than_invents() { + let mut r = matrix(&[&[1.0, 0.5], &[0.5, 1.0]]); + r[0][1] = None; + assert!(cluster(&r, 300).is_none(), "a null cell is not a distance of 1"); + } + + #[test] + fn the_cap_is_honoured() { + let r = matrix(&[&[1.0, 0.5, 0.2], &[0.5, 1.0, 0.3], &[0.2, 0.3, 1.0]]); + assert!(cluster(&r, 2).is_none()); + } +} diff --git a/src/lib.rs b/src/lib.rs index 1973652..976b2f1 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -22,6 +22,7 @@ pub mod fitqtl; pub mod frequencies; pub mod genoupload; pub mod genotypes; +pub mod heatmap; pub mod normalize; mod plot; mod error; @@ -260,6 +261,7 @@ pub fn app() -> Router { .routes(routes!(routes::plot::plot_bulklmm)) .routes(routes!(routes::plot::plot_bnw)) .routes(routes!(routes::plot::plot_pca)) + .routes(routes!(routes::plot::plot_heatmap)) .routes(routes!(routes::phewas::group_phewas)) .routes(routes!(routes::frequencies::group_version_frequencies)) .routes(routes!(routes::frequencies::group_marker_frequencies)) diff --git a/src/routes/correlation_matrix.rs b/src/routes/correlation_matrix.rs index 2e6c883..9a433b6 100644 --- a/src/routes/correlation_matrix.rs +++ b/src/routes/correlation_matrix.rs @@ -65,6 +65,11 @@ pub struct MatrixRequest { /// Fewest paired observations a cell may have. Defaults to 6. #[serde(default)] pub min_overlap: Option<usize>, + /// Also return a clustered ordering (and its tree) for a heatmap: average + /// linkage on `1 - r`. The matrix is symmetric, so one order serves both + /// axes. + #[serde(default)] + pub cluster: Option<bool>, /// Also return a PCA of the matrix (eigenvalues, explained variance, /// loadings over the traits whose every cell is valid). Off by default: /// the r matrix is worth reading on its own first. @@ -201,6 +206,16 @@ pub async fn correlation_matrix( if let Some(pca) = &pca { body["pca"] = serde_json::to_value(pca).unwrap_or(serde_json::Value::Null); } + let clustering = if wanted.cluster.unwrap_or(false) { + // Refused rather than guessed when a cell is missing: an unknown + // distance treated as 1 would invent a structure and a plot of it. + crate::heatmap::cluster(&matrix.r, crate::pca::MAX_PCA_TRAITS) + } else { + None + }; + if let Some(clustering) = &clustering { + body["heatmap"] = serde_json::to_value(clustering).unwrap_or(serde_json::Value::Null); + } Ok(Json( ctx.envelope(body) .with_note(&format!( @@ -227,6 +242,19 @@ pub async fn correlation_matrix( "Cells with fewer than min_overlap observations are null in r and p, and their \ n still says how many there were.", ) + .with_note(&match (&clustering, wanted.cluster.unwrap_or(false)) { + (Some(clustering), _) => format!( + "Clustering: average linkage on 1 - r, {} merge(s), largest distance {:.3}; \ + `heatmap.order` is the drawing order for both axes.", + clustering.merges.len(), + clustering.max_height + ), + (None, true) => "No clustering: the matrix has a gap (a null cell), so some \ + distances are unknown -- drop those traits and ask again." + .to_string(), + (None, false) => "No clustering: pass \"cluster\": true for a heatmap order." + .to_string(), + }) .with_note(&match &pca { Some(pca) if pca.components.is_empty() => format!( "PCA: not computed -- {} trait(s) were usable and it needs at least 2, and \ @@ -448,6 +476,7 @@ mod tests { method: None, corr_samples_group: None, min_overlap: None, + cluster: None, pca: None, }; // build() would go to the database; the arithmetic is what is tested diff --git a/src/routes/plot.rs b/src/routes/plot.rs index fd56abc..2b4c043 100644 --- a/src/routes/plot.rs +++ b/src/routes/plot.rs @@ -817,6 +817,103 @@ pub async fn plot_pca( Ok(svg_response(rendered)) } + +#[utoipa::path(post, path = "/plot/heatmap", + summary = "Draw the clustered heatmap of a correlation matrix, as an SVG", + description = "Post the response of POST /compute/correlation/matrix back (as-is) after \ +asking it for `\"cluster\": true`, and get the figure scripts/plot-heatmap.py draws: the r \ +matrix in the average-linkage order, one dendrogram showing why those traits are neighbours, \ +and a diverging colour scale with blue negative and red positive. Nothing is recomputed — the \ +order comes from the reply. image/svg+xml, not the JSON envelope; `x-plot-summary` carries the \ +plotter's one-line summary.", + params(PlotParams), + request_body = serde_json::Value, + responses( + (status = 200, description = "The SVG", body = String, content_type = "image/svg+xml"), + Unauthorized, + (status = 422, description = "The posted body carries no clustered order", body = ApiError), + (status = 502, description = "The plotter failed", body = ApiError) + ) +)] +#[gnauth(token_only)] +pub async fn plot_heatmap( + ctx: Ctx, + _token: AuthToken, + Query(plot_params): Query<PlotParams>, + Json(posted): Json<serde_json::Value>, +) -> Result<Response, ApiError> { + let rid = ctx.request_info(); + if let Err(detail) = check_heatmap_result(&posted) { + return Err(ApiError::new( + StatusCode::UNPROCESSABLE_ENTITY, + "not_a_heatmap_result", + "Not a clustered matrix", + detail, + "plot_heatmap", + ) + .with_request_id(rid)); + } + let config = Config::load(); + let mut extra: Vec<String> = Vec::new(); + if let Some(title) = plot_params.title.as_deref() { + extra.push("--title".to_string()); + extra.push(title.to_string()); + } + let borrowed: Vec<&str> = extra.iter().map(String::as_str).collect(); + let rendered = plot::render( + &config.plot_python, + &config.heatmap_plotter, + std::path::Path::new(&config.gemma_cache_dir), + &posted, + plot_params + .trait_label + .as_deref() + .or(plot_params.title.as_deref()) + .unwrap_or(""), + &borrowed, + ) + .await + .map_err(|error| { + ApiError::new( + StatusCode::BAD_GATEWAY, + "plot_failed", + "The plotter failed", + error.to_string(), + "plot_heatmap", + ) + .with_request_id(rid) + })?; + Ok(svg_response(rendered)) +} + +/// The posted body must carry `heatmap.order` from the matrix endpoint. +fn check_heatmap_result(result: &serde_json::Value) -> Result<(), String> { + let data = result.get("data").unwrap_or(result); + let heatmap = data + .get("heatmap") + .ok_or("the posted body has no `heatmap` object: ask /compute/correlation/matrix for \ + \"cluster\": true first")?; + let order = heatmap + .get("order") + .and_then(|order| order.as_array()) + .ok_or("`heatmap.order` is missing")?; + if order.len() < 2 { + return Err("a heatmap needs at least two traits".to_string()); + } + let traits = data + .get("traits") + .and_then(|traits| traits.as_array()) + .ok_or("the posted body has no `traits` array")?; + if traits.len() != order.len() { + return Err(format!( + "`heatmap.order` lists {} trait(s) but `traits` has {}", + order.len(), + traits.len() + )); + } + Ok(()) +} + /// The posted body must carry `pca.components`, from the matrix endpoint. fn check_pca_result(result: &serde_json::Value) -> Result<(), String> { let pca = result |
