about summary refs log tree commit diff
path: root/src
diff options
context:
space:
mode:
authorPjotr Prins <pjotr.public01@thebird.nl>2026-11-16 17:17:11 +0000
committerPjotr Prins <pjotr.public01@thebird.nl>2026-11-16 17:17:11 +0000
commitea3dd926211e8db4a0d7d3739a606440b888e8b0 (patch)
tree31b58cd0126960e70a76e45dc2c3b7c9a1c6d0b6 /src
parent33e837e771e07936c808fb3aeb3540525691718c (diff)
downloadgenenetwork4-main.tar.gz
correlation matrix: clustered heatmap and its plot HEAD main
`"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.rs8
-rw-r--r--src/heatmap.rs214
-rw-r--r--src/lib.rs2
-rw-r--r--src/routes/correlation_matrix.rs29
-rw-r--r--src/routes/plot.rs97
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