Permutation Tests That Rerun The Clustering Pipeline

Why the Entire Pipeline Belongs in the Test

A marker gene can look unusually different between a cluster and the remaining cells partly because the same expression data helped select the genes, form the clusters, and test the differences. A test that treats the final cluster labels and selected genes as if they had been specified independently omits those opportunities for selection. The issue is not resolved by permuting only the final labels while leaving the selected genes and clusters unchanged.

A full-pipeline permutation test instead asks how large a marker statistic would be when the same search procedure is applied to data transformed under a specified null hypothesis. For every permitted transformation, the analysis repeats all data-adaptive steps: preprocessing that depends on the data, feature selection, clustering, and marker testing. The statistic summarizes the strongest claim the pipeline can produce, so the observed result is compared with the strongest results from complete reruns.

This test does not have a universal permutation recipe. Its validity depends on a null hypothesis and transformations that make the observed data and transformed data comparable under that null. The transformation scheme is part of the statistical model, not a computational convenience.

Define the Pipeline and Its Test Statistic

For a concrete version, let \(T_{ck}(X)\) be the test statistic for gene \(k\) in cluster-versus-rest contrast \(c\), where \(c\) ranges over the contrasts produced by the pipeline. A two-sided maximum statistic is

Here \(\mathcal{S}(X)\) is the set of contrasts and genes that the pipeline actually selects or reports for input \(X\). If the intended claim is directional and the direction is specified in advance, a one-sided maximum may be suitable instead. The choice must be made before examining the permutation results. Taking the maximum makes the statistic sensitive to the strongest result across the pipeline’s search; it does not itself correct for any search steps that are left out of the rerun.

A pipeline needs deterministic conventions for such cases as ties in feature selection, cluster-label naming, empty clusters, or zero estimated variance. One solution is to use fixed tie-breaking rules and define in advance how undefined marker statistics are handled. Cluster labels are arbitrary names, so the statistic should not depend on whether a clustering algorithm calls a group “1” or “2.” For example, a maximum over all cluster-versus-rest contrasts is unchanged by merely renaming the clusters.

Null Invariance and the Randomization Test

A standard sufficient condition for a finite-sample randomization test uses a group of transformations. Let \(\mathcal{G}\) be a finite group acting on the possible data matrices: each \(g\in\mathcal{G}\) maps a matrix \(X\) to \(gX\), the identity leaves \(X\) unchanged, and compositions and inverses remain in the group. The null hypothesis must imply invariance under this action: for every \(g\in\mathcal{G}\), \(gX\) has the same null distribution as \(X\). This is a substantive assumption about the data under the null, not something established by seeing a similar result in a few permutations.

For each transformed matrix, apply the same complete pipeline and calculate \(D(gX)\). If every group element can be enumerated, the exact upper-tail randomization p-value is

The identity transformation is included, so the observed statistic is included in the reference set. The “greater than or equal to” comparison handles ties conservatively: ties count against rejection. Under the stated group action and null invariance, the observed data are uniform over their transformation orbit under the null. Consequently, the rank of the observed statistic among the orbit statistics is valid; using the upper tail with ties cannot make the test anti-conservative. The attainable p-values are discrete, especially when the group is small.

When full enumeration is too costly, draw \(B\) transformations independently and uniformly from \(\mathcal{G}\), with replacement, and rerun the full pipeline for each. Under the same invariance conditions, the observed statistic and the independently transformed statistics have exchangeable ranks. A valid Monte Carlo p-value is

The plus one accounts for the observed statistic and avoids reporting a zero p-value when none of the sampled statistics exceeds it. This justification depends on uniform sampling from the group and null invariance. Merely collecting transformations that each seem plausible, or showing that each transformation separately preserves the marginal distribution of \(D(X)\), is not sufficient to establish exchangeable ranks.

What Must Be Rerun—and What Must Be Fixed

A rerun must repeat any step whose output would change if the transformed data changed. This usually includes data-driven feature ranking and filtering, the choice of clustering features, the clustering itself, and the marker tests. If a tuning parameter or cluster count was selected by inspecting the same data, that selection must also be repeated if it is part of the procedure being assessed. Otherwise, the null reference distribution represents a narrower search than the observed analysis.

Some choices can remain fixed when they were specified independently of the data or are fixed by the design. Examples include an externally defined set of eligible genes or a prespecified preprocessing rule. The distinction is whether a choice is part of the adaptive search being tested, not whether it is computationally convenient to hold it fixed. If clustering or another algorithm uses randomness, use a deterministic implementation or specify how algorithmic randomness is handled consistently in both the observed and transformed analyses.

Transformations must also match the null claim. As one illustrative scheme, independently permuting cell order within each gene preserves each gene’s observed values while breaking their alignment across cells. This corresponds to a strong null of invariance to those separate permutations; it does not automatically test every scientific claim of “no biologically meaningful clusters.” A transformation that preserves unwanted signal, destroys relevant nuisance structure, or violates the stated null can produce a reference distribution for the wrong question.

Justification, Diagnostics, and Alternatives

The rank argument explains why the full rerun matters. Under the null, invariance makes the observed data and its uniformly transformed versions comparable over the group orbit. Applying the same deterministic pipeline to each matrix gives a corresponding set of pipeline statistics. Because every version undergoes the same search, the observed statistic is ranked against the search results that the null procedure itself can generate. If instead only the final marker test is rerun, the reference values do not include the search that produced the observed marker.

Several practical checks help reveal problems, although none proves invariance. Confirm that the identity transformation reproduces the observed pipeline result and that every transformation uses the same code, stopping rules, and tie handling. Inspect how often reruns fail, return too few cells in a cluster, or produce undefined test statistics. A rule for such outcomes must be specified consistently rather than dropping inconvenient permutations after seeing their results. For Monte Carlo tests, report \(B\) and the exceedance count; if the p-value is near the decision threshold, increase \(B\) to reduce simulation uncertainty.

Compare the rerun outputs as well as their final maximum: sharp changes in selected genes or cluster structure can indicate that the selection process is highly variable. Such variability is exactly why a frozen-pipeline reference may be misleading, but it does not validate the transformation scheme. The main alternatives answer different questions. A fixed-cluster marker test treats labels as given and does not account for adaptive clustering. Selective-inference methods condition on a specified selection event and require a suitable model for that event. Sample splitting or independent validation separates discovery from confirmation but uses data differently. A full-pipeline permutation test is attractive when the complete analysis can be rerun and a credible invariance null can be stated; it is not a substitute for that null or a universal remedy for dependence and confounding.

A common mistake is to say, “Each permutation preserves the data distribution, so the observed and permuted statistics have exchangeable ranks.” That reasoning is incomplete. Separate distributional invariance statements do not specify a coherent group action or a sampling scheme for the transformed statistics. To justify the rank test, specify sufficient conditions such as a group acting on the data, null invariance under that group, and uniform group transformations; alternatively, establish exchangeability of the observed and sampled statistics directly. If those conditions are not credible, the calculated tail proportion need not be a valid p-value for the scientific null.