Reducing the Search Space in Protein Structure Prediction

PhD defense by Rasmus Fonseca


The protein structure prediction problem is that of computationally predicting the three-dimensional structure of an amino acid chain from the sequence of amino acids alone. This has been an open problem for more than 30 years and developing a practical solution is widely considered the ’holy grail’ of computational biology. While ’de novo’ protein structure prediction is possible for some short chains, this thesis describes improved data structures and algorithms for representing and analyzing proteins that can help predict the structure of large proteins faster and more reliably.                  

This thesis consists of eight research papers. Half the papers address the problem of efficiently exploring the space of protein conformations such that promising structures are more frequently sampled. For example we investigate how hard constraints, which are rarely used in molecular modelling, can be formulated and used to improve optimization methods used in structure prediction.                       

The other half of this work deals with efficient data structures for representing protein structures. When performing a conformational search, atoms change positions and it is necessary to check for atom collisions very frequently. We present a data structure, based on bounding volume hierarchies, that decrease the computational time required to perform these operations by a factor of three compared to similar state-of-the-art methods. Another challenge when generating high-quality protein structures is to detect and remove packing flaws, i.e. small holes in the protein interior. We present a new method based on Delaunay tessellations that reduces the computational time of these detections four-fold compared to state-of-the-art methods.

Assessment Committee

  • Professor Christian Igel, Department of Computer Science, University of Copenhagen, chairman
  • Professor Jack Snoeyink, University of North Carolina, USA
  • Professor Anna Tramontano, "La Sapienza" University in Rome


Professor Pawel Winter, Department of Computer Science, University of Copenhagen

For an electronic copy of the thesis, please contact Jette Giovanni Møller,, research group secretary.