A Peaceman-Rachford Splitting Method for the Protein Side-Chain Positioning Problem

Forbes Burkowski (), Haesol Im () and Henry Wolkowicz ()
Additional contact information
Forbes Burkowski: Cheriton School of Computer Science, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
Haesol Im: Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
Henry Wolkowicz: Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada

INFORMS Journal on Computing, 2025, vol. 37, issue 4, 962-976

Abstract: This paper considers the NP-hard protein side-chain positioning ( SCP ) problem, an important final task of protein structure prediction. We formulate the SCP as an integer quadratic program and derive its doubly nonnegative (DNN) (convex) relaxation. Strict feasibility fails for this DNN relaxation. We apply facial reduction to regularize the problem. This gives rise to a natural splitting of the variables. We then use a variation of the Peaceman-Rachford splitting method to solve the DNN relaxation. The resulting relaxation and rounding procedures provide strong approximate solutions. Empirical evidence shows that almost all our instances of this NP-hard SCP problem, taken from the Protein Data Bank, are solved to provable optimality . Our large problems correspond to solving a DNN relaxation with 2,883,601 binary variables to provable optimality.

Keywords: protein structure prediction; side-chain positioning; doubly nonnegative relaxation; facial reduction; Peaceman-Rachford splitting method (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.0094 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:37:y:2025:i:4:p:962-976

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().