# Computational Protein Design Using AND/OR Branch-and-Bound Search

arXiv: https://arxiv.org/abs/1412.3138 · HTML: https://mlsanity.com/paper/1412.3138/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Dec 2014.

## Built on by (most cited first, 1 of 1)

- [Boosting AND/OR-Based Computational Protein Design: Dynamic Heuristics and Generalizable UFO](https://mlsanity.com/paper/2309.00408/) (2023)

## Abstract (arXiv)

The computation of the global minimum energy conformation (GMEC) is an important and challenging topic in structure-based computational protein design. In this paper, we propose a new protein design algorithm based on the AND/OR branch-and-bound (AOBB) search, which is a variant of the traditional branch-and-bound search algorithm, to solve this combinatorial optimization problem. By integrating with a powerful heuristic function, AOBB is able to fully exploit the graph structure of the underlying residue interaction network of a backbone template to significantly accelerate the design process. Tests on real protein data show that our new protein design algorithm is able to solve many prob- lems that were previously unsolvable by the traditional exact search algorithms, and for the problems that can be solved with traditional provable algorithms, our new method can provide a large speedup by several orders of magnitude while still guaranteeing to find the global minimum energy conformation (GMEC) solution.