Weekly Notes for Week 19

• This weeks topics:

  • Continuation of canonicalization.
  • Network expansion using graph transformation
  • Integer Linear Programming (ILP)
    • Introduction
    • Examples
    • Exercises
  • Autocatalytic Solutions via ILP
  • If time allows, if will start with Minimum Cycle Bases

• Wrt. the first mandatory assignment I will

  • introduce to the strategy framework of mød
  • explain the “revive” strategy in mød

• Reading Material:

  • For Canonicalization : still Chapter 4 of [1]

  • Link for visualising graph canonicalization as shown in the first lecture: http:// jakobandersen.github.io/graph_canon_vis

  • For network strategies and network expansion : Chapter 9 of [1]

  • Ring perception:

    – Franziska Berger, Christoph Flamm, Petra M. Gleiss, Josef Leydold, Peter F.

       Stadler: Counterexamples in Chemical Ring Perception. Journal of Chemical
       Information and Modeling 44(2): 323-331 (2004)
    

    – Hanser T, Jauffret P, Kaufmann G, (1996), A New Algorithm for Exhaustive

       Ring Perception in a Molecular Graph. J Chem Inf Comput Sci, 36(6):1146-1152. DOI:10.1021/c
    

  • Recommended reading if you are more interested:

    – Downs, G.M., Gillet, V.J., Holliday, J.D., Lynch, M.F.: Theoretical aspects of

     ring perception and development of the extended set of smallest rings concept.
    

    Journal of Chemical Information and Computer Sciences, 187-206 (1989)

[1] PhD Thesis by Jakob Lykke Andersen

Exercises 03 (in class, no submission):

• Use the graph-canon executable to create a JSON file which can be uploaded to the graph canonical visualisation webpage. Use i.) the grid graph (9 nodes, 12 edges) and ii.) the graph as used on page 18 of week18-19-2025.canonicalisation.pdf. (For the first graph you must create a graph in DIMACS format). Use DFS for the search tree traversal and discuss the pruning.

• Implement a small example illustrating how to solve the knapsack problem with an ILP solver. I recommend using gurobi using the python interface.

• From the file provided for the first assignment, execute and discuss the three revive examples.

• Study the examples provided in https://ac2025.algochem.techfak.de/Material/Other/code-snippets to get a basic understanding of how to use wildcards (and terms) in graph grammar rules.

• Study the example https://ac2025.algochem.techfak.de/Material/Other/code-snippets/smiles-counter-example.py to understand the problems of the original canonicalisation approach for SMILES.

• For the ILP exercises there is an additional exercises sheet.