Computing the exact arrangement of circles on a sphere, with applications in structural biology - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2007

Computing the exact arrangement of circles on a sphere, with applications in structural biology

Frédéric Cazals
Sebastien Loriot
  • Fonction : Auteur
  • PersonId : 836959

Résumé

Given a collection of circles on a sphere, we adapt the Bentley-Ottmann algorithm to the spherical setting to compute the {\em exact} arrangement of the circles. The algorithm consists of sweeping the sphere with a meridian, which is non trivial because of the degenerate cases and the algebraic specification of event points. From an algorithmic perspective, and with respect to general sweep-line algorithms, we investigate a strategy maintaining a linear size event queue. (The algebraic aspects involved in the development of the predicates involved in our algorithm are reported in a companion paper.) From an implementation perspective, we present the first effective arrangement calculation dealing with general circles on a sphere in an exact fashion, as exactness incurs a mere factor of two with respect to calculations performed using {\em double} floating point numbers on generic examples. In particular, we stress the importance of maintaining a linear size queue, in conjunction with arithmetic filter failures. From an application perspective, we present an application in structural biology. Given a collection of atomic balls, we adapt the sweep-line algorithm to report all balls covering a given face of the spherical arrangement on a given atom. This calculation is used to define molecular surface related quantities going beyond the classical exposed and buried solvent accessible surface areas. Spectacular differences w.r.t. traditional observations on protein - protein and protein - drug complexes are also reported.
Fichier principal
Vignette du fichier
rrSpheres-v1.pdf (813.85 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00118781 , version 1 (06-12-2006)
inria-00118781 , version 2 (06-12-2006)
inria-00118781 , version 3 (06-12-2006)
inria-00118781 , version 4 (18-09-2007)

Identifiants

  • HAL Id : inria-00118781 , version 4

Citer

Frédéric Cazals, Sebastien Loriot. Computing the exact arrangement of circles on a sphere, with applications in structural biology. [Research Report] RR-6049, INRIA. 2007, pp.56. ⟨inria-00118781v4⟩
155 Consultations
283 Téléchargements

Partager

Gmail Facebook X LinkedIn More