Quadratic unconstrained binary optimization and constraint programming approaches for lattice-based cyclic peptide docking

• URL: http://arxiv.org/abs/2412.10260v1
• Date: Fri, 13 Dec 2024 16:30:17 GMT
• Title: Quadratic unconstrained binary optimization and constraint programming approaches for lattice-based cyclic peptide docking
• Authors: J. Kyle Brubaker, Kyle E. C. Booth, Akihiko Arakawa, Fabian Furrer, Jayeeta Ghosh, Tsutomu Sato, Helmut G. Katzgraber,
• Abstract summary: The peptide-protein docking problem is an important problem in structural biology that facilitates rational and efficient drug design.<n>Our work extends recent efforts by incorporating the objectives and constraints associated with peptide cyclization and peptide-protein docking in the two-particle model on a tetrahedral lattice.<n>We implement an end-to-end framework that enables the evaluation of our methods on instances from the Protein Data Bank (PDB)
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The peptide-protein docking problem is an important problem in structural biology that facilitates rational and efficient drug design. In this work, we explore modeling and solving this problem with the quantum-amenable quadratic unconstrained binary optimization (QUBO) formalism. Our work extends recent efforts by incorporating the objectives and constraints associated with peptide cyclization and peptide-protein docking in the two-particle model on a tetrahedral lattice. We propose a ``resource efficient'' QUBO encoding for this problem, and baseline its performance with a novel constraint programming (CP) approach. We implement an end-to-end framework that enables the evaluation of our methods on instances from the Protein Data Bank (PDB). Our results show that the QUBO approach, using a classical simulated annealing solver, is able to find feasible conformations for problems with up to 6 peptide residues and 34 target protein residues, but has trouble scaling beyond this problem size. In contrast, the CP approach can solve problems with up to 13 peptide residues and 34 target protein residues. We conclude that while QUBO can be used to successfully tackle this problem, its scaling limitations and the strong performance of the CP method suggest that it may not be the best choice.

Related papers

• Max-Cut graph-driven quantum circuit design for planar spin glasses [0.0]
  We present a graph-based approach for finding the ground state of spin glasses. We employ a clustering strategy that organizes qubits into distinct groups based on the maximum cut technique. Our results underscore the potential of hybrid quantum-classical methods in addressing complex optimization problems.
  arXiv  Detail & Related papers  (2025-04-16T14:00:32Z)
• Lattice Protein Folding with Variational Annealing [2.164205569823082]
  We introduce a novel training scheme that employs masking to identify the lowest-energy folds in two-dimensional Hydrophobic-Polar (HP) lattice protein folding. Our findings emphasize the potential of advanced machine learning techniques in tackling complex protein folding problems.
  arXiv  Detail & Related papers  (2025-02-28T01:30:15Z)
• A Novel P-bit-based Probabilistic Computing Approach for Solving the 3-D Protein Folding Problem [4.410469529030158]
  This study marks the first work to apply probabilistic computing to tackle protein folding. We introduce a novel many-body interaction-based encoding method to map the problem onto an Ising model. Our simulations show that this approach significantly simplifies the energy landscape for short peptide sequences of six amino acids.
  arXiv  Detail & Related papers  (2025-02-27T12:46:25Z)
• Solving the Product Breakdown Structure Problem with constrained QAOA [0.0]
  We present a method for solving the industry relevant Product Breakdown Structure problem. Our solution is based on constrained QAOA, which by construction never explores the part of the Hilbert space that represents solutions forbidden by the problem constraints. We experimentally show that this approach has not only a very favorable scaling behavior, but also appears to suppress the negative effects of Barren Plateaus.
  arXiv  Detail & Related papers  (2024-06-21T15:15:02Z)
• OTClean: Data Cleaning for Conditional Independence Violations using Optimal Transport [51.6416022358349]
  sys is a framework that harnesses optimal transport theory for data repair under Conditional Independence (CI) constraints. We develop an iterative algorithm inspired by Sinkhorn's matrix scaling algorithm, which efficiently addresses high-dimensional and large-scale data.
  arXiv  Detail & Related papers  (2024-03-04T18:23:55Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• Lagrangian Duality in Quantum Optimization: Overcoming QUBO Limitations for Constrained Problems [0.0]
  We propose an approach to solving constrained optimization problems based on embedding the concept of Lagrangian duality into the framework of adiabatic quantum computation. Within the setting of circuit-model fault-tolerant quantum computation, we demonstrate that this approach achieves a quadratic improvement in circuit depth and maintains a constraint-independent circuit width.
  arXiv  Detail & Related papers  (2023-10-06T19:09:55Z)
• An Optimization-based Deep Equilibrium Model for Hyperspectral Image Deconvolution with Convergence Guarantees [71.57324258813675]
  We propose a novel methodology for addressing the hyperspectral image deconvolution problem. A new optimization problem is formulated, leveraging a learnable regularizer in the form of a neural network. The derived iterative solver is then expressed as a fixed-point calculation problem within the Deep Equilibrium framework.
  arXiv  Detail & Related papers  (2023-06-10T08:25:16Z)
• No-Regret Constrained Bayesian Optimization of Noisy and Expensive Hybrid Models using Differentiable Quantile Function Approximations [0.0]
  Constrained Upper Quantile Bound (CUQB) is a conceptually simple, deterministic approach that avoids constraint approximations. We show that CUQB significantly outperforms traditional Bayesian optimization in both constrained and unconstrained cases.
  arXiv  Detail & Related papers  (2023-05-05T19:57:36Z)
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
  We present an alternative method that does not require extra slack variables. We evaluate our approach on the traveling salesman problem, the bin packing problem, and the knapsack problem. This new approach can be used to solve problems with inequality constraints with a reduced number of resources.
  arXiv  Detail & Related papers  (2022-11-25T06:05:18Z)
• Designing Biological Sequences via Meta-Reinforcement Learning and Bayesian Optimization [68.28697120944116]
  We train an autoregressive generative model via Meta-Reinforcement Learning to propose promising sequences for selection. We pose this problem as that of finding an optimal policy over a distribution of MDPs induced by sampling subsets of the data. Our in-silico experiments show that meta-learning over such ensembles provides robustness against reward misspecification and achieves competitive results.
  arXiv  Detail & Related papers  (2022-09-13T18:37:27Z)
• Polynomial unconstrained binary optimisation inspired by optical simulation [52.11703556419582]
  We propose an algorithm inspired by optical coherent Ising machines to solve the problem of unconstrained binary optimization. We benchmark the proposed algorithm against existing PUBO algorithms, and observe its superior performance. The application of our algorithm to protein folding and quantum chemistry problems sheds light on the shortcomings of approxing the electronic structure problem by a PUBO problem.
  arXiv  Detail & Related papers  (2021-06-24T16:39:31Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Integrated Cutting and Packing Heterogeneous Precast Beams Multiperiod Production Planning Problem [0.0]
  We introduce a novel variant of cutting production planning problems named Integrated Cutting and Packing Heterogeneous Beams Multiperiod Production Planning (ICP-HPBMPP) We propose an integer linear programming model for the ICP-HPBMPP, as well as a lower bound for its optimal objective function value. We also propose a genetic algorithm approach for the ICP-HPBMPP as an alternative solution method.
  arXiv  Detail & Related papers  (2020-08-25T23:10:37Z)

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.