The resolution of the enumeration problem. A) The process of enumeration: The hyperpath given by running
FindAll on the hypergraph of Figure 2D. This hyperpath is not minimal as can be verified by running
Minimize without constraints (i.e.
Rf = {∅}). Two minimal hypergraphs connect
v8 to the source nodes
v1,
v4: the one containing hyperarcs
R4,
R7 and the one highlighted in the figure containing only the hyperarcs
R3,
R4; B) Scheme of resolution of the enumeration problem for biosynthesis of liquiritigenin whose hypergraph is represented in Figure 1. Each node in the scheme corresponds to a call to
FindPath and contains the constraint sets
Rf and
Rn (see left bottom box), and the minimal hyperpath
corresponding to the given constraints.
FindPath iteratively calls itself, the structure obtained is a rooted tree where each node represents a call to
FindPath, and each call is characterized by the sets
Rf and
Rn. In particular there are no constraints on the pathway searched at the root node, corresponding to the first call to
FindPath, this fact is expressed by having empty
Rf and
Rn. The hyperpath found is
R1,
R2,
R4,
R7. For each reaction in the hyperpath, a new call to
FindPath is done, this time with the constraints induced by the hyperpath solution of the parent node. Processes that do not return hyperpaths
are not followed by calls to children processes, while the processes that return one hyperpath
have unconstrained reactions
and are followed by as many children processes as unconstrained reactions. The children processes have as set of reactions that cannot belong to the returned pathway
Rn' the same as the father augmented by one reaction from the unconstrained set of the hyperpath
returned by the father process, while the set of reactions required to belong to the pathway
Rf ' is given by the ones of the father augmented by all the reactions preceding the one added to
Rn to get
Rn'. Consider for instance the process giving as pathway
it contains two reactions not in
Rf :
R5 and
R9 so its two children processes have
Rn given by
R4 ∪
R5 and
R4 ∪
R9 and
Rf is given by the one of the father: {
R1,
R2} union once with {∅} and once with
R5: the only unconstrained reaction preceding
R9 in the pathway
.