Enumerating tree-like chemical graphs with given upper and lower bounds on path frequencies

Area of Science:

• Chemoinformatics
• Bioinformatics
• Computational Chemistry

Background:

• Enumerating chemical graphs is crucial for drug design and determining novel compound structures.
• Existing methods can be computationally intensive due to processing individual feature vectors.

Purpose of the Study:

• To develop a more efficient algorithm for enumerating tree-like chemical graphs.
• To address the challenge of handling sets of upper and lower feature vectors simultaneously.

Main Methods:

• A novel exact branch-and-bound algorithm is proposed.
• New bounding operations are introduced, considering upper/lower feature vectors, bond constraints, and detachment conditions.

Main Results:

• The new algorithm directly processes all feature vectors in a given set.
• It avoids the computational burden of applying previous algorithms to each vector individually.

Conclusions:

• The developed algorithm effectively enumerates tree-like chemical graphs with specified path frequency bounds.
• This offers a more efficient approach for applications in chemoinformatics and drug discovery.