An exact algorithm for side-chain placement in protein design
From MaRDI portal
Publication:691432
DOI10.1007/S11590-011-0308-0zbMATH Open1259.90150arXiv1103.1503OpenAlexW3098215245MaRDI QIDQ691432FDOQ691432
Authors: Stefan Canzar, Nora C. Toussaint, Gunnar W. Klau 
Publication date: 30 November 2012
Published in: Optimization Letters (Search for Journal in Brave)
Abstract: Computational protein design aims at constructing novel or improved functions on the structure of a given protein backbone and has important applications in the pharmaceutical and biotechnical industry. The underlying combinatorial side-chain placement problem consists of choosing a side-chain placement for each residue position such that the resulting overall energy is minimum. The choice of the side-chain then also determines the amino acid for this position. Many algorithms for this NP-hard problem have been proposed in the context of homology modeling, which, however, reach their limits when faced with large protein design instances. In this paper, we propose a new exact method for the side-chain placement problem that works well even for large instance sizes as they appear in protein design. Our main contribution is a dedicated branch-and-bound algorithm that combines tight upper and lower bounds resulting from a novel Lagrangian relaxation approach for side-chain placement. Our experimental results show that our method outperforms alternative state-of-the art exact approaches and makes it possible to optimally solve large protein design instances routinely.
Full work available at URL: https://arxiv.org/abs/1103.1503
Recommendations
Programming involving graphs or networks (90C35) Applications of mathematical programming (90C90) Boolean programming (90C09)
Cites Work
- Title not available (Why is that?)
- A semidefinite programming approach to side chain positioning with new rounding strategies
- Linear programming relaxations and belief propagation -- an empirical study
- The traveling-salesman problem and minimum spanning trees: Part II
- Fast and accurate algorithms for protein side-chain packing
Cited In (16)
- Combining variable neighborhood search and estimation of distribution algorithms in the protein side chain placement problem
- Global energy minimisation and cotranslational protein folding of HP models
- BWM*: A novel, provable, ensemble-based dynamic programming algorithm for sparse approximations of computational protein design
- Computational comparison studies of quadratic assignment like formulations for the in silico sequence selection problem in De Novo protein design
- Faster placement of hydrogens in protein structures by dynamic programming
- A semidefinite programming approach to side chain positioning with new rounding strategies
- Side Chain-Positioning as an Integer Programming Problem
- Fast and accurate algorithms for protein side-chain packing
- Protein structure optimization by side-chain positioning via beta-complex
- Title not available (Why is that?)
- Minimization-aware recursive \(K^{*}\) (\({ MARK}^{*}\)): a novel, provable algorithm that accelerates ensemble-based protein design and provably approximates the energy landscape
- Computational protein design as an optimization problem
- Research in Computational Molecular Biology
- Novel formulations for the sequence selection problem in de novo protein design with flexible templates
- BetaSCP2: a program for the optimal prediction of side-chains in proteins
- A Novel Minimized Dead-End Elimination Criterion and Its Application to Protein Redesign in a Hybrid Scoring and Search Algorithm for Computing Partition Functions over Molecular Ensembles
Uses Software
This page was built for publication: An exact algorithm for side-chain placement in protein design
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q691432)
