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. |
Export this paper
