Complex Systems

A Travelling Salesman Approach to Protein Conformation Download PDF

Henrik Bohr
Søren Brunak
Department of Structural Properties of Matter,
The Technical University of Denmark, DK-2800 Lyngby, Denmark


A simple method for finding conformational substates of proteins is presented and realized through computer simulations. It is based on a procedure in which the amino acids in a protein take the places of the cities in the three-dimensional travelling salesman problem. Optimization by simulated annealing was employed in the computer simulations to obtain conformational substates originating from a given three-dimensional structure of the protein backbone. Two polypeptides, Avian Pancreatic Polypeptide and Leucin-Enkephalin, were modelled and compared with available x-ray diffraction data. The method gives an interesting spinoff: the possibility of assigning a measure of complexity to real protein structures, due to the fact that a metric on the set of interactions employed by the protein can be defined naturally.