Title: “Pairwise and Multi-Component  Protein-Protein Docking Using  Exhaustive Branch-and-Bound  Tri-Dimensional Rotational Searches”

Referees:

• Frederic Cazals, Research Director Inria, Sophia Antipolis Mediterranee
• Raphael Guerois, Research Scientist CEA, Institut de Biologie Integrative de la Cellule, Saclay

Examiners:

• Juan Cortes, Research Director CNRS, Laboratoire d’analyse et d’architecture des systemes, Toulouse
• Pablo Chacon, Research Scientist CSIC, Rocasolano Physical Chemistry Institute, Madrid, Spain

Advisors:

• David W. Ritchie, Research Scientist, LORIA, Nancy
• Isaure Chauvot de Beauchene, Research Scientist, CNRS, LORIA, Nancy
• Marie-Dominique Devignes, Research Scientist, CNRS HDR, LORIA, Nancy

Abstract:

Determination of tri-dimensional (3D) structures of protein complexes is crucial to increase research advances on biological processes that help, for instance, to understand the development of diseases and their possible prevention or treatment. The difficulties and high costs of experimental methods to determine protein 3D structures and the importance of protein complexes for research have encouraged the use of computer science for developing tools to help filling this gap, such as protein docking algorithms. The protein docking problem has been studied for over 40 years. However,
developing accurate and efficient protein docking algorithms remains a challenging problem due to the size of the search space, the approximate nature of the scoring functions used, and often the inherent flexibility of the protein structures to be docked.

This thesis presents an algorithm to rigidly dock proteins using a series of exhaustive 3D branch-and-bound rotational searches in which non-clashing orientations are scored using ATTRACT. The rotational space is represented as a quaternion “pi-ball”, which is systematically sub-divided in a “branch-and-bound” manner, allowing efficient pruning of rotations that will give steric clashes. The contribution of this thesis can be described in three main parts as follows. 1) The algorithm called EROS-DOCK to assemble two proteins. It was tested on 173 Docking Benchmark complexes. According to the CAPRI quality criteria, EROS-DOCK typically gives more acceptable or medium quality solutions than ATTRACT and ZDOCK. 2)The extension of the EROS-DOCK algorithm to allow the use of atom-atom or residue-residue distance restraints using a text file. The results show that using even just one residue-residue restraint in each interaction interface is sufficient to increase the number of cases with acceptable solutions within the top 10 from 51 to 121 out of 173 pairwise docking cases. Hence, EROS-DOCK offers a new improved search strategy to incorporate experimental data, of which a proof-of-principle using synthetic data is demonstrated in this thesis, and that this might be especially important for multi-body complexes. 3)The extension of the algorithm to dock trimeric complexes. However, finding an optimal solution is a combinatorially hard problem. Thus, the method proposed was based on the premise that all of the interfaces in a multi-body docking solution should be similar to at least one interface in each of the lists of pairwise docking solutions. Then, a new fast technique to calculate the RMSD between pairs of transformation matrices and an adaptation of the branch-and-bound rotational search algorithm were used to accelerate the search for low RMSD docking solutions. The algorithm was tested on a home-made benchmark of 11 three-body cases. Seven complexes obtained at least one acceptable quality solution in the top 50.

In future, the EROS-DOCK algorithm can evolve by integrating improved scoring functions and other types of restraints. Moreover, it can be used as a component in elaborate workflows to efficiently solve complex problems of multi-protein assemblies.