Pruning Spurious MST Branches

Why Pruning Requires More Than a Short Edge

A minimum spanning tree (MST) connects cells in a tree using the selected cell-to-cell geometry and edge weights. After compression into a trajectory skeleton, a small number of paths and junctions summarize the tree. Some terminal paths may arise from noise, outlying cells, or local sampling irregularities. Removing such a path can make a trajectory easier to interpret, but a pruning rule can also erase a real, weakly sampled cell state. The decision is therefore about the reliability of a branch under an explicit rule, not proof that the branch is biologically unreal.

The earlier material on compressing cell MSTs into trajectory skeletons supplies the representation used here: a skeleton retains the tree's principal paths and junctions while summarizing the original cell-level MST. This tutorial focuses on assessing terminal branches in that representation. It does not assign developmental time or determine a branch's biological identity.

The definition depends on the representation. If the skeleton stores a compressed edge as a path through multiple original MST edges, its weight must represent the sum of those original edge lengths, not merely the straight-line distance between its endpoints, if the goal is to measure length along the tree. Likewise, count original cells mapped to the branch, not the number of skeleton vertices: compression can represent many cells with a single segment.

A basic length-and-count rule uses two cutoffs, \(L_{\min}\) and \(n_{\min}\). A conservative version flags a branch only if it is both short and sparsely supported:

This is a deterministic screening rule, not a statistical test. \(L_{\min}\) has the units of the edge weights, while \(n_{\min}\) is a number of cells. The rule makes sense only after the geometry, edge-weight definition, cell-assignment procedure, and cutoffs have been specified. If the embedding is rescaled, length cutoffs must be rescaled too.

Why Length and Cell Count Are Complementary

Branch length and cell count describe different features. Length asks how far the path extends in the selected geometry. Cell count asks how many observed cells support its exclusive portion. A short path with many cells might be a compact but well-populated state. A long path with few cells could be an outlying extension, or a genuine but rare state. Neither measure alone resolves that ambiguity.

The AND rule above is cautious: a branch must be short and sparsely populated to be removed. An alternative OR rule removes a branch if either condition is met. The OR rule is more aggressive because every branch meeting either criterion is eligible for pruning. These rules answer different tolerance-for-error questions; neither is universally correct.

Justification and Assumptions

The length calculation follows from the definition of path length in a weighted tree. In a tree there is a unique path between the attachment junction and the leaf. If that path contains edges \(e_1,\ldots,e_k\), and each edge has a nonnegative weight \(w(e_i)\) representing distance along the tree, then its total length is the sum of those edge lengths:

This sum is appropriate because each successive edge contributes another segment to the path. It is not generally appropriate to substitute the direct distance between the branch endpoints: that chord can be shorter than the route along the tree, and it ignores intermediate curvature or detours. Under the AND rule, pruning follows directly from two comparisons. If \(L_b \leq L_{\min}\) and \(n_b \leq n_{\min}\), both screening conditions are met; if either inequality fails, the branch is retained by that rule.

Interpretation requires several assumptions and checks. The inferred structure must be a tree, the skeleton must preserve the intended branch paths, and the edge weights must be comparable along those paths. Cell assignments to branches must be well-defined and count each original cell at most once for a given branch. The chosen embedding and distance measure must be appropriate for the scientific question. If an edge weight is a transformed dissimilarity without a meaningful additive length interpretation, the sum can still be a chosen score, but should not be described as geometric path length.

Threshold Sensitivity and Diagnostics

A pruning decision can change when a cutoff changes slightly. Rather than present one threshold pair as uniquely correct, examine a small, scientifically plausible range of values. For each pair, record which branches are flagged and whether the retained skeleton's important junctions and paths change. Report the threshold units, cell-count definition, rule (AND or OR), and the range over which the interpretation remains stable.

A useful diagnostic table can show each branch's length and count alongside the decision under several threshold pairs. A branch close to a cutoff deserves particular attention: a small change in the cutoff, cell assignment, or edge weights could reverse its classification. Also inspect whether apparent support comes from a few highly isolated cells or whether the branch is represented across a coherent stretch of the path. Such inspection can inform interpretation, but it should not silently replace the stated rule.

Alternatives, Limitations, and Common Mistakes

Pruning is not the only defensible choice. Keeping all branches avoids deleting a possible rare state, but leaves potentially noisy terminal paths in the skeleton. An AND rule is a conservative screen requiring evidence from both length and cell count; an OR rule is more aggressive and can remove a long but poorly populated path or a short but densely populated one. A researcher can also defer pruning and present a sensitivity analysis, making the unpruned skeleton and the threshold-dependent alternatives visible. If results change substantially across reasonable thresholds, that instability is itself important to report.

No length-and-count rule identifies biological truth. Cell count depends on sample composition, capture, filtering, and the way cells are assigned to the skeleton. Length depends on the chosen representation and geometry. A genuine state may be rare or occupy a short transition, while an artifact can have many cells. Pruning also changes the tree: it removes the branch's path and cells from the retained skeleton, so conclusions that rely on that branch should be revisited rather than assumed unchanged.

• Mistake: treating a low count as proof of an artifact. A small \(n_b\) means limited observed support, not that the state is false. State the rule's screening interpretation and consider whether rare states are scientifically plausible.
• Mistake: using endpoint chord distance as branch length. This can understate the route along a curved or indirect tree path. Sum the weights along the branch edges when the weights represent additive distances.
• Mistake: reporting cutoffs without units or logic. “Pruned below 0.2” is incomplete. Specify the length units, cell-count cutoff, and whether both criteria or either criterion triggers pruning.
• Mistake: assuming a stable result from one threshold pair. Nearby cutoffs can change the topology. Show which branches are sensitive and avoid presenting the selected pair as a universal standard.