Quantum Optimisation for Protein-Protein Interaction Network Alignment

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.

EMAP-SSN: An Embedding- and Multiple-Alignment-Integrated Sequence Similarity Network Platform for Interactive Exploration of Protein Sequence Space
X. Feng, E. Master
bioRxiv5 Sep 2026PreprintCC BYFull textBioinformatics & computational biologybioRxiv
IMU-based upper limb kinematics validation: sensor fusion optimisation, sensor-to-segment alignment, and joint angle accuracy.
A. Fabre, G. Kerr, P. Pivonka +1
bioRxiv29 Sep 2026PreprintAll rights reservedFull textSystems & synthetic biologybioRxiv
PATHNet: A Thermodynamic Path-Integral-Inspired Neural Network for Protein-Ligand Interaction Prediction
B. G. A. S., A. Singh, S. Kanchan +1
bioRxiv11 Oct 2026PreprintCC BY-NC-NDFull textBioinformatics & computational biologybioRxiv
Transcription factor modularity in a gene-centered C. elegans core neuronal protein–DNA interaction network
Vanessa Vermeirssen, M. Inmaculada Barrasa, César A Hidalgo +5
Genome Research4 Nov 2026PreprintCC BY-NC 4.0Full textProteomics & metabolomics NeuroscienceHAL
Scaling Quantum Optimisation Beyond Hardware Limits for Real-World Scientific Workloads: Genome Assembly on Current Quantum Hardware
N. G Sankar, G. Miliotis, S. Caton
bioRxiv4 Sep 2026PreprintCC BYFull textBioinformatics & computational biologybioRxiv

Cite

BibTeX RIS

BibTeX

@misc{stahl2026quantum,
  title = {{Quantum Optimisation for Protein-Protein Interaction Network Alignment}},
  author = {Merle Stahl and Robert J. Banks and Matthias Traube and Josua Unger and Wolfgang Lechner and Jan Baumbach and Mhaned Oubounyt},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.05238},
  eprint = {2609.05238},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.05238},
}

RIS

TY  - UNPB
TI  - Quantum Optimisation for Protein-Protein Interaction Network Alignment
AU  - Merle Stahl
AU  - Robert J. Banks
AU  - Matthias Traube
AU  - Josua Unger
AU  - Wolfgang Lechner
AU  - Jan Baumbach
AU  - Mhaned Oubounyt
PY  - 2026
DA  - 2026/09/04
PB  - arXiv
DO  - 10.48550/arxiv.2609.05238
UR  - https://arxiv.org/abs/2609.05238
AB  - 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.
ER  -

Abstract

Related

Cite