Reaction networks#
A grammar — a set of molecules plus a set of rules — describes a whole space of chemistry: apply the rules to the molecules, then to the products, and so on. Expanding it yields a derivation graph (DG), the reaction network whose vertices are molecules and whose hyperedges are reactions. The space is often infinite, so expansion is driven by a strategy that says how far, and in what direction, to go.
From a grammar to a derivation graph#
There are two ways to drive the expansion. The strategy framework composes
predefined operators with >>: addSubset() seeds the active
set, repeat() iterates, revive() feeds
newly created molecules back in, and leftPredicate() /
rightPredicate() filter derivations. A toy grammar —
acetone plus two relabeling rules written in DFS — expands to a small space:
acetone = smiles("CC(=O)C", "acetone", add=False)
rules = [ruleDFS("[C]1>>[Si]1", "C->Si", add=False),
ruleDFS("[O]1>>[S]1", "O->S", add=False)]
dg = DG(graphDatabase=[acetone])
dg.build().execute(addSubset(acetone) >> repeat(revive(rules)), verbosity=0)
print(dg.numVertices, "molecules,", dg.numEdges, "reactions")
dg.print()
12 molecules, 20 reactions
DG 0 (12 vertices, 20 hyperedges)
The apply framework does the same by hand — builder.apply([mol], rule) —
for full control, deduplicating products with a set (isomorphic molecules
share a canonical key). Breadth-first expansion explodes quickly, so real grammars
lean on the predicates above to keep the space finite.
Walk the result with dg.vertices and dg.edges; a hyperedge has .sources,
.targets and .rules, and getSBMLString() exports the
whole network as SBML.
"""7. From a grammar to a derivation graph.
A grammar is a set of molecules plus a set of rules. Expanding it produces a
*derivation graph* (DG): a reaction network whose vertices are molecules and
whose hyperedges are reactions. Two ways to drive the expansion:
* the **strategy** framework -- compose predefined operators (``addSubset``,
``repeat``, ``leftPredicate`` ...) with ``>>``; high level, plug-and-play;
* the **apply** framework -- call ``builder.apply([mol], rule)`` yourself for
full control, deduplicating products by hand (isomorphic graphs share a
canonical key, so a ``set`` removes duplicates).
Toy grammar: acetone plus two relabeling rules, r0 (C -> Si) and r1 (O -> S).
Run: python 06_grammar_to_dg.py
"""
import _bootstrap
from molfoundry import (
smiles, ruleDFS, DG, addSubset, repeat, revive, enable_post,
)
enable_post()
acetone = smiles("CC(=O)C", "acetone")
# The two relabeling rules, written in the compact DFS line notation: the id ties
# the left vertex to the right one, so "[C]1>>[Si]1" relabels a carbon in place.
r0 = ruleDFS("[C]1>>[Si]1", "C to Si")
r1 = ruleDFS("[O]1>>[S]1", "O to S")
rules = [r0, r1]
# --- strategy framework -----------------------------------------------------
# repeat(revive(...)) keeps re-applying the rules to newly created molecules
# until nothing new appears (a fixed point).
dg_strat = DG(graphDatabase=[acetone])
dg_strat.build().execute(addSubset(acetone) >> repeat(revive(rules)), verbosity=0)
dg_strat.print()
print(f"strategy framework: {dg_strat.numVertices} molecules, {dg_strat.numEdges} reactions")
# --- apply framework --------------------------------------------------------
# Same result, expanded by hand: pop a molecule, apply each rule, collect the
# fresh products, dedupe with a set, repeat.
dg_apply = DG(graphDatabase=[acetone])
current = {acetone}
seen = {acetone}
rounds = 0
with dg_apply.build() as b:
while current:
m = current.pop()
products = set()
for r in rules:
for d in b.apply([m], r):
products |= {t.graph for t in d.targets}
rounds += 1
fresh = products - seen
seen |= fresh
current |= fresh
dg_apply.print()
print(f"apply framework: {dg_apply.numVertices} molecules, {dg_apply.numEdges} reactions "
f"({rounds} apply rounds)")
print("\nBoth frameworks explore the same 6-molecule space "
"(acetone -> ... -> hexa-substituted).")
Oro’s adenine synthesis#
Joan Oró showed in 1961 that adenine — a nucleobase essential to life — forms
in good yield from hydrogen cyanide (HCN) and ammonia in water. The entire
mechanism is captured by five reaction rules (terse enough for DFS, and term
rules because they use * wildcards): HCN dimerization, addition across a C=N,
ammonolysis of nitriles to amidines, condensation, and an imine–enamine
tautomerization.
To verify the proposed mechanism, name the twelve molecules it passes through
(HCN = A … adenine = J, plus the ammonia catalyst) and expand the grammar while
forbidding it from ever leaving that set — a rightPredicate. The network closes
on exactly those twelve species, and its reactions are the Oró pathway from HCN
all the way to adenine:
rules = [
ruleDFS("[N]1#[C]2[H]3.[N]4#[C]5[H]6>>[N]1#[C]2[C]5([H]6)=[N]4[H]3", "r1f", labelType=LabelType.Term, add=False),
ruleDFS("[N]1#[C]2[H]3.[N]4([H]6)=[C]5([*]7)[*]8>>[N]1#[C]2[C]5([*]7)([*]8)[N]4([H]6)[H]3", "r2f", labelType=LabelType.Term, add=False),
ruleDFS("[N]1#[C]2[*]3.[H]4[N]5([*]6)[*]7>>[H]4[N]1=[C]2([*]3)[N]5([*]6)[*]7", "r3f", labelType=LabelType.Term, add=False),
ruleDFS("[H]1[N]2([H]4)[*]3.[H]5[N]6=[C]7([*]8)[*]9>>[*]3[N]2=[C]7([*]8)[*]9.[H]1[N]6([H]4)[H]5", "r6f", labelType=LabelType.Term, add=False),
ruleDFS("[*]1[N]2=[C]3([*]8)[C]4([H]5)([*]6)[*]7>>[*]1[N]2([H]5)[C]3([*]8)=[C]4([*]6)[*]7", "r7f", labelType=LabelType.Term, add=False),
]
known = [smiles(s, n, add=False) for n, s in [
("A","C#N"),("B","N#CC=N"),("C","NC(C#N)C#N"),("D","NC(C#N)C(=N)N"),
("E","NC(=N)C(N)C(N)=N"),("F","NC(=N)C(N)C(N)=NC=N"),("X","NC(=N)C1C(N)=NC=N1"),
("G","NC(=N)C1=C(N)NC=N1"),("H","NC=N"),("I","N=CN=C(N)C(=C1N)N=CN1"),
("J","NC1=NC=NC(=C12)NC=N2"),("cat","N")]]
known_keys = {g.canonKey for g in known}
ls = LabelSettings(LabelType.Term, LabelRelation.Unification)
dg = DG(graphDatabase=known, labelSettings=ls)
dg.build().execute(
addSubset(known) >> rightPredicate[lambda d: all(g.canonKey in known_keys for g in d.right)](repeat(rules)),
verbosity=0)
adenine = smiles("NC1=NC=NC(=C12)NC=N2", add=False)
print(dg.numVertices, "species,", dg.numEdges, "reactions; adenine reached:",
any(v.graph.canonKey == adenine.canonKey for v in dg.vertices))
dg.print()
12 species, 18 reactions; adenine reached: True
DG 1 (12 vertices, 18 hyperedges)
Without that restriction a single expansion round already yields hundreds of
molecules. Predicates rein it in: forbid high-energy 3- and 4-membered rings
(patterns built with graphDFS() and detected by a subgraph
search, monomorphism) and cap the carbon count — bringing one round from 249 to
69 molecules (see the full script).
"""16. Oro's adenine synthesis (and taming a chemical space).
Joan Oro showed (1961) that adenine -- a nucleobase essential to life -- forms
in good yield from hydrogen cyanide (HCN) and ammonia in water. The whole
mechanism is captured by just five reaction rules (written here in DFS notation,
with ``*`` wildcards, so they are term rules):
r1f HCN + HCN -> imino-acetonitrile
r2f HCN + imine -> add across the C=N
r3f nitrile + amine -> amidine (ammonolysis; reactions 3,4,5,7)
r6f amidine + amine -> condensation (reactions 6,8,9)
r7f imine <-> enamine tautomerization
This script does two things the original tutorial does:
1. **Verify the mechanism.** Restrict every product to the set of molecules the
proposed pathway names (a ``rightPredicate``), expand to a fixed point, and
confirm the network connects HCN (A) all the way to adenine (J).
2. **Tame the unrestricted space.** Without that restriction a single expansion
round already yields hundreds of molecules. Two predicates rein it in:
forbid high-energy 3- and 4-membered rings (patterns built with ``graphDFS``
and detected by subgraph search), and cap the carbon count.
Run: python 16_oro_adenine.py
"""
import _bootstrap
from molfoundry import (
smiles, graphDFS, ruleDFS, DG, LabelSettings, LabelType, LabelRelation,
addSubset, repeat, rightPredicate, enable_post,
)
enable_post()
# The five mechanism rules, in DFS line notation (term rules -- "*" is a wildcard).
rules = [
ruleDFS("[N]1#[C]2[H]3.[N]4#[C]5[H]6>>[N]1#[C]2[C]5([H]6)=[N]4[H]3",
"r1f", labelType=LabelType.Term, add=False),
ruleDFS("[N]1#[C]2[H]3.[N]4([H]6)=[C]5([*]7)[*]8>>[N]1#[C]2[C]5([*]7)([*]8)[N]4([H]6)[H]3",
"r2f", labelType=LabelType.Term, add=False),
ruleDFS("[N]1#[C]2[*]3.[H]4[N]5([*]6)[*]7>>[H]4[N]1=[C]2([*]3)[N]5([*]6)[*]7",
"r3f", labelType=LabelType.Term, add=False),
ruleDFS("[H]1[N]2([H]4)[*]3.[H]5[N]6=[C]7([*]8)[*]9>>[*]3[N]2=[C]7([*]8)[*]9.[H]1[N]6([H]4)[H]5",
"r6f", labelType=LabelType.Term, add=False),
ruleDFS("[*]1[N]2=[C]3([*]8)[C]4([H]5)([*]6)[*]7>>[*]1[N]2([H]5)[C]3([*]8)=[C]4([*]6)[*]7",
"r7f", labelType=LabelType.Term, add=False),
]
# The 12 molecules the proposed mechanism passes through: HCN (A) ... adenine (J),
# plus the ammonia catalyst.
known = [
smiles("C#N", "A", add=False), # hydrogen cyanide
smiles("N#CC=N", "B", add=False),
smiles("NC(C#N)C#N", "C", add=False),
smiles("NC(C#N)C(=N)N", "D", add=False),
smiles("NC(=N)C(N)C(N)=N", "E", add=False),
smiles("NC(=N)C(N)C(N)=NC=N", "F", add=False),
smiles("NC(=N)C1C(N)=NC=N1", "X", add=False),
smiles("NC(=N)C1=C(N)NC=N1", "G", add=False),
smiles("NC=N", "H", add=False), # formamidine
smiles("N=CN=C(N)C(=C1N)N=CN1", "I", add=False),
smiles("NC1=NC=NC(=C12)NC=N2", "J", add=False), # adenine
smiles("N", "cat", add=False), # ammonia (catalyst)
]
name = {g.canonKey: g.name for g in known}
known_keys = set(name)
ls = LabelSettings(LabelType.Term, LabelRelation.Unification)
# --- 1. verify the mechanism reproduces the A -> J pathway -------------------
dg = DG(graphDatabase=known, labelSettings=ls)
dg.build().execute(
addSubset(known)
>> rightPredicate[lambda d: all(g.canonKey in known_keys for g in d.right)](
repeat(rules)
),
verbosity=0,
)
dg.print()
print(f"Mechanism restricted to the {len(known)} named molecules: "
f"{dg.numVertices} species, {dg.numEdges} reactions")
print("Productive steps (identity/catalyst-only steps hidden):")
for e in dg.edges:
ed = sorted(name[v.graph.canonKey] for v in e.sources)
pr = sorted(name[v.graph.canonKey] for v in e.targets)
if ed != pr: # skip the catalyst passing straight through
print(f" {' + '.join(ed):12s} -> {' + '.join(pr)}")
adenine = smiles("NC1=NC=NC(=C12)NC=N2", add=False)
print("adenine (J) reached:",
any(v.graph.canonKey == adenine.canonKey for v in dg.vertices))
# --- 2. tame the otherwise explosive space ----------------------------------
# Forbidden ring patterns, built with graphDFS (wildcard atoms and bonds).
cyc3 = graphDFS("[*]1{*}[*]{*}[*]{*}1", "3-ring", add=False)
cyc4 = graphDFS("[*]1{*}[*]{*}[*]{*}[*]{*}1", "4-ring", add=False)
def network_size(strategy):
dg = DG(graphDatabase=known, labelSettings=ls)
dg.build().execute(addSubset(known) >> strategy, verbosity=0)
return dg.numVertices
def forbid(strat, patterns):
return rightPredicate[
lambda d: all(not p.monomorphism(g, labelSettings=ls)
for p in patterns for g in d.right)
](strat)
def max_carbons(strat, n):
return rightPredicate[lambda d: all(g.vLabelCount("C") <= n for g in d.right)](strat)
print("\nOne unrestricted expansion round vs. constrained ones:")
print(f" unrestricted : {network_size(repeat[1](rules))} molecules")
print(f" forbid 3- and 4-rings : {network_size(forbid(repeat[1](rules), [cyc3, cyc4]))} molecules")
print(f" forbid rings + at most 5 C : {network_size(max_carbons(forbid(repeat[1](rules), [cyc3, cyc4]), 5))} molecules")
Pathways and integer flow#
A derivation graph is a reaction network, so a natural question is: given
feedstocks and a target, what sequence of reactions actually makes the target?
That is an integer-flow (hyperflow) query — assign an integer firing count to
each reaction so mass is conserved at every molecule. MolFoundry ships a pure-SMT
solver, FlowModelSMT (z3, no license needed), and a
faster Gurobi ILP FlowModel for large networks. Both
return mass-balanced flows; whether a flow is realizable — has a valid firing
order — is answered separately by solution.is_realizable() /
solution.enumerate_certificates(), the latter returning that order as a
certificate.
Build the formose sugar network and ask for the shortest pathway to glyceraldehyde, then recover a firing order. Declaring an out-flow only on the target forces every feedstock and intermediate to be fully consumed, so the flow is stoichiometrically clean:
formaldehyde = smiles("C=O", "formaldehyde", add=False)
glycolaldehyde = smiles("OCC=O", "glycolaldehyde", add=False)
ke = ruleGMLString('rule [ ruleID "keto->enol" left [ edge [ source 1 target 4 label "-" ] edge [ source 1 target 2 label "-" ] edge [ source 2 target 3 label "=" ] ] context [ node [ id 1 label "C" ] node [ id 2 label "C" ] node [ id 3 label "O" ] node [ id 4 label "H" ] ] right [ edge [ source 1 target 2 label "=" ] edge [ source 2 target 3 label "-" ] edge [ source 3 target 4 label "-" ] ] ]', add=False)
al = ruleGMLString('rule [ ruleID "aldol" left [ edge [ source 1 target 2 label "=" ] edge [ source 2 target 3 label "-" ] edge [ source 3 target 4 label "-" ] edge [ source 5 target 6 label "=" ] ] context [ node [ id 1 label "C" ] node [ id 2 label "C" ] node [ id 3 label "O" ] node [ id 4 label "H" ] node [ id 5 label "O" ] node [ id 6 label "C" ] ] right [ edge [ source 1 target 2 label "-" ] edge [ source 2 target 3 label "=" ] edge [ source 5 target 6 label "-" ] edge [ source 4 target 5 label "-" ] edge [ source 6 target 1 label "-" ] ] ]', add=False)
seed = [formaldehyde, glycolaldehyde]
dg = DG(graphDatabase=seed)
dg.build().execute(
addSubset(seed) >> rightPredicate[lambda d: all(g.vLabelCount("C") <= 3 for g in d.right)](
repeat[3]([ke, ke.makeInverse(), al, al.makeInverse()])),
verbosity=0)
target = next(v for v in dg.vertices if v.graph.smiles == "O=CC(O)CO")
flow = FlowModelSMT(dg)
flow.add_in_flow(dg.findVertex(formaldehyde), 0, 10)
flow.add_in_flow(dg.findVertex(glycolaldehyde), 0, 10)
flow.add_out_flow(target, 1, 1)
solution = flow.optimum()
print(f"shortest pathway ({int(solution.obj_value)} reactions):")
for step, e in enumerate(next(solution.enumerate_certificates(), []), 1):
ed = " + ".join(s.graph.smiles for s in e.sources)
pr = " + ".join(t.graph.smiles for t in e.targets)
print(f" {step}. {ed} -> {pr}")
shortest pathway (2 reactions):
1. O=CCO -> OC=CO
2. OC=CO + O=C -> O=CC(O)CO
"""7. Reaction networks and pathway queries.
Once a grammar is expanded into a derivation graph, the DG *is* a reaction
network. A common question is: given some feedstocks and a target, what
sequence of reactions actually makes the target? That is a integer-flow (a.k.a.
hyperflow) query: assign an integer firing count to each reaction so that mass
is conserved at every molecule, subject to what may flow in and out.
MolFoundry ships two integer-flow solvers with the same API:
* ``FlowModelSMT`` -- a pure-SMT (z3) solver. Needs no license, so it is used
here.
* ``FlowModel`` -- a Gurobi ILP; faster for large networks (needs a Gurobi
license).
Both return mass-balanced flows (a firing count per reaction). Whether a flow is
*realizable* -- i.e. has a valid firing order -- is a separate question, answered
by ``solution.is_realizable()`` / ``solution.enumerate_certificates()`` (the
latter hands back a valid order as a certificate).
Here we build the formose network (formaldehyde + glycolaldehyde under keto-enol
and aldol chemistry) and ask for the shortest pathway to glyceraldehyde, then
recover a firing order. Declaring an out-flow only on the target forces every
feedstock and intermediate to be fully consumed, so the flow is
stoichiometrically clean.
Run: python 07_reaction_networks_and_flow.py
"""
import _bootstrap
from _bootstrap import GML
from molfoundry import (
smiles, ruleGML, DG, addSubset, repeat, rightPredicate,
inputGraphs, enable_post, FlowModelSMT,
)
enable_post()
formaldehyde = smiles("C=O", "formaldehyde")
glycolaldehyde = smiles("OCC=O", "glycolaldehyde")
keto_enol = ruleGML(str(GML / "keto_enol.gml"))
keto_enol_b = ruleGML(str(GML / "keto_enol.gml"), invert=True)
aldol = ruleGML(str(GML / "aldol_addition.gml"))
aldol_b = ruleGML(str(GML / "aldol_addition.gml"), invert=True)
# Build the network, capping molecules at 3 carbons to keep it small.
dg = DG(graphDatabase=inputGraphs)
dg.build().execute(
addSubset(inputGraphs)
>> rightPredicate[lambda d: all(g.vLabelCount("C") <= 3 for g in d.right)](
repeat[3]([keto_enol, keto_enol_b, aldol, aldol_b])
),
verbosity=0,
)
dg.print()
print(f"formose network: {dg.numVertices} species, {dg.numEdges} reactions")
# glyceraldehyde, O=CC(O)CO -- the C3 aldose we want to make.
target = next(v for v in dg.vertices if v.graph.smiles == "O=CC(O)CO")
flow = FlowModelSMT(dg)
flow.add_in_flow(dg.findVertex(formaldehyde), 0, 10)
flow.add_in_flow(dg.findVertex(glycolaldehyde), 0, 10)
flow.add_out_flow(target, 1, 1) # only the target leaves the network
solution = flow.optimum() # fewest reactions (mass-balanced)
print(f"\nshortest pathway to glyceraldehyde ({int(solution.obj_value)} reactions):")
print(" feed:", {v.graph.name: c for v, c in solution.in_flow})
# The flow is a reaction multiset; a valid firing order (if one exists) is a
# certificate, recovered separately via enumerate_certificates().
order = next(solution.enumerate_certificates(), None)
if order is None:
print(" (this flow has no valid firing order -- it is not realizable)")
else:
for step, e in enumerate(order, 1):
educts = " + ".join(s.graph.smiles for s in e.sources)
products = " + ".join(t.graph.smiles for t in e.targets)
print(f" {step}. {educts} -> {products}")
print(" (this firing order is a certificate: it can be run start to finish)")
Depicting derivation graphs#
print() renders the network as inline SVG. A
DGPrinter controls what is drawn: pushVertexVisible
hides vertices (and their arrows) that fail a predicate — ideal for suppressing
highly-connected “hub” molecules that clutter the picture — while
pushVertexColor / pushEdgeColor highlight chosen species or reactions, and
withRuleName labels each reaction with its rule.
hide = DGPrinter()
hide.pushVertexVisible(lambda v: v.graph.canonKey != formaldehyde.canonKey)
dg.print(hide) # the formose network again, minus the formaldehyde hub
DG 2 (5 vertices, 5 hyperedges)
"""9. Tricks for depicting derivation graphs.
``DG.print()`` accepts a ``DGPrinter`` that controls what is drawn and how.
The most useful knobs:
* ``pushVertexVisible(pred)`` -- hide vertices (and their reaction arrows) that
fail the predicate. Great for suppressing highly-connected "hub" molecules
(H2O, H+, ...) that otherwise clutter the picture.
* ``pushVertexColor(fn)`` / ``pushEdgeColor(fn)`` -- color chosen molecules or
reactions (e.g. highlight a target).
* ``withRuleName`` -- label each reaction with its rule's name.
Here we build the formose network (formaldehyde + glycolaldehyde under keto-enol
and aldol rules) and draw it three ways.
Run: python 08_depicting_dgs.py
"""
import _bootstrap
from _bootstrap import GML
from molfoundry import (
smiles, ruleGML, DG, DGPrinter, addSubset, repeat, rightPredicate,
inputGraphs, enable_post,
)
enable_post()
formaldehyde = smiles("C=O", "formaldehyde")
glycolaldehyde = smiles("OCC=O", "glycolaldehyde")
keto_enol = ruleGML(str(GML / "keto_enol.gml"))
keto_enol_b = ruleGML(str(GML / "keto_enol.gml"), invert=True)
aldol = ruleGML(str(GML / "aldol_addition.gml"))
aldol_b = ruleGML(str(GML / "aldol_addition.gml"), invert=True)
dg = DG(graphDatabase=inputGraphs)
dg.build().execute(
addSubset(inputGraphs)
>> rightPredicate[lambda d: all(g.vLabelCount("C") <= 4 for g in d.right)](
repeat[2]([keto_enol, keto_enol_b, aldol, aldol_b])
),
verbosity=0,
)
print(f"formose network: {dg.numVertices} molecules, {dg.numEdges} reactions")
# (a) the full network
dg.print()
# (b) hide the formaldehyde hub -- fewer crossing arrows
hide = DGPrinter()
hide.pushVertexVisible(lambda v: v.graph.canonKey != formaldehyde.canonKey)
dg.print(hide)
# (c) highlight the feedstocks and label reactions by rule name
highlight = DGPrinter()
highlight.withRuleName = True
feed = {formaldehyde.canonKey, glycolaldehyde.canonKey}
highlight.pushVertexColor(lambda v: "#2f7d32" if v.graph.canonKey in feed else "")
dg.print(highlight)
print("Wrote three DG drawings to summary/summary.html (full, hub-hidden, highlighted).")