6533b838fe1ef96bd12a4e04

RESEARCH PRODUCT

Arrangements de cercles sur une sphère: Algorithmes et Applications aux modèles moléculaires representés par une union de boules

subject

description

Since the early work of Richard et al., geometric constructions havebeen paramount for the description of macromolecules and macro-molecularassemblies. In particular, Voronoï and related constructions have beenused to describe the packing properties of atoms, to compute molecularsurfaces, to find cavities. This thesis falls in this realm, andafter a brief introduction to protein structure, makes fourcontributions.First, using the sweep line paradigm of Bentley and Ottmann, wepresent the first effective algorithm able to construct the exactarrangement of circles on a sphere. Moreover, assuming the circlesstem from the intersection between spheres, we present a strategy to reportthe covering list of a face of the arrangement---that is the list ofspheres covering it. Along the way, we ascertain the fact thatexactness of the arrangement can be achieved with a smallcomputational overhead.Second, we develop the algebraic and geometric primitives required by the sweepalgorithm, so as to make it generic and robust. These primitives are integrated ina broader context, namely the CGAL 3D Spherical Kernel.Third, we use the aforementioned machinery to tackle a computational structuralbiology problem, namely the selection of diverse conformations from a large redundant set.We propose to solve this selection problem by computingrepresentatives maximizing the surface area or the volume of theselection. From a geometric standpoint, these questions can be handledresorting to arrangements of circles and spheres.The validation is carried out along two lines. On the geometric side,we show that our selections match the molecular surface area ofselections output by standard strategies but using a smaller numberof conformers by one and two orders of magnitude. Onthe docking side, we show that our selections can significantlyimprove 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 ofCGAL.