A Constraint Programming Approach to Weighted Isomorphic Mapping of Fragment-based Shape Signatures

• URL: http://arxiv.org/abs/2112.10892v1
• Date: Mon, 20 Dec 2021 22:35:36 GMT
• Title: A Constraint Programming Approach to Weighted Isomorphic Mapping of Fragment-based Shape Signatures
• Authors: Thierry Petit and Randy J. Zauhar
• Abstract summary: Fragment-based shape signature techniques have proven to be powerful tools for computer-aided drug design. But finding the optimal match of a part of the fragmented compound can be time-consuming. We use constraint programming to solve this specific problem.
• Score: 0.5801044612920815
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Fragment-based shape signature techniques have proven to be powerful tools for computer-aided drug design. They allow scientists to search for target molecules with some similarity to a known active compound. They do not require reference to the full underlying chemical structure, which is essential to deal with chemical databases containing millions of compounds. However, finding the optimal match of a part of the fragmented compound can be time-consuming. In this paper, we use constraint programming to solve this specific problem. It involves finding a weighted assignment of fragments subject to connectivity constraints. Our experiments demonstrate the practical relevance of our approach and open new perspectives, including generating multiple, diverse solutions. Our approach constitutes an original use of a constraint solver in a real time setting, where propagation allows to avoid an enumeration of weighted paths. The model must remain robust to the addition of additional constraints making some instances not tractable. This particular context requires the use of unusual criteria for the choice of the model: lightweight, standard propagation algorithms, data structures without prohibitive constant cost while reducing the search space. The objective is not to design new, complex algorithms to solve difficult instances.

Related papers

• Bounded Synthesis of Synchronized Distributed Models from Lightweight Specifications [4.08734863805696]
  We present an approach to automatically synthesize synchronized models from lightweight formal specifications. Our approach takes as input a specification of a distributed system along with a global linear time constraint. It produces executable models for the component specifications whose concurrent execution satisfies the global constraint.
  arXiv  Detail & Related papers  (2025-02-19T18:54:32Z)
• Athanor: Local Search over Abstract Constraint Specifications [2.3383199519492455]
  We focus on general-purpose local search solvers that accept as input a constraint model. The Athanor solver we describe herein differs in that it begins from a specification of a problem in the abstract constraint specification language Essence.
  arXiv  Detail & Related papers  (2024-10-08T11:41:38Z)
• Counting Solutions to Conjunctive Queries: Structural and Hybrid Tractability [8.618430843854048]
  Counting the number of answers to conjunctive queries is a fundamental problem in databases that, under standard assumptions, does not have an efficient solution. We pinpoint tractable classes by examining the structural properties of intrinsic instances and introducing the novel concept of #-hypertree decomposition.
  arXiv  Detail & Related papers  (2023-11-24T16:09:12Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  We discuss the problem of bounding partially identifiable queries, such as counterfactuals, in Pearlian structural causal models. A recently proposed iterated EM scheme yields an inner approximation of those bounds by sampling the initialisation parameters. We show how a single symbolic knowledge compilation allows us to obtain the circuit structure with symbolic parameters to be replaced by their actual values.
  arXiv  Detail & Related papers  (2023-10-05T07:10:40Z)
• Compositional Diffusion-Based Continuous Constraint Solvers [98.1702285470628]
  This paper introduces an approach for learning to solve continuous constraint satisfaction problems (CCSP) in robotic reasoning and planning. By contrast, our model, the compositional diffusion continuous constraint solver (Diffusion-CCSP), derives global solutions to CCSPs.
  arXiv  Detail & Related papers  (2023-09-02T15:20:36Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• Retrieval-based Controllable Molecule Generation [63.44583084888342]
  We propose a new retrieval-based framework for controllable molecule generation. We use a small set of molecules to steer the pre-trained generative model towards synthesizing molecules that satisfy the given design criteria. Our approach is agnostic to the choice of generative models and requires no task-specific fine-tuning.
  arXiv  Detail & Related papers  (2022-08-23T17:01:16Z)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  We present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space. We generalize the "XY"-mixer designed to preserve the subspace of "one-hot" states to the general case of subspaces given by a number of computational basis states. Our analysis also leads to valid Trotterizations for "XY"-mixer with fewer CX gates than is known to date.
  arXiv  Detail & Related papers  (2022-03-11T17:19:26Z)
• Efficient Generation of Structured Objects with Constrained Adversarial Networks [25.74932947671932]
  Generative Adversarial Networks (GANs) struggle to generate structured objects like molecules and game maps. We propose Constrained Adversarial Networks (CANs), an extension of GANs in which the constraints are embedded into the model during training. CANs support efficient inference of valid structures (with high probability) and allows to turn on and off the learned constraints at inference time.
  arXiv  Detail & Related papers  (2020-07-26T19:04:37Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  We present a general framework for mining constraints from data. In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem. We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
  arXiv  Detail & Related papers  (2020-06-18T20:09:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.