Skip to content
#edge computing Open access

Navigating Large Chemical Spaces Using Graph Theory and Integer Programming

Sep 2026 · Journal of Chemical Information and Modeling · Vol 66, pp. 11862 - 11881 · 0 citations · 97 references
Computational Drug Discovery Methods

TL;DR

A computational framework that integrates graph theory and integer programming to enable the efficient navigation of large chemical spaces and demonstrates the effectiveness of the proposed approach by navigating the chemical space of per- and polyfluoroalkyl substances (PFAS); this comprises approximately 15,000 molecular structures.

Abstract

Navigating and analyzing large chemical spaces are necessary to accelerate the design and discovery of new molecules and chemical processes. In this work, we introduce a computational framework that integrates graph theory and integer programming to enable the efficient navigation of large chemical spaces. Our framework represents the chemical space as a graph, wherein nodes represent molecules and edges represent the degree of similarity or connectivity based on domain-specific information. Using the graph representation, we identify representative molecules by computing the so-called minimum dominating set (MDS), which in our context is the minimum set of molecules that is connected to all other molecules. We present a suite of solution strategies for the MDS problem including heuristic and rigorous integer programming (IP) approaches. We show that these approaches allow us to capture physicochemical properties and domain-specific logic and constraints, facilitating the identification of molecules with the target properties. We demonstrate the effectiveness of the proposed approach by navigating the chemical space of per- and polyfluoroalkyl substances (PFAS); this comprises approximately 15,000 molecular structures. We compare our framework against traditional dimensionality reduction and clustering methods such as t-SNE and K-means clustering.

Read PDF

Similar papers

Sep 2026

Line-Graph Node Centrality in Retrosynthesis.

This work proposes the use of line graphs of molecular graphs, in which nodes represent bonds of the original molecule, together with node centrality measures as a quantitative criterion for identifying strategic bonds, and demonstrates the approach in detail on six structurally diverse natural products.

Z. Boskovic · 0 citations
Open access Aug 2026

Grouper: symmetry-aware functional-group graph representations for generative exploration of chemical space

The vastness of chemical space holds immense potential for discovery, yet its systematic exploration remains computationally daunting. We mitigate this complexity by focusing on chemically meaningful differences captured by functional-group motifs and collapsing symmetry-equivalent configurations. We operationalize t...

Kieran Nehil-Puleo, Nicholas C. Craven, Clare McCabe et al. · 0 citations
Open access Sep 2026

Efficient visualization of chemical space

It is shown that basic properties of the metrics used in the original space can be used to infer the shape of the chemical space, which in turns suggests an optimal strategy to project chemical information to lower dimensions.

Akash Surendran, Krisztina Zsigmond, Le-Xin Chen et al. · 0 citations
Sep 2026

Graph-to-Graph Inverse Design of Surfactants under Multiobjective and Structural Constraints

Rapid, sustainable redesign of large functional molecules requires efficient exploration of vast chemical spaces subject to multiple properties and constraints. Graph neural networks have shown strong performance in molecular property prediction, yet their use for inverse design remains relatively underexplored. Mean...

Alexander W. Rogers, Ruediger Zillmer, A. Lane et al. · 0 citations
Sep 2026

KnottedGraph: Scalable knotted-graph topology for scientific and mathematical discovery

KnottedGraph is introduced, a computational framework that converts such scientific representations to knotted graphs that retain graph connectivity and spatial embedding together, enabling large-scale classification and introducing a route from topological data to LLM-assisted AI4Math discovery.

Hakan Akgun, Xian-Quan Yan, Ke-Han Liu et al. · 0 citations
Open access Sep 2026

Numerical Prediction of Physicochemical Properties of Drug Structures via Some Graph Parameters

An exploratory investigation into the physicochemical properties of 10 selected drug and bioactive molecules from diverse therapeutic classes to evaluate bulk size-dependent properties using these fundamental graph parameters highlights the potential of these fundamental graph parameters in QSPR modeling.

Mukaddes Ökten Turacı · 0 citations

Related blog posts

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.