Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


A branch and cut algorithm for the optimal solution of the side-chain placement problem

Althaus, Ernst and Kohlbacher, Oliver and Lenhof, Hans-Peter and Müller, Peter

MPI-I-2000-1-001. January 2000, 26 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
Rigid--body docking approaches are not sufficient to predict the structure of a
protein complex from the unbound (native) structures of the two proteins.
Accounting for side chain flexibility is an important step towards fully
flexible protein docking. This work describes an approach that allows
conformational flexibility for the side chains while keeping the protein
backbone rigid. Starting from candidates created by a rigid--docking
algorithm, we demangle the side chains of the docking site, thus creating
reasonable approximations of the true complex structure. These structures are
ranked with respect to the binding free energy. We present two new techniques
for side chain demangling. Both approaches are based on a discrete
representation of the side chain conformational space by the use of a rotamer
library. This leads to a combinatorial optimization problem. For the solution
of this problem we propose a fast heuristic approach and an exact, albeit
slower, method that uses branch--\&--cut techniques. As a test set we use the
unbound structures of three proteases and the corresponding protein
inhibitors. For each of the examples, the highest--ranking conformation
produced was a good approximation of the true complex structure.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
main.ps6557 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Althaus, Ernst and Kohlbacher, Oliver and Lenhof, Hans-Peter and M{\"u}ller, Peter},
  TITLE = {A branch and cut algorithm for the optimal solution of the side-chain placement problem},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2000-1-001},
  MONTH = {January},
  YEAR = {2000},
  ISSN = {0946-011X},