Comparison and enumeration of chemical graphs

Area of Science:

• Computational chemistry
• Graph theory
• Cheminformatics

Background:

• Chemical compounds are commonly represented as graphs in computational systems.
• Understanding the computational complexity of graph problems is crucial for chemical data analysis.

Purpose of the Study:

• To review graph classes relevant to chemical compounds.
• To analyze the computational complexities of fundamental problems on these graph classes.
• To discuss algorithms for chemical graph matching, mapping, and enumeration.

Main Methods:

• Review of graph theory literature concerning chemical structures.
• Analysis of computational complexity for key graph algorithms.
• Discussion of algorithms for graph isomorphism, subgraph isomorphism, maximum common subgraph, reaction atom mapping, graph enumeration, and stereoisomer enumeration.

Main Results:

• Identified relevant graph classes for chemical compounds.
• Detailed computational complexities for problems like graph identity, subgraph matching, and reaction mapping.
• Explored algorithms for enumerating chemical graphs and stereoisomers.
• Discussed the link between graph enumeration and kernel functions for chemical compounds.

Conclusions:

• The computational complexity of problems on chemical graphs varies significantly across different graph classes.
• Efficient algorithms are essential for handling large-scale chemical data and enabling tasks like drug discovery and reaction prediction.
• Further research into specialized graph algorithms can enhance cheminformatics capabilities.