Quantum Optimisation for Protein-Protein Interaction Network Alignment

• URL: http://arxiv.org/abs/2609.05238v1
• Date: Fri, 04 Sep 2026 15:04:55 GMT
• Title: Quantum Optimisation for Protein-Protein Interaction Network Alignment
• Abstract summary: Protein-protein interaction (PPI) network alignment combines topological and sequence information to identify conserved modules across species.<n>We model the alignment as a weighted maximum common induced subgraph problem and reformulate it through a modular product graph.<n>We develop a hybrid framework combining kernelisation, branch-and-bound, and seven Quantum Approximate optimisation algorithms.
• Score: 0.4763980315619087
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Protein-protein interaction (PPI) network alignment combines topological and sequence information to identify conserved modules across species, but global alignment remains challenging: heuristics sacrifice optimality, while exact methods lack scalability. We model the alignment as a weighted maximum common induced subgraph problem and reformulate it through the modular product graph to a minimum-weight vertex cover on the complement, with node weights carrying sequence similarity. To solve this problem, we develop a hybrid framework combining kernelisation, branch-and-bound, and seven Quantum Approximate Optimisation Algorithm (QAOA) formulations. These formulations differ in how the cover constraints are enforced, from penalty terms in the cost Hamiltonian to mixers confined to the feasible subspace. For single round QAOA, we derive closed-form expressions for the expected cost of four circulant mixer variants, enabling performance characterisation without circuit simulation. Applied to synthetic and real-world networks reduced to KEGG pathways, the QAOA formulations achieve high topological conservation on the aligned core while at least maintaining biological conservation comparable to leading classical aligners, at the cost of reduced node coverage. Across selected KEGG pathways, the aligned subnetworks retain disease-associated proteins, preserving biologically relevant information. Cheaper formulations leave more edges uncovered, while enforcing feasibility in the mixer raises circuit depth by one to two orders of magnitude. Together, these results highlight the potential of quantum optimisation for PPI network alignment and the resource trade-offs that will shape its scalability as quantum hardware matures.

Related papers

• Resource-Efficient Bio-Molecular Docking on a NISQ-era Digital Quantum Computer [16.44284103525396]
  We propose a hybrid quantum-classical approach for molecular docking.<n>We prove that a global minimizer of the FBE objective can always be chosen to be a pure product state.<n>We also execute the circuit on an IBM quantum computer.
  arXiv  Detail & Related papers  (2026-08-20T10:27:47Z)
• PACE-QAOA: Physics-Constrained Quantum Optimization for Qubit-Efficient Power System Islanding [10.677892416842944]
  Controlled islanding partitions a stressed power network to limit disrupted power transfer while preserving operational integrity in every island.<n>This paper develops a qubit-efficient hybrid quantum formulation that overcomes limited qubit capacity.<n>A qubit-efficient Lagrangian strategy combines quantum optimization with classical refinement to enforce operational constraints.
  arXiv  Detail & Related papers  (2026-08-03T18:42:00Z)
• A Hybrid Classical-Quantum Approach for Multi-Constrained Location Optimization Problem [0.19573380763700712]
  The Maximal Covering Location Problem (MCLP) aims to determine the optimal facility placements that maximize total coverage.<n>It is characterized by both equality and inequality constraints, which ensure correct coverage but significantly increase the complexity of exploring the solution space as instance size grows.<n>In this work, the MCLP is formulated as a Quadratic Unconstrained Binary Optimization model, where constraint embedding plays a critical role in solution quality.
  arXiv  Detail & Related papers  (2026-07-08T19:44:55Z)
• SeqGPT: A Constrained Transformer Agent for the Inverse Designof Multi-Panel Composite Structures [43.7610048074368]
  SeqGPT is a conditional Transformer agent developed to replace computationally expensive iterative methods.<n> Numerical experiments on the 18-panel horseshoe benchmark demonstrate that SeqGPT generates solutions near-instantaneously.
  arXiv  Detail & Related papers  (2026-07-03T12:00:39Z)
• Scalable Peptide Design via Memory-Efficient Equivariant Transformer [44.385833887269456]
  We introduce MEET (Memory Efficient Equivariant Transformer), an E(3) equivariant backbone for scalable atomistic peptide modeling.<n>MEET maintains coupled invariant scalar and equivariant vector feature streams, while reformulating geometric computation around memory efficient attention.<n> integrated into a VAE and latent diffusion pipeline for full atom peptide generation.<n> Experiments on large scale AFDB derived datasets further show that the proposed backbone supports systematic model and data scaling, leading to better binding affinity, physical validity, and sample diversity.
  arXiv  Detail & Related papers  (2026-06-23T17:25:04Z)
• PAC-Bayesian Adversarially Robust Generalization for Message Passing Graph Neural Networks: A Sensitivity Analysis [80.64607823130437]
  We extend PAC-Bayesian framework from deep neural networks to message passing GNNs.<n>We derive a tighter robust generalization bound in the adversarial setting.
  arXiv  Detail & Related papers  (2026-06-04T15:31:21Z)
• A Scalable Distributed Quantum Optimization Framework via Factor Graph Paradigm [46.08923284345648]
  We introduce a structure-aware framework for distributed quantum optimization.<n>We find that for a search space of size $N$, our framework achieves $O(sqrtN)$ query complexity up to processors and separator dependent factors.<n>We show that structure-aware decomposition delivers a practical path to scalable distributed quantum optimization on quantum networks.
  arXiv  Detail & Related papers  (2026-03-08T15:15:52Z)
• Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
  Push-based decentralized communication enables optimization over communication networks, where information exchange may be asymmetric.<n>We develop a unified uniform-stability framework for the Gradient Push (SGP) algorithm.<n>A key technical ingredient is an imbalance-aware generalization bound through two quantities.
  arXiv  Detail & Related papers  (2026-02-24T05:32:03Z)
• SKANet: A Cognitive Dual-Stream Framework with Adaptive Modality Fusion for Robust Compound GNSS Interference Classification [47.20483076887704]
  Global Navigation Satellite Systems (GNSS) face growing threats from sophisticated jamming interference.<n>We propose a cognitive deep learning framework built upon a dual-stream architecture that integrates Time-Frequency Images (TFIs) and Power Spectral Density (PSD)<n>We show that SKANet achieves an overall accuracy of 96.99%, exhibiting superior robustness for compound jamming classification.
  arXiv  Detail & Related papers  (2026-01-19T07:42:45Z)
• Scalable Quantum Walk-Based Heuristics for the Minimum Vertex Cover Problem [0.0]
  We propose a novel quantum algorithm for the Minimum Vertex Cover (MVC) problem based on continuous-time quantum walks (CTQWs)<n>In this framework, the coherent propagation of a quantum walker over a graph encodes its structural properties into state amplitudes.<n>We show that the CTQW-based algorithm consistently achieves superior approximation ratios and exhibits remarkable robustness with respect to network topology.
  arXiv  Detail & Related papers  (2025-12-02T17:04:57Z)
• Hephaestus: Mixture Generative Modeling with Energy Guidance for Large-scale QoS Degradation [44.97875113025023]
  We study the Quality of Service Degradation (QoSD) problem, in which an adversary perturbs edge weights to degrade network performance.<n>No prior model directly tackles the RefineD problem under nonlinear edge-weight functions.<n>This work proposes PIMMA, a self-reinforcing framework that synthesizes feasible solutions in latent space.
  arXiv  Detail & Related papers  (2025-10-19T22:48:35Z)
• Cons-training Tensor Networks: Embedding and Optimization Over Discrete Linear Constraints [2.8834278113855896]
  We introduce a novel family of tensor networks, termed constrained matrix product states (MPS)<n>MPS incorporate exactly arbitrary discrete linear constraints, including inequalities, into sparse block structures.<n>These networks are particularly tailored for modeling distributions with support strictly over the feasible space.
  arXiv  Detail & Related papers  (2024-05-15T00:13:18Z)

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.