Find a Balanced Two-Way Partition via Hierarchical Clustering

Performs hierarchical clustering on a distance matrix and cuts the dendrogram into two groups. A partition is considered "balanced" if both groups contain at least max(3, ceiling(n * min_group_frac)) samples. For balanced partitions, the average silhouette width is computed to quantify separation quality.

Usage

find_partition_hclust(dist_mat, min_group_frac = 0.25)

Arguments

dist_mat: A dist object representing pairwise distances between samples. Typically obtained from a module similarity matrix via as.dist(1 - sim_mat).
min_group_frac: Numeric value between 0 and 0.5 specifying the minimum fraction of total samples required in each group. The actual minimum group size is max(3, ceiling(n_samples * min_group_frac)). Default: 0.25.

Value

A list with:

groups: Named integer vector of group assignments (1 or 2), one per sample. NULL if no balanced partition was found.
silhouette: Average silhouette width (higher = better separation). NA if the partition is imbalanced.
hclust: The hclust object, which can be passed to pheatmap for consistent dendrogram ordering.
balanced: Logical indicating whether a balanced partition was found.

Details

This function is used in MOSAIC's subgroup detection pipeline to test whether a feature module defines meaningful patient subtypes: compute a module similarity matrix with compute_module_similarity, convert to distance, and test for a balanced partition here.

Examples

if (FALSE) { # \dontrun{
# Compute module similarity
sim_mat <- compute_module_similarity(
  result$mosaic_embed_list,
  feature_idx = which(feature_clusters == module_id)
)

# Test for subgroups
partition <- find_partition_hclust(as.dist(1 - sim_mat))

if (partition$balanced) {
  cat("Silhouette:", partition$silhouette, "\n")
  cat("Group sizes:", table(partition$groups), "\n")

  # Visualize
  plot_mds_cluster(sim_mat, "Subgroups",
                   cluster = partition$groups)
}

# Permutation test for significance
n_perm <- 1000
null_sils <- numeric(n_perm)
for (p in seq_len(n_perm)) {
  rand_idx <- sample(total_features, length(module_idx))
  rand_sim <- compute_module_similarity(projected_list, rand_idx)
  rand_part <- find_partition_hclust(as.dist(1 - rand_sim))
  null_sils[p] <- ifelse(rand_part$balanced, rand_part$silhouette, 0)
}
pval <- (sum(null_sils >= partition$silhouette) + 1) / (n_perm + 1)
} # }