Why Represent a Workflow as a Graph?
A single-cell analysis is a sequence of transformations, but it is rarely just one long sequence. Quality-control summaries may be computed alongside sample-level metadata checks; a report may combine results from several analyses. A dependency graph makes these relationships explicit. It records which stages require the output of which other stages, so an analyst can determine a valid execution order and trace the consequences of changed inputs.
The graph is useful only when its dependencies reflect the actual computation. If a clustering stage uses a normalized expression matrix and a selected set of highly variable genes, both inputs must be represented. If the graph omits one, it can fail to rerun work that has become outdated. If it includes dependencies that do not exist, it may rerun more of the workflow than necessary.
In a stage-only graph, an edge from preprocessing to analysis means that the analysis consumes preprocessing output. Input files, annotations, parameter files, and software environment specifications can instead be represented as source nodes with edges to the stages that use them. Either representation can work; the essential requirement is that the graph account for all relevant inputs. Throughout, an edge points from a prerequisite toward the stage that depends on it.
Execution Order and the Finite-DAG Result
A topological ordering of a directed graph is a linear ordering of its nodes in which every edge points from an earlier node to a later node. It is a valid sequential schedule: no stage is placed before a prerequisite. A graph may have multiple valid topological orderings because independent stages can be ordered in either way.
The result gives a basis for workflow execution. If a graph has a cycle, the stages in that cycle depend on one another in a way that cannot be satisfied by a sequential ordering. For example, if normalization requires clusters and clustering requires normalized values, the graph contains a cycle; the workflow specification must be clarified or redesigned before execution.
Finding the Stages Affected by a Change
For a changed input or stage \(c\), its downstream set consists of \(c\) and every node reachable from \(c\) by following directed edges. If \(c\) is an input artifact, the stages in this set are the stages whose results may be affected. Recompute those stages in a topological order of the relevant subgraph. Nodes that are not reachable from \(c\) do not depend on it according to the graph.
The set \(D(c)\) is a conservative logical rerun set: a stage is included because a declared dependency provides a route by which the change could affect its output. Whether an existing output can be reused is a separate question about the validity of that output and the execution system. A dependency graph identifies what may need recomputing; it does not, by itself, verify that a saved result was produced from the current inputs.
Worked Example: A Finite DAG and a Valid Execution Order
Consider a hypothetical workflow with seven nodes: raw counts \(C\), gene annotation \(A\), quality control \(Q\), filtered counts \(F\), normalization \(N\), clustering \(K\), and report \(R\). Suppose the edges are \(C \to Q\), \(Q \to F\), \(A \to F\), \(F \to N\), \(N \to K\), and \(K \to R\). The annotation is needed when filtering counts, while the raw counts enter quality control.
One topological ordering is \(C, A, Q, F, N, K, R\). Check each edge: \(C\) precedes \(Q\); both \(Q\) and \(A\) precede \(F\); \(F\) precedes \(N\); \(N\) precedes \(K\); and \(K\) precedes \(R\). Thus all six edges satisfy the ordering rule.
The workflow also shows that not every stage must follow every other stage. \(C\) and \(A\) are both source nodes, so either may come first. Quality control can be run once \(C\) is available; it need not wait for annotation \(A\), because no edge connects \(A\) to \(Q\). This independence can permit parallel work, provided the execution system and computing resources allow it.
Derivation: Why a Finite DAG Can Be Ordered
A node with no incoming edges is called a source. Every nonempty finite DAG has a source. To see why, suppose instead that every node has an incoming edge. Start at any node and repeatedly follow an incoming edge to a predecessor. Since the graph has finitely many nodes, this process must revisit a node. The edges followed between the repeated visits form a directed cycle, contradicting the assumption that the graph is acyclic. Therefore at least one source exists.
Place a source first and remove it and its outgoing edges. The remaining graph is still finite and acyclic, so if it is nonempty it also has a source. Repeating this step removes every node. The resulting list is a topological ordering: when a node was selected, no remaining node had an edge into it, so all its predecessors had already been removed and placed earlier. This argument establishes the result for finite DAGs without assuming it holds for infinite graphs.
Select a node whose prerequisites have already been completed, or a source when constructing a full ordering.
Record the stage’s inputs and output so that downstream stages can use the intended artifact.
Once all of a stage’s prerequisites are available, it becomes eligible to execute. Independent eligible stages may be run in parallel.
Tracing Changes Through a Single-Cell Workflow
In practice, a graph must include more than the obvious expression-data transformations. A report may depend on a table, a figure, and sample metadata. A model fit may depend on the normalized matrix, selected features, configuration, code, and software environment. Earlier material on input provenance, configuration files, version control, and software environments provides ways to identify these inputs; the graph represents how they feed into analysis stages.
Whether a dependency belongs in the graph depends on the computation. If a stage reads a configuration parameter, that parameter should be connected to the stage. If changing that parameter can affect a downstream table or report, the dependency should also propagate through those stages. Conversely, do not connect every input to every stage merely for convenience: doing so obscures real independence and expands the rerun set.
Worked Example: A Changed Gene Annotation
Suppose the hypothetical graph has nodes for counts \(C\), annotation \(A\), quality control \(Q\), filtered counts \(F\), normalization \(N\), feature selection \(H\), clustering \(K\), marker analysis \(M\), and report \(R\). Its edges are \(C \to Q\), \(Q \to F\), \(A \to F\), \(F \to N\), \(N \to H\), \(H \to K\), \(K \to M\), \(F \to M\), and \(M \to R\). The report also directly uses clustering, so add \(K \to R\).
Suppose the annotation is updated. Starting at \(A\), the only outgoing edge is \(A \to F\). From \(F\), paths continue to \(N\), then \(H\), then \(K\); from \(K\) they continue to \(M\) and \(R\). Also, \(F \to M\) gives another route to marker analysis. Therefore, including the changed annotation node, the affected set is \(D(A)=\{A,F,N,H,K,M,R\}\), which contains seven nodes.
Quality control \(Q\) is not in this set: the graph has no directed path from \(A\) to \(Q\). Thus the annotation change calls for rerunning the affected stages in an order such as \(F,N,H,K,M,R\), after the updated annotation is available. This conclusion is conditional on the stated graph being accurate. If quality control actually uses the annotation to label or filter genes, an edge \(A \to Q\) is missing and the graph must be corrected.
Worked Example: A Changed Analysis Parameter
Now suppose the workflow has nodes for normalized counts \(N\), a feature-selection parameter \(P_H\), selected features \(H\), clustering parameter \(P_K\), clusters \(K\), marker results \(M\), and report \(R\). The edges are \(N \to H\), \(P_H \to H\), \(H \to K\), \(P_K \to K\), \(K \to M\), \(N \to M\), and \(M \to R\), with \(K \to R\) as well. The parameter \(P_H\) controls how many features are selected.
If \(P_H\) changes, the reachable nodes are \(H\), \(K\), \(M\), and \(R\), in addition to \(P_H\) itself. Thus \(D(P_H)=\{P_H,H,K,M,R\}\), a set of five nodes. Normalized counts \(N\) and the clustering parameter \(P_K\) are not descendants of \(P_H\), so this graph does not call for rerunning them. The parameter change may alter the selected features, which can alter clustering and then marker results and the report; those are precisely the downstream dependencies represented here.
If instead \(P_K\) changes, the affected set is \(\{P_K,K,M,R\}\). Feature selection \(H\) remains upstream and does not depend on the clustering parameter. Explicit parameter nodes make such distinctions visible rather than relying on a person to remember which settings were used by each stage.
Diagnostics, Alternatives, and Limitations
A useful graph is both executable and reviewable. Before relying on it, check whether every stage has all the inputs it reads, whether outputs are named and traced to their producers, and whether the graph is acyclic. A cycle may indicate a genuine specification error or a stage that combines tasks which should be separated. An unexplained rerun of many unrelated stages can indicate overly broad dependencies; an output that remains unchanged after one of its actual inputs changes suggests a missing edge or a mismatch between the graph and the implementation.
A linear script is simple to read when every stage truly follows one fixed chain. However, it can rerun independent work unnecessarily and can conceal which inputs control each result. A dependency graph makes branching and reuse explicit and supports scheduling independent stages. A manually maintained checklist can be flexible, but is easier to apply inconsistently when many outputs and parameters are involved. None of these representations guarantees statistical validity: the graph organizes computation, not the scientific justification for filtering, normalization, model choice, or interpretation.
| Representation | Strength | Risk or limitation |
|---|---|---|
| Linear script | Easy to follow for a genuinely sequential analysis | May repeat independent work and hide input relationships |
| Dependency graph | Shows branching, prerequisites, and change propagation | Only as accurate as its declared dependencies |
| Manual checklist | Easy to adapt for small analyses | Rerun decisions may be inconsistent or difficult to audit |
A graph can also be too coarse. If one node represents an entire multi-stage analysis, a small change may appear to affect the whole analysis even when only one component depends on it. Splitting a node is helpful when the components have distinct inputs or outputs and that distinction changes execution decisions. Excessive splitting, however, adds maintenance without improving clarity. The appropriate granularity is the level at which dependencies and outputs can be stated reliably.
Finally, graph reachability describes potential influence, not guaranteed numerical change. A modified parameter might happen to produce the same output, but downstream stages are still in the logical rerun set if they consume that output. Conversely, an omitted dependency can make a workflow appear efficient while leaving results inconsistent with the current inputs. The graph should document actual data and configuration flow, not merely the rerun policy an analyst hopes to use.
Check Your Understanding
Answer each question, then compare your reasoning with the solutions below.
- In a graph with edges \(X \to A\), \(X \to B\), \(A \to C\), and \(B \to C\), which stages can execute independently after \(X\) is available?
- A metadata file \(G\) feeds a filtering stage \(F\), which feeds normalization \(N\) and then clustering \(K\). What stages are in the rerun set if \(G\) changes?
- Why is the finite-DAG topological-ordering result not automatically a claim about every infinite DAG?
- A report stage reads a clustering result and sample metadata, but the graph connects it only to the clustering result. What problem can this cause when metadata changes?
Solutions. (1) \(A\) and \(B\) can execute independently once \(X\) is available: neither depends on the other. \(C\) must wait for both. (2) The affected stages are \(G,F,N,K\), in that order after the changed input is available. (3) The source-removal argument relies on finiteness to ensure a source exists and that repeated removal terminates; arbitrary infinite graphs need not have a sequence ordering all nodes. (4) The graph omits a real dependency, so changing metadata may fail to trigger an updated report. Add an edge from the metadata input to the report stage, or to any intermediate stage that consumes it.