Arrangements de cercles sur une sphère : algorithmes et applications aux modèles moléculaires représentés par une union de boules
Institution:
DijonDisciplines:
Directors:
Abstract EN:
Since the early work of Richard et al. , geometric constructions have been paramount for the description of macromolecules and macro-molecular assemblies. In particular, Voronoï and related constructions have been used to describe the packing properties of atoms, to compute molecular surfaces, to find cavities. This thesis falls in this realm, and after a brief introduction to protein structure, makes four contributions. First, using the sweep line paradigm of Bentley and Ottmann, we present the first effective algorithm able to construct the exact arrangement of circles on a sphere. Moreover, assuming the circles stem from the intersection between spheres, we present a strategy to report the covering list of a face of the arrangement---that is the list of spheres covering it. Along the way, we ascertain the fact that exactness of the arrangement can be achieved with a small computational overhead. Second, we develop the algebraic and geometric primitives required by the sweep algorithm, so as to make it generic and robust. These primitives are integrated in a broader context, namely the CGAL 3D Spherical Kernel. Third, we use the aforementioned machinery to tackle a computational structural biology problem, namely the selection of diverse conformations from a large redundant set. We propose to solve this selection problem by computing representatives maximizing the surface area or the volume of the selection. From a geometric standpoint, these questions can be handled resorting to arrangements of circles and spheres. The validation is carried out along two lines. On the geometric side, we show that our elections match the molecular surface area of selections output by standard strategies but using a smaller number of onformers by one and two orders of magnitude. On the docking side, we show that our selections can significantly improve the results obtained for a flexible-loop docking algorithm. Finally, we discuss the implementation issues and the design choices, in the context of the best practices underlying the development of CGAL.
Abstract FR:
Depuis les travaux précurseurs de Richard et al. , les constructions géométriques occupent une place importante dans la description des macro-molécules et leurs assemblages. En particulier, certains complexes cellulaires liés au diagramme de Voronoï ont été utilisés pour décrire les propriétés de compacité des empilement atomiques, calculer des surfaces moléculaires, ou encore détecter des cavités à la surface des molécules. Cette thèse se positionne dans ce contexte, et après une brève introduction à la structure des protéines, détaille quatre contributions. Premièrement, en utilisant le principe de balayage introduit par Bentley et Ottmann, cette thèse présente le premier algorithme effectif pour construire l'arrangement exact de cercles sur une sphère. De plus, en supposant que les cercles proviennent de l'intersection entre sphères, une stratégie pour calculer les listes couvrantes d'une face de l'arrangement (i. E. La liste des boules qui la recouvrent) est proposée. L'exactitude n'étant pas une fin en soi, mais plutôt une façon de rendre l'algorithmique robuste, nous montrons expérimentalement que le surcoût induit est modeste. Deuxièmement, cette thèse développe les primitives algébriques et géométriques requises par l'algorithme de balayage afin de le rendre générique et robuste. Ces primitives sont intégrées dans une contexte plus général, à savoir le noyau CGAL pour les objets sphériques. Troisièmement, la machinerie introduite est utilisée pour traiter un problème de biologie structurale computationelle : la sélection d'un sous-ensemble varié à partir d'un ensemble redondant de conformations de boucles. Nous proposons de résoudre ce problème de sélection en retenant les représentants qui maximisent l'aire ou le volume de la sélection. Ces questions peuvent être traitées géométriquement à l'aide d'arrangements de cercles sur une sphère. La validation est faîte sur deux fronts. D'un point de vue géométrique, nous montrons que notre approche génère des sélections dont l'aire de la surface moléculaire équivaut à celle de sélections obtenues par des stratégies classiques, mais qui sont de taille nettement inférieure. Du point de vue amarrage de protéines, nous montrons que nos sélections améliorent de manière significative les résultats obtenus à l'aide d'un algorithme manipulant des parties flexibles. Pour finir, nous discutons les problèmes et choix d'implémentation, en les replaçant dans le contexte de la librairie CGAL.