| Popis: |
Depuis les travaux précurseurs de Richard et al., les constructions géométriquesoccupent 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 à lastructure 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 effectifpour construire l'arrangement exact de cercles sur une sphère.De plus, en supposant que les cercles proviennent de l'intersection entresphères, une stratégie pour calculer les listes couvrantes d'une face del'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'algorithmiquerobuste, 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étriquesrequises par l'algorithme de balayage afin de le rendre générique et robuste. Ces primitivessont 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èmede 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électionsdont 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 demanière significative les résultats obtenus à l'aide d'un algorithme manipulant desparties flexibles.Pour finir, nous discutons les problèmes et choix d'implémentation, enles replaçant dans le contexte de la librairie CGAL. |
