Pairwise and Multi-Component Protein-Protein Docking Using Exhaustive Branch-and-Bound Tri-Dimensional Rotational Searches
Docking protéique par paire et à plusieurs composants, à l'aide d'une exploration systématique de l'espace tri-dimensionnel des rotations par un algorithme de séparation et évaluation
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 “π-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. 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 data-driven computational restraints is demonstrated in this thesis, and this might be especially important for multi-body complexes. 3)The extension of the algorithm to dock trimeric complexes. Here, the proposed method is 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. 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.
La détermination des structures tri-dimensionnelles (3D) des complexes protéiques est cruciale pour l’avancement des recherches sur les processus biologiques qui permettent, par exemple, de comprendre le développement de certaines maladies et, si possible, de les prévenir ou de les traiter. Face à l’intérêt des complexes protéiques pour la recherche, les difficultés et le coût élevé des méthodes expérimentales de détermination des structures 3D des protéines ont encouragé l’utilisation de l’informatique pour développer des outils capables de combler le fossé, comme par exemple les algorithmes d’amarrage protéiques. Le problème de l’amarrage protéique a été étudié depuis plus de 40 ans. Cependant, le développement d’algorithmes d’amarrages précis et efficaces demeure un défi à cause de la taille de l’espace de recherche, de la nature approximée des fonctions de score utilisées, et souvent de la flexibilité inhérente aux structures de protéines à amarrer. Cette thèse présente un algorithme pour l’amarrage rigide des protéines, qui utilise une série de recherches exhaustives rotationnelles au cours desquelles seules les orientations sans clash sont quantifiées par ATTRACT. L’espace rotationnel est représenté par une hyper-sphère à quaternion, qui est systématiquement subdivisée par séparation et évaluation, ce qui permet un élagage efficace des rotations qui donneraient des clashs stériques entre les deux protéines. Les contributions de cette thèse peuvent être décrites en trois parties principales comme suit. 1) L’algorithme appelé EROS-DOCK, qui permet d’amarrer deux protéines. Il a été testé sur 173 complexes du jeu de données “Docking Benchmark”. Selon les critères de qualité CAPRI, EROS-DOCK renvoie typiquement plus de solutions de qualité acceptable ou moyenne que ATTRACT et ZDOCK. 2) L’extension de l’algorithme EROS-DOCK pour permettre d’utiliser les contraintes de distance entre atomes ou entre résidus. Les résultats montrent que le fait d’utiliser une seule contrainte inter-résidus dans chaque interface d’interaction est suffisant pour faire passer de 51 à 121 le nombre de cas présentant une solution dans le top-10, sur 173 cas d’amarrages protéine-protéine. 3) L’extension de EROSDOCK à l’amarrage de complexes trimériques. Ici, la méthode proposée s’appuie sur l’hypothèse selon laquelle chacune des trois interfaces de la solution finale doit être similaire à au moins l’une des interfaces trouvées dans les solutions des amarrages pris deux-à-deux. L’algorithme a été testé sur un benchmark de 11 complexes à 3 protéines. Sept complexes ont obtenu au moins une solution de qualité acceptable dans le top-50 des solutions. À l’avenir, l’algorithme EROS-DOCK pourra encore évoluer en intégrant des fonctions de score améliorées et d’autres types de contraintes. De plus il pourra être utilisé en tant que composant dans des workflows élaborés pour résoudre des problèmes complexes d’assemblage multi-protéiques.
Origin | Files produced by the author(s) |
---|
Loading...