Quantifying Root Uncertainty on an MST

Why Root Choice Needs a Sensitivity Analysis

An MST gives a connected tree of cells, but an unrooted tree does not specify which cell represents the start of a biological process. Assigning pseudotime requires a root: each cell’s time is calculated along its path from that root. When the starting state is uncertain, choosing one plausible cell and reporting only the resulting pseudotime can make a root-dependent ordering look definitive.

This tutorial measures that dependence while holding the inferred tree fixed. The question is not which root is biologically correct; it is how much the resulting paths, distances, and cell orderings vary over a stated set of plausible roots. This conditional analysis does not capture uncertainty in the tree itself, its edge weights, or the choice of cells.

The earlier material on assigning pseudotime along an MST establishes this distance-based assignment. Here the essential change is to calculate it for more than one root. Use the same tree, edge lengths, cell-to-tree mapping, and pseudotime convention for every candidate. Otherwise, differences cannot be attributed to root choice alone.

If pseudotime is rescaled to run from zero to one, do that separately and explicitly for each root. For example, one common rescaling is \(\tilde{\tau}_r(v)=\tau_r(v)/\max_{u\in V}\tau_r(u)\), provided the maximum is positive. Raw and rescaled values answer different questions: raw distances retain the tree’s length units, while rescaled values express position relative to the farthest cell from each root. Do not compare them as if they were interchangeable.

Summarizing Root-Induced Variation

For each cell, the simplest summary is the range of its pseudotime over the candidate roots. If the candidate roots have prespecified plausibility weights \(q_r\), where \(q_r\geq 0\) and \(\sum_{r\in R}q_r=1\), a weighted mean and standard deviation can summarize the values. The weights encode the analyst’s stated plausibility assessment; unless they come from a defined probabilistic model, they are not probabilities that the roots are biologically true.

The range is \(\max_{r\in R}\tau_r(v)-\min_{r\in R}\tau_r(v)\). These are descriptive sensitivity summaries, not confidence intervals: they do not quantify sampling uncertainty or assign coverage to an unknown parameter. Report them with the candidate-root set and the pseudotime units. Also inspect cell ordering. Two roots can give similar distances for a cell while reversing its order relative to another cell.

Calculating Cell-Level Sensitivity

The following table gives the full distance calculation for the same hypothetical tree. For each entry, add the edge lengths on the unique path from the listed root. The two root choices are given equal weight only for illustrating a weighted summary.

For instance, A’s distance from E follows A–B–C–E, so \(\tau_E(A)=1+2+1=4\). The equal-weight mean is \((0+4)/2=2\), and its range is \(4-0=4\). A mean across roots is a compact summary, not necessarily a pseudotime that corresponds to any single valid root or rooted traversal. Here A and E both have mean 2, even though each is at time zero under one root and time four under the other.

How Root Choice Changes Ordering

Pseudotime is often used to order cells, so distance summaries alone can miss important changes. For example, under root A, B precedes C because \(\tau_A(B)=1<3=\tau_A(C)\). Under root E, C precedes B because \(\tau_E(C)=1<3=\tau_E(B)\). This reversal is a direct warning against presenting one ordering as insensitive to root choice.

One useful diagnostic is to compare pairwise orderings across candidate roots. For each pair of cells, record whether \(\tau_r(u)<\tau_r(v)\), whether the ordering reverses across roots, and whether either root produces a tie. A global rank-correlation summary can also be reported when there are many cells, but it does not identify which branch or cells drive disagreement. Pairwise reversals and per-cell ranges help locate the sensitivity.

A Short Justification for the Distance Calculation

The sensitivity calculation rests on two simple facts: the graph is a tree, and its edge lengths are nonnegative. A tree has exactly one path between any two vertices. Therefore each candidate root defines one unambiguous route to each cell. Summing the edge lengths along that route gives the root-to-cell distance used for pseudotime.

For a change of root from \(r\) to \(s\), the distance difference can be understood by comparing their paths to \(v\). Any shared segment contributes to both sums and cancels when the distances are subtracted. The nonshared segments determine the change. In the example, the paths from A and E to F share E–F, but the A-root path also includes A–B–C–E. Thus \(\tau_A(F)-\tau_E(F)=(1+2+1+2)-2=4\) distance units, exactly the length of the extra segment from A to E.

This argument also clarifies the scope of the result. It justifies comparing distances on a fixed tree; it does not justify the candidate roots, the edge weights, or the tree as a model of biological progression.

Practical Workflow, Diagnostics, and Alternatives

Several failures are detectable. A candidate outside the tree’s connected component has no finite path distance to the other cells, so it cannot be included in this comparison without first resolving the disconnected representation. A zero maximum distance makes max-rescaling undefined. Very large ranges concentrated on one branch suggest that the root choice particularly affects that branch. If all candidate roots produce identical pseudotimes for a cell, its distance is insensitive within the chosen candidate set, but that does not prove the set includes all plausible roots.

A single prespecified root is simpler and appropriate when independent biological evidence strongly supports it, but it hides sensitivity if plausible alternatives exist. Reporting every candidate-root result is transparent for a small set. For many candidates, ranges, weighted summaries, and ordering comparisons provide compact descriptions, as long as the underlying candidate set and weights remain available. A consensus or average pseudotime can be convenient for visualization, but averaging does not generally produce a valid root-to-cell distance system for any actual root.

Common Mistake and Limitations

A common mistake is to interpret a weighted average across roots as the cell’s expected biological time, or to treat plausibility weights as posterior probabilities without a probabilistic model. The correction is to call these quantities root-sensitivity summaries, state the weights and their source, and avoid biological interpretations that the calculation does not support.

Root sensitivity is conditional on the chosen MST and its edge lengths. It does not account for uncertainty in how the tree was constructed, whether an edge is spurious, or whether a different geometric representation would be more appropriate. Nor does pseudotime, by itself, establish elapsed clock time, causation, or a unique biological direction. If roots are plausible in different components, or if the candidate set excludes a credible start state, the summary can be incomplete or undefined. Interpret the results alongside the evidence used to define plausible roots.