Assigning Pseudotime Along an MST Path

From a Rooted Tree to Pseudotime

A minimum spanning tree (MST) connects the cells or trajectory nodes in a connected graph without cycles, using selected edge weights. Once a root is specified, the tree gives each cell a unique route from that root. Assigning pseudotime along the MST means summarizing each cell’s position along its root-to-cell route. The calculation is straightforward; its interpretation depends on what an edge represents and how its weight was chosen.

Here, consider a fixed, connected MST with root \(r\). Each edge \(e\) has a positive length \(w_e\), measured in the distance or embedding units used to construct the tree. The root is assumed to be specified independently of the distance calculation. A cell may be an MST vertex, or it may lie partway along an edge if cells have been projected onto a trajectory skeleton.

Definition: The root-to-cell path for cell \(v\) is the unique path in the tree from root \(r\) to \(v\). Its edge-count distance, \(d_{\mathrm{count}}(v)\), is the number of edges on that path. Its edge-length distance, \(d_{\mathrm{length}}(v)\), is the sum of the weights of those edges. A rescaled path-based pseudotime divides one of these distances by its maximum over the cells being considered, so that the root has value 0 and the most distant cell has value 1.

For an edge-length distance, the units are those of the edge weights. Edge-count distance is measured in numbers of edges. These are distinct summaries: one counts steps in the chosen graph representation, while the other accumulates the lengths assigned to those steps. Neither is automatically elapsed time. Pseudotime orders cells relative to a root according to a chosen trajectory representation.

d_{\mathrm{count}}(v)=\sum_{e\in P(r,v)}1, \qquad d_{\mathrm{length}}(v)=\sum_{e\in P(r,v)}w_e, \qquad \tau(v)=\frac{d(v)}{\max_{u\in V}d(u)}

Here \(P(r,v)\) is the set of edges on the root-to-\(v\) path, \(V\) is the set of cells or trajectory nodes being assigned pseudotime, and \(d\) denotes the chosen distance. The last formula defines a separate rescaling for each chosen distance. Because all edge weights are positive, the root has distance zero and, for any parent-to-child edge, the child’s distance exceeds its parent’s by that edge’s contribution. If the tree has only one node, the maximum distance is zero, so this normalization is undefined; report that the tree has no non-root path rather than dividing by zero.

Calculating Distances Along Branches

A root establishes direction away from the root, but a branching tree does not provide one total order for all cells. Cells on different branches can have equal distances or be incomparable in the branching structure. A scalar pseudotime records root distance; it does not say which branch a cell follows. For interpretation, retain branch membership or the relevant path as well as the scalar value.

Worked Example: Comparing Edge Counts and Edge Lengths

Suppose a hypothetical rooted tree has a path \(r\to a\to b\), with edge lengths 1 and 2, and two outgoing edges from \(b\): \(b\to c\) of length 3 and \(b\to d\) of length 5. The cells are the four non-root vertices \(a,b,c,d\), together with root \(r\).

The edge-count distances are 0 at \(r\), 1 at \(a\), 2 at \(b\), and 3 at both \(c\) and \(d\). The edge-length distances are \(0\), \(1\), \(1+2=3\), \(1+2+3=6\), and \(1+2+5=8\), respectively.

The maximum edge count is 3, so rescaled edge-count pseudotimes for \(r,a,b,c,d\) are \(0\), \(1/3\), \(2/3\), \(1\), and \(1\). The maximum edge length is 8, so rescaled edge-length pseudotimes are \(0\), \(1/8\), \(3/8\), \(6/8\), and \(1\). Thus \(c\) and \(d\) tie under edge count even though their weighted path distances differ. These values describe positions on this hypothetical tree, not time in biological units.

The edge-length sum is often useful when the weights represent geometric distances in a cell-state embedding. But the interpretation is conditional on that geometry and those weights. If weights are transformed similarities, inverse similarities, or another edge cost, the accumulated sum has those chosen cost units; it should not be called geometric arc length without justification.

Why Edge Count Depends on Representation

Edge count is sensitive to how finely a trajectory is divided into edges. Subdividing an edge creates more steps without changing the underlying geometric path. If all edges represent equally meaningful transitions, counting them may be useful. If vertices arise simply from computational resolution, equal weight per edge can give a misleading sense of relative progress.

Worked Example: Subdivision Changes Edge-Count Pseudotime

Consider a hypothetical path \(r\to a\to b\), with lengths 9 from \(r\) to \(a\) and 1 from \(a\) to \(b\). The edge-count distances are 0, 1, and 2, so normalized values for \(a\) and \(b\) are \(1/2\) and 1. The edge-length distances are 0, 9, and 10, giving normalized values \(9/10=0.9\) and 1.

Now represent the same geometry by dividing the length-9 edge into nine edges of length 1, leaving the length-1 edge unchanged. The distance to \(a\) is now 9 edges out of 10 total, so its normalized edge-count value changes from \(1/2\) to \(9/10=0.9\). Its edge-length distance remains 9 out of 10, or 0.9. This calculation shows why edge count can change when a graph is refined even if the path geometry and total length remain fixed.

The result does not mean edge count is always inappropriate. It means the analyst must know what the vertices and edges represent. In a compressed trajectory skeleton, one edge may summarize a long segment; counting that as one step treats it like every other edge, regardless of its represented length.

Rescaling and Cells Within Edges

Rescaling expresses distance as a fraction of the largest root distance in the specified set. It preserves the ordering of distances within that set, because dividing all nonnegative distances by the same positive constant cannot reverse their order. It removes measurement units, but it does not make two different trees, roots, or edge-weight choices equivalent. A value of 0.5 means half the maximum assigned path distance under that particular construction, not half of a known biological process.

If a cell is located within an edge, use its fractional position on that edge rather than rounding it to an endpoint. Let the edge run from parent \(p\) to child \(q\), and let \(\lambda\) be the fraction of its length from \(p\) to the cell, where \(0\leq\lambda\leq1\). Add \(\lambda w_{pq}\) to the parent’s edge-length distance. For a fractional edge-count distance, add \(\lambda\) to the parent’s edge-count distance. This treats position along the edge as linear in the chosen edge coordinate.

d_{\mathrm{length}}(v)=d_{\mathrm{length}}(p)+\lambda w_{pq}, \qquad d_{\mathrm{count}}(v)=d_{\mathrm{count}}(p)+\lambda

Worked Example: Interpolating a Projected Cell

Suppose a hypothetical tree has root \(r\), an edge \(r\to a\) of length 2, an edge \(a\to b\) of length 6, and a branch \(r\to c\) of length 5. A projected cell \(x\) lies one-third of the way from \(a\) to \(b\), so \(\lambda=1/3\) on that edge.

The parent distance to \(a\) is 2. Therefore \(x\)’s edge-length distance is \(2+(1/3)(6)=4\). Its fractional edge-count distance is \(1+1/3=4/3\). The complete edge-length distances are 0 at \(r\), 2 at \(a\), 8 at \(b\), 5 at \(c\), and 4 at \(x\); the maximum is 8. Thus the rescaled edge-length pseudotime for \(x\) is \(4/8=0.5\), while that for \(c\) is \(5/8=0.625\).

For edge count, the distances are 0, 1, 2, 1, and \(4/3\), respectively, with maximum 2. The rescaled edge-count pseudotime for \(x\) is \((4/3)/2=2/3\). The different values arise because the two metrics measure different things: \(x\) is one-third of the way along the second edge, but that edge accounts for most of the total geometric distance.

Assumptions, Diagnostics, and Limitations

The calculations assume that the tree is connected, that a root has been chosen, and that the edge weights or edge positions are defined consistently. A tree’s unique root-to-cell path makes the sum unambiguous. Positive edge lengths ensure that distance increases strictly from parent to child; zero-length edges can produce ties along a path. If cells occupy vertices, edge counts are integers; if they are projected into edges, fractional counts require the interpolation convention above.

Check the assignment before interpreting it:

Confirm the root is on the same connected tree as every cell being assigned. Distances from that root are not defined for cells in a disconnected component.
Check that each cell’s path follows the intended branch and that the edge weights are finite and in the intended units.
Compare edge-count and edge-length values. Large disagreements can reveal unequal edge lengths or sensitivity to graph resolution.
Verify that the root has distance zero, each child’s distance equals its parent’s distance plus the edge contribution, and normalized values lie between 0 and 1.
Inspect branch labels alongside pseudotime. Equal distances on distinct branches do not imply that cells share the same state or fate.

A frequent mistake is to interpret normalized pseudotime as a calibrated measure of elapsed time: for example, to claim that a cell at 0.5 is halfway through differentiation. The calculation only establishes that the cell’s chosen path distance is half the largest root distance in the selected tree. A second mistake is to assume edge-count pseudotime is unaffected by adding intermediate vertices. The subdivision example shows otherwise; edge-length distance is unchanged there only because the subdivided lengths sum to the original edge length.

Edge count is simple and avoids dependence on the numerical scale of edge weights, but it gives every edge equal contribution. Edge length incorporates weights and can reflect geometric distance, but depends on the embedding, distance metric, and construction of the tree. Rescaling either distance makes it unitless and convenient for plotting, but does not correct a poor tree or an unsuitable metric. A principal curve instead assigns position along a fitted continuous path and is appropriate to a different trajectory representation; an MST provides explicit branches but can be sensitive to its graph construction. No one summary removes uncertainty in the root or the trajectory itself.

Key takeaway: State the root, tree, edge-weight definition, distance metric, and rescaling set whenever reporting MST pseudotime. Edge count measures steps; edge length accumulates edge weights; rescaling expresses either as a fraction of its maximum. All are relative path coordinates, not elapsed time by themselves.

Check Your Understanding

Answer each question, then compare with the solutions below.

A rooted path has edge lengths 2, 2, and 6. What are the edge-count and edge-length distances at the second vertex, and the corresponding distances at the terminal vertex?
Why can inserting intermediate vertices change normalized edge-count pseudotime without changing the geometric path?
A cell lies halfway along an edge of length 4. Its parent is at edge-length distance 3 and edge-count distance 2. Find both distances for the cell.
What does a rescaled edge-length pseudotime of 0.4 mean, and what does it not establish?

Solutions. (1) At the second vertex, two edges have been traversed, so edge-count distance is 2; edge-length distance is \(2+2=4\). At the terminal vertex, edge-count distance is 3 and edge-length distance is \(2+2+6=10\). (2) Each inserted edge adds one to the step count, changing the denominator and possibly the numerator of the normalized count, even when the sum of geometric edge lengths is unchanged. (3) Here \(\lambda=1/2\). The edge-length distance is \(3+(1/2)(4)=5\); the fractional edge-count distance is \(2+1/2=2.5\). (4) It means the cell’s root-to-cell edge-length distance is 0.4 times the maximum such distance in the selected set. It does not establish that 40% of biological time has elapsed or that the cell is at a fixed fraction of a biological process.