SynDOKU

SynDOKU addresses the constrained realizability of abstract reaction networks. Given an abstract network and a set of known molecules, it finds a bijection from abstract entities to molecules such that every assigned reaction is atom-balanced. The assignment may additionally be constrained by a prescribed set of graph-transformation rules.

This balanced-bijection problem is NP-complete. SynDOKU solves practical instances with a backtrack-and-prune algorithm inspired by the VF2 family of subgraph-isomorphism algorithms. Constraint propagation reduces candidate domains throughout the search, while chemical validation rejects assignments that violate atom balance or the allowed reaction rules.

Backtracking solver

Load one of the bundled problems and pass it to the backtracking solver:

from syndoku.models import ProblemJSON
from syndoku.validation.atom_balance import AtomBalance
from syndoku.solvers import make_solver

problem, _ = ProblemJSON.load(
    "data/toy_instances.json",
    example_id="ex_1",
)

solver = make_solver("bt", atom=AtomBalance())
result = solver.solve(problem, stop_at_first=True)
print(result.solutions)

The implementation is available as syndoku.solvers.backtrack.BacktrackSolver.

Run your own problem

Start in a notebook by defining the abstract reactions and supplying one candidate molecule for each abstract entity. The solver infers the entities from the reaction strings, then searches for a one-to-one assignment.

from syndoku.models import ProblemBuilder
from syndoku.solvers import make_solver
from syndoku.validation import AtomBalance

problem = ProblemBuilder.from_strings(
    reactions=[
        "A+B>>C",
        "C+D>>E",
        "E+F>>G",
    ],
    molecular_structures=[
        "C#C",
        "[H][H]",
        "C=C",
        "[H]C#N",
        "CCC#N",
        "O",
        "CCC(=O)N",
    ],
)

solver = make_solver("bt", atom=AtomBalance())
result = solver.solve(problem, stop_at_first=False)

print(f"{len(result.solutions)} solution(s) in {result.elapsed_sec:.3f} s")
for solution in result.solutions:
    print(solution)

If you have reaction templates, pass them to ProblemBuilder.from_strings through rules=... and construct the solver with temp=TemplateValidation() as well.

For command-line use, install the package and save the same problem as JSON. The syndoku command accepts this schema:

{
  "network": {
    "reactions": [
      "A+B>>C",
      "C+D>>E",
      "E+F>>G"
    ]
  },
  "molecules": [
    {"id": "C#C", "formula": "C2H2", "smiles": "C#C"},
    {"id": "[H][H]", "formula": "H2", "smiles": "[H][H]"},
    {"id": "C=C", "formula": "C2H4", "smiles": "C=C"},
    {"id": "[H]C#N", "formula": "CHN", "smiles": "[H]C#N"},
    {"id": "CCC#N", "formula": "C3H5N", "smiles": "CCC#N"},
    {"id": "O", "formula": "H2O", "smiles": "O"},
    {"id": "CCC(=O)N", "formula": "C3H7NO", "smiles": "CCC(=O)N"}
  ],
  "rules": []
}

Save this as prob.json, then run it from the repository root. By default, the command stops at the first valid assignment:

syndoku prob.json

Use --all-solutions to enumerate every assignment. A JSON file containing multiple examples additionally requires --example-id:

syndoku prob.json --all-solutions
syndoku data/toy_instances.json --example-id ex_9

The command automatically enables template validation when the JSON contains non-empty rules.

Benchmarks

Run the KEGG M00001 benchmark with:

python -m syndoku.benchmarks.kegg --configs B15

Run all NOG backtracking ablations (B0 through B16) on every seeded network with:

python -m syndoku.benchmarks.nog.run_ablation

The runner checkpoints to results/nog_ablation/ablation.csv and resumes by default. Use --configs, --sizes, or --seeds to run a subset.

Contributing

• Tuyet-Minh Phan
• Tieu-Long Phan

Publication

On the realizability of abstract reaction networks with real molecules and reactions

License

This project is licensed under the Apache License 2.0. See LICENSE for details.

Acknowledgments

This project has received funding from the European Union's Horizon Europe Doctoral Network programme under the Marie Skłodowska-Curie grant agreement No. 101072930 (TACsy -- Training Alliance for Computational Systems Chemistry).