From Cell Profiles to a Weighted Graph
A trajectory representation begins with a geometric choice: each cell is represented by a profile in a chosen coordinate space, and distances or other dissimilarities between profiles can be used to weight graph edges. A minimum spanning tree (MST) gives a connected, branching structure that includes every represented cell while minimizing the sum of its edge weights. It is a graph construction, not by itself evidence that the edges are biological lineage relationships.
For this tutorial, assume there are finitely many cells and that a fixed, undirected candidate graph specifies which cell pairs may be joined. Each candidate edge has a finite real-valued weight, usually a nonnegative distance or dissimilarity. The graph and weights are treated as given during construction. The choice of representation, distance, and candidate edges affects the result; the calculation cannot resolve whether those choices capture the relevant biology.
If the candidate graph includes every pair of cells, it is the complete graph. A complete graph on \(n\) cells has an edge for each of the \(n(n-1)/2\) distinct pairs. In practice, a candidate graph may instead retain only a subset of pairs. An MST is defined only if the graph being considered is connected: otherwise, no set of its edges can connect all vertices. A connected graph with \(n\) vertices has a spanning tree with \(n-1\) edges.
Kruskal’s Algorithm
Kruskal’s algorithm constructs an MST by considering edges from smallest weight to largest. It accepts an edge if adding it would not create a cycle in the edges already accepted; otherwise it rejects that edge. The procedure stops when the accepted edges connect all vertices. If weights are tied, tied edges may be processed in either order. Different valid choices can produce different MSTs with the same minimum total weight.
Order all edges by nondecreasing weight. Record how ties are handled, since the particular tree may depend on their ordering.
Accept an edge if its endpoints are in different connected components of the accepted-edge graph. Reject it if its endpoints are already connected, because adding it would make a cycle.
At that point, if the accepted-edge graph is connected, it is a spanning tree. If all candidate edges are exhausted before the vertices are connected, the candidate graph is disconnected and has no spanning tree.
The key decision is not simply whether an edge is short: it is whether the edge joins two components that are not yet connected. A short edge within one component would close a cycle and add no connection between components.
Worked Example: Constructing a Tree from Four Cells
Suppose four hypothetical cell profiles, A, B, C, and D, have the following pairwise distances. The candidate graph is complete, so every pair is available.
| Pair | Distance |
|---|---|
| A–B | 1 |
| A–C | 4 |
| A–D | 5 |
| B–C | 2 |
| B–D | 3 |
| C–D | 1 |
Sort the edges: A–B (1), C–D (1), B–C (2), B–D (3), A–C (4), and A–D (5). Accept A–B and C–D; they form two components, \(\{A,B\}\) and \(\{C,D\}\). The next edge, B–C, joins those components, so accept it. There are now \(n-1=3\) accepted edges and all four cells are connected.
The total weight is
The remaining edges each have endpoints already connected through accepted edges, so adding any of them would create a cycle. The resulting tree includes every cell, is connected, and has no cycle.
Why the Greedy Construction Is Minimum
The cycle check preserves the possibility of connecting components without redundant edges. The minimum-weight choice also ensures that an accepted edge does not make the best possible total weight worse. The following exchange argument justifies the rule, including when there are tied weights.
This argument assumes a connected graph and finite edge weights. It does not require all weights to be distinct. With ties, the inequality \(w(e)\leq w(f)\) still holds, although more than one minimum spanning tree may be possible.
Worked Example: Respecting a Candidate Graph
Suppose five hypothetical cells have a supplied candidate graph with these edges and weights: A–B (0.8), B–C (0.9), A–C (1.1), C–D (1.4), D–E (1.6), and C–E (2.0). These are the only permitted edges; other cell pairs are not candidates.
Process the edges in order. Accept A–B (0.8) and B–C (0.9). Reject A–C (1.1), because A and C are already connected by A–B and B–C; accepting A–C would create a cycle. Accept C–D (1.4), then D–E (1.6). The resulting four edges connect all five cells without a cycle.
The total weight is
The construction is an MST of this candidate graph. It is not necessarily the MST of the complete graph on these cells, because excluded pairs could provide cheaper ways to connect some cells. Restricting candidate edges changes the set of trees over which the total weight is minimized.
Worked Example: Detecting a Disconnected Candidate Graph
Consider four hypothetical cells A, B, C, and D. Suppose the candidate graph contains only A–B with weight 0.7 and B–C with weight 1.0; D has no candidate edge. The graph has two components, \(\{A,B,C\}\) and \(\{D\}\). Kruskal accepts both available edges, but it cannot connect D.
A spanning tree on four cells would require \(4-1=3\) edges, but only two candidate edges exist, and no edge crosses from D to the other component. Therefore this candidate graph has no spanning tree. Calling the two accepted edges an MST would be incorrect: they form a spanning forest, not a spanning tree.
For comparison, suppose the complete graph also supplies C–D with weight 1.5, A–D with weight 2.1, A–C with weight 1.8, and B–D with weight 2.3. Kruskal on that complete graph accepts A–B (0.7), B–C (1.0), and C–D (1.5). These connect all four cells, giving a tree with total weight
The bridge C–D makes a spanning tree possible because it connects the previously separate cell D to the other cells. In an analysis, a disconnected candidate graph should be recognized as such rather than silently repaired by treating a non-candidate pair as an available edge.
Checks, Alternatives, and Limitations
After constructing a tree, verify the result directly. For \(n\) vertices, the accepted graph should have \(n-1\) edges, be connected, and contain no cycle. Also check that every accepted edge was permitted by the candidate graph and that the listed total equals the sum of its edge weights. These checks catch bookkeeping errors, such as stopping too early or accepting an edge that closes a cycle.
A complete-graph MST considers every pair, while an MST on a sparse candidate graph can use only the supplied subset. The complete graph avoids excluding a pair before tree construction, but may require handling many more edges. A sparse graph can reduce computation and encode a neighborhood restriction, but it can be disconnected or can force a different, heavier tree. This tutorial treats the candidate graph and weights as fixed; the choice of edge weights is a separate modeling decision.
An MST can contain vertices with more than two incident edges, so it can represent branching where a single principal curve may be inadequate, as discussed in the earlier material on principal curves and branches. But the tree remains a geometric summary of the supplied profiles and weights. It does not, on its own, establish temporal direction, identify a root, or prove that a branch is a biological fate. Those interpretations require additional evidence and analysis.
- Long connecting edge: A tree must connect all vertices in a connected candidate graph, so its edges may include a conspicuously long bridge. Inspect whether this reflects a genuine connection, a sparse sampling gap, an outlier, or a candidate-graph artifact.
- Tied weights: Ties may yield multiple minimum trees. Report that the tree is not uniquely determined by the weights when relevant; do not treat one tied-edge ordering as biological evidence.
- Disconnected graph: If edge processing ends with multiple components, report that no spanning tree exists on the specified graph. Do not label the resulting forest a spanning tree.
- Unexamined representation: A mathematically valid MST can still be misleading if the cell coordinates or dissimilarities do not represent the biological variation of interest.
Check Your Understanding
Answer each question, then compare with the solutions below.
- What three properties must a subgraph have to be a spanning tree?
- For four vertices, how many edges does a spanning tree contain?
- Three vertices have edge weights A–B = 1, B–C = 2, and A–C = 2. Which edges does Kruskal accept if it processes A–B first and then B–C? What is the total weight?
- Why is a connected candidate graph required for an MST of all represented cells?
- Does constructing an MST establish that each edge is a biological lineage relationship? Explain.
Solutions. 1. It includes every vertex, is connected, and has no cycle. 2. \(4-1=3\) edges. 3. It accepts A–B and B–C, which connect all three vertices without a cycle; the total weight is \(1+2=3\). The remaining edge A–C would create a cycle. 4. A spanning tree must connect every vertex using edges in the candidate graph; if that graph has separate components, no permitted edge can connect them. 5. No. An MST minimizes the supplied weights on the specified graph; interpreting edges as biological relationships requires further evidence.