F Cazals
email: frederic.cazals@sophia.inria.fr

Revisiting the Voronoi description of Protein-Protein interfaces: Algorithms

Keywords: Protein interfaces, Computational Geometry, Voronoi diagrams, Geometric patterns

Describing macro-molecular interfaces is key to improve our understanding of the specificity and of the stability of macro-molecular interactions, and also to predict complexes when little structural information is known. Ideally, an interface model should provide easy-tocompute geometric and topological parameters exhibiting a good correlation with important bio-physical quantities. It should also be parametric and amenable to comparisons. In this spirit, we recently developed an interface model based on Voronoi diagrams, which proved instrumental to refine state-of-the-art conclusions and provide new insights. This paper formally presents this Voronoi interface model. First, we discuss its connexion to classical interface models based on distance cut-offs and solvent accessibility. Second, we develop the geometric and topological constructions underlying the Voronoi interface, and design efficient algorithms based on the Delaunay triangulation and the α-complex. We conclude with perspectives. In particular, we expect the Voronoi interface model to be particularly well suited for the problem of comparing interfaces in the context of large-scale structural studies.

Introduction

On classical protein -protein interface models

Modeling interfaces. Understanding the stability and the specificity of macromolecular interactions is a key endeavour in computational structural biology. Such an endeavour requires on the one hand describing non-covalent interactions for the interfaces of complexes which have been solved experimentally, and on the other hand developing algorithms able to predict complexes when little or no structural information on the partners is known. On a per-complex basis, interface models allow one to investigate correlations between structural parameters and key bio-physical properties such as the conservation of residues, their polarity, the water dynamics at the interface, mutagenesis data, etc. For large scale experiments in the context of proteomics, the comparison of binding patches associated to interface models allow, in particular, the investigation of putative partners between orphan molecules. Classical interface models. Classical interface models are twofold. May be the most widely used model is the so-called geometric footprint also called distancebased model, which consists of considering all pairs of atoms within a distance threshold d, typically in the range 5-8 Å. But as illustrated on Fig. 1, considering all atoms of one partner which are within distance d from the second partner results in a bias towards convex regions [START_REF] Grünberg | Complementarity of structure ensembles in protein-protein binding[END_REF]. Another very popular interface model is that based on the Solvent Accessible Surface (SAS). Recall that the SAS is the boundary of balls with expanded radii, i.e. Van der Walls radii expanded by r = 1.4 Å to account for a water probe. In this model, an interface atom is an atom contributing to the SAS of its own sub-unit, but losing part of this exposed surface in the complex. See Fig. 2. Interface atoms identified this way can further be classified as exposed or buried, depending on whether they retain accessibility in the complex, the former and latter making up the so-called rim and core of the interface. But as established in [START_REF] Cazals | Revisiting the voronoi description of protein-protein interfaces[END_REF] and explained in section 2.1, the SAS model actually omits privileged contacts.

Overall, a general drawback of these two models is that they do not provide a rich framework to compute pieces of information such as volume and surface areas, curvature information, dissection of the interface into patches. Instead, the computation of such quantities requires running dedicated algorithms.

The Voronoi interface

Intuitive presentation. Recall that the Euclidean Voronoi diagram of a collection of sample points is the partition of the ambient space into convex cells, such that all points in a cell have the sample associated to the cell as nearest neighbor. In bio-chemistry, since atoms' radii depend on their chemical type, one replaces the Euclidean distance by the so-called power distance1 . Abusing terminology, we still call the resulting diagram a Voronoi diagram. In the sequel, we shall consider the Voronoi diagram of atoms with expanded radii. See Fig. 3 for a 2D illustration.

Neighbors in a Voronoi diagram are actually privileged neighbors. That is, given two neighboring spheres S i and S j , and for any point p found on the dual Voronoi face, one has π(p, S i ) = π(p, S j ) < π(p, S k ), ∀k = i, j. This property is the main incentive for using pairs of neighboring regions to report interface neighbors. However, two atoms may share a Voronoi face, yet their relative distance might be arbitrarily large. To get around this difficulty, let a restricted ball or restriction be the intersection of this ball with its Voronoi region, see e.g. the red ball on Fig. 3(a). Focusing on pairs of neighboring restrictions instead of pairs of neighboring Voronoi regions allows one to report pairs of privileged neighbors without resorting to a distance cutoff. We illustrate this construction to define our Voronoi interface model. Consider a complex involving two partners A and B, and denote W the water molecules, if any. These types are also referred to as colors. Atoms of type A/B/W are denoted a i /b i /w i , respectively.

Let an interface water molecule be a water molecule such that its restriction has neighboring restrictions of type A and B. Water molecules which are not at the interface are called bulk water molecules. As illustrated on Fig. 3(a), our interface features pairs of restrictions of type [A; B] or [A; W ] or [B; W ], with W standing for interface water molecules. Each pair actually conveys two pieces of information, namely the atoms associated to the restrictions, and the Voronoi facet, also called tile, dual of this edge. As illustrated on Fig. 3(b), an interface atom is an atom involved in at least one pair. Focusing on two types allows one to define three bicolor interfaces. That is, tiles of type AB (AW and BW ) define the interface AB (AW and BW respectively). Tiles of type AB define direct contacts between the partners, while tiles of type AW and BW define contacts between these partners which are mediated by interface water molecules. The union of tiles AW and BW defines the AW-BW interface. The union of the AW-BW and AB interfaces defines the ABW interface, which separates the partners and gives a global overview of the interaction area, regardless of the role played by water molecules. See Fig. 3(c,d).

Interestingly, the interface ABW can be shelled into concentric shellsprosaically speaking the process is similar to peeling an onion from the outside to the inside. The process yields a integer called the Voronoi Shelling Order or VSO to tiles and atoms. This VSO qualifies the depth of an atom at the interfacefrom one for rim atoms to an integer in the range 7-10 for most complexes. See Fig. 3(c,d).

Connexions to classical interface parameters. We now discuss the finding made with our interface model, and note in passing that the corresponding soft-ware, Intervor [START_REF] Loriot | Modeling macro-molecular interfaces with intervor[END_REF], can be run and retrieved from http://cgal.inria.fr/abs/Intervor, together with plugins for VMD and Pymol.

We established in [START_REF] Cazals | Revisiting the voronoi description of protein-protein interfaces[END_REF] that our model identifies a superset of interface atoms losing solvent accessibility [BCR + 04], which actually draws the attention to interactions between main chain atoms upon association. (Algorithms in section 2.1.) Interface tiles are naturally gathered into patches, which have been shown [START_REF] Cazals | Revisiting the voronoi description of protein-protein interfaces[END_REF] to be coherent with those obtained with classical clustering algorithms [START_REF] Chakrabarti | Dissecting protein-protein recognition sites[END_REF]. (Algorithms in sections 2.2, 2.3 and 3.2.) Quantifying the planarity of interfaces and patches is important, e.g. to estimate (de-)solvation energies and also to identify putative binding regions for docking. While previous studies have used strategies based on plane fitting [START_REF] Jones | Principles of protein-protein interactions[END_REF], the Voronoi interface comes with a notion of discrete (mean) curvature [START_REF] Cazals | Revisiting the voronoi description of protein-protein interfaces[END_REF], which allows to assess the curvature properties at any scale (from two tiles to the whole interface). (Algorithms in section 2.4.) Finally, the VSO provides a discrete interface depth parameterization which refines the dissection into a core and a rim [CCJ99,BCR + 04]. In [START_REF] Bouvier | Shelling the voronoi interface of protein-protein complexes reveals patterns of residue conservation, dynamics and composition[END_REF], this parameterization allowed us to sharpen the investigation of correlations between (i) the interface geometry, (ii) the location of polar residues [START_REF] Chakrabarti | Dissecting protein-protein recognition sites[END_REF], (iii) the location of conserved residues [GC05], (iv) the dynamics of interfacial water [START_REF] Mihalek | On itinerant water molecules and detectability of protein-protein interfaces through comparative analysis of homologues[END_REF]. (Algorithms in section 3.3.)

We note in passing that another Voronoi interface definition has been proposed in [START_REF] Ban | Interface surfaces for protein-protein complexes[END_REF]. This interface model uses the Voronoi diagram of the Van der Walls atoms (rather than the expanded radii), and closes small gaps at the interface using a growth process of the atoms which consists of expanding their squared radii by a value α. As a consequence, the atoms reported are not qualified with respect to solvent accessibility.

Bicolor Voronoi interfaces

In this section, we formally define bicolor Voronoi interfaces. We use the terminology of bicolor AB interface -the interface between the two proteins A and B, although the presentation is identical for any bicolor interface. We assume that the reader is familiar with the α-complex of a union of balls [START_REF] Edelsbrunner | Weighted alpha shapes[END_REF].

Bicolor interface and interface neighbors

To account for privileged contacts in the Voronoi diagram of atomic balls, we seek pairwise intersections of restrictions of different colors. To balls whose restrictions intersect actually define an edge in the α-complex of the balls for α = 0, whence the following: Definition 1. An AB interface edge is an edge of type AB in the α-complex of the balls B i , with α = 0; its endpoints are called interface atoms. The interface neighbors of a sphere S i are the atoms of the second molecule sphere S i is connected to through an interface edge. The AB interface is defined as the collection Voronoi facets dual of the AB interface edges. A Voronoi edge bounding an interface Voronoi facet is called an interface Voronoi edge.

With respect to interface atoms defined with the BSA criterion, one can prove the following:

Observation. 1 Any atom S i such that losing solvent accessibility during complex formation is an interface atom by Def. 1.

However, the converse is false, as already mentioned in section 1.1, since an interface atom by Def. 1 may not lose solvent accessibility. A sufficient-but not necessary-condition for that is met when the atom is buried in its own subunit, and a 2D illustration is provided on Fig. 4. On that figure, the maintenance of the so-called empty ball property which characterizes Delaunay triangulations results in the creation an edge between the buried atom centered at a 0 and the red atom centered at a 4 .

Topology of bicolor Voronoi interfaces

Consider a bicolor interface, say the AB interface. Since the interface is a subset of the Voronoi diagram, it is a cell complex. To further qualify its topology, we need to examine how Voronoi facets patch together. Since a facet is the dual of a bicolor edge, we examine the tetrahedra containing this edge. We define:

a 1 a 2 a 3 a 0 a 4 a 1 a 2 a 3 a 0
Fig. 4. In the Voronoi model, interface atoms can be buried (a) Atom centered at a0 is buried in its subunit (b) Yet, it makes an interface edge with atom centered at a4 in the complex.

Definition 2. The type of a tetrahedron featuring atoms of types A and B is denoted by a pair (i, j) where i, j respectively count the number of atoms of each type, and i + j = 4. Similarly, the type of a tetrahedron featuring an additional atomic type out of W, X is denoted by a triple (i, j, k), with k the number of atoms of the third type, and i + j + k = 4.

A case analysis of the types of tetrahedra yields:

Observation. 2 The bicolor interface has the following properties:

-A Voronoi edge bounding an AB Voronoi facet has one or two incident AB Voronoi facets. Such a Voronoi edge is on the interface boundary iff only one edge of its dual triangle is an interface edge of type AB. -The neighborhood of every Voronoi vertex is either a topological disk, a halftopological disk, or two half-topological disks pinched together at the Voronoi vertex. This later case correspond to a tetrahedron of type (2, 2), where two bicolor edges are interface edges, and these two edges span the four vertices of the tetrahedron.

An interface can be connected through a pinched Voronoi vertex of a type (2, 2) tetrahedron. For such a tetrahedron, out of the four bicolor edges, only two actually occur in the α-complex. Phrased differently, we have two independent bicolor pairs. See Figs. 5 and6. Since the intersection of the corresponding Voronoi facets does not encode a joint property of these pairs, we define: Definition 3. Two Voronoi facets are called edge-connected if they share a Voronoi edge. An edge-connected component of the interface is a collection of edge-connected Voronoi facets. The closed curves bounding an edge connected component are called the loops.

We now present the algorithms used to retrieve connected components and loops.

Computing bicolor interfaces and their boundaries

Retrieving connected components. Given an initial Voronoi facet f 0 dual of an edge e 0 , the exploration of the corresponding connected component requires running a breadth-first-search (or depth-first-search) like algorithm anchored at f 0 . To run such an algorithm, the only information required is the list of Voronoi facets edge connected to a given facet f . But two edge connected Voronoi facets are dual of edges of the same triangle. Therefore, to report the facets edge connected to a facet f dual of an edge e, we just need to report the Delaunay triangles (i)incident to e (ii)featuring a second bicolor edge whose type is that of e. This is easily done by rotating around edge e in the Delaunay triangulation. Upon completion of a connected component, we have a collection of Delaunay edges. We record them without any additional topological information as any such information is encoded in the Delaunay triangulation. As an example, we present an algorithm to retrieve the cycles bounding a connected component. This algorithm operates on the Delaunay triangulation, but takes constant time per boundary edge.

Retrieving the cycles bounding a connected component. Starting from an initial boundary Voronoi edge e, a given cycle (also called loop) can be computed by iteratively following the successor of e on the boundary of the connected component. Assume e is oriented and denote s(e), t(e) the corresponding source and target Voronoi vertices, and let T (v) be the tetrahedron associated with Voronoi vertex v. The successor of edge e is one of the four Voronoi edges dual of the facets of T (t(e)). Following observation 2, if the neighborhood of t(e) is a half-topological disk, tetrahedron T (t(e)) has only two facets whose dual Voronoi edges are boundary edges. Since e is one of them, extending the loop requires retrieving and following the second one. On the other hand, if t(e) is a pinched Voronoi vertex and if the four edges belong to the boundary of the connected component processed, there are three potential outgoing edges, but only one bounding the Voronoi facet which has e on its boundary. Again, extending the loop requires finding and following this edge. Equipped with this extension operation, computing the loop of a given edge e 0 requires picking an arbitrary orientation for e 0 , and following the boundary until the Voronoi vertex T (s(e 0 )) is encountered again. To retrieve all the loops, we just have to iterate over the remaining boundary edges which are not already part of a loop.

The previous description actually eludes a difficulty, namely the way infinite tetrahedra are handled. (Recall these are the tetrahedra featuring a triangle of the convex hull of the Delaunay triangulation). When such a tetrahedron is encountered during the extension of a loop, we do not report its Voronoi center but the weighted circumcenter of the finite facet -that is the center of the smallest sphere orthogonal to the three spheres associated with the vertices of the facet.

Geometry of connected components

The most straightforward geometric statistics for an interface are its surface area and its boundary length. Apart from these, another interesting quantity is the interface curvature. Since a bicolor interface is a piecewise linear orientable surface, the natural way to characterize its extrinsic curvature consists of using the mean curvature. Notice that since we aim at studying the way a surface is embedded in R 3 , the extrinsic curvature is more suited than the intrinsic Gauss curvature, which is related to topological invariants and in particular boundary properties -cf the Gauss-Bonnet theorem. Recall that the mean curvature of a polyhedral surface is carried out along edges [START_REF] Santaló | of Encyclopedia of Mathematics and its Applications[END_REF], the amount of mean curvature attached to an edge being defined by h(e) = β(e)l(e), with l(e) the edge length and β(e) the angle between the normals to the facets incident to e, the angle being counted positively (negatively) if e is convex (concave). We thus define s H = e∈IVE h(e), with IVE the collection of interior Voronoi edges of the interface.

In a bio-chemical setting, one expects dihedral angles to alternate. Therefore, large values of s H indicate that the interface facets bend in a coherent fashion at the interface scale. Notice that in case of interfaces with several connected components, the components must be oriented coherently for the sum to make sense. But since the angle between the Voronoi facets matches the angle between the corresponding Delaunay edges, implementing this constraint means initializing the orientation of all the components in the same way -e.g. from protein A to protein B. See Fig. 7.

On the geometry of interface facets

As seen in section 1.2, bicolor edges selected from the 0-complex allow one to report interface neighbors without resorting to a distance cutoff. Phrased differently, long edges belong to the Delaunay triangulation but not the α-complex. This filtering mechanism avoids using explicit solvent molecules, a strategy often resorted to in applications deriving statistical potentials from the Delaunay triangulation. However, this filtering mechanism does not provide any control on the geometry of the interface Voronoi facets, and in particular, large facets are expected near the convex hull of the atoms centers. In other words, interface edges encode the topology of the interface but not its geometry.

To retrieve a relevant geometric information, we build upon the observation that boundary atoms do not play a major role from an energetic standpoint [START_REF] Bogan | Anatomy of hot spots in protein interfaces[END_REF], so that one may discard selected boundary edges these atoms are involved in. One way to discard large Voronoi facets is the following. Recall than any simplex in the α-complex comes with a value µ which gives the weight of its largest orthogonal ball [START_REF] Edelsbrunner | Weighted alpha shapes[END_REF]. For an interface edge e, denoting w e the weight of its smallest ball, one can therefore discard the edge if µ/w e ≥ M , with M a positive number. Since weights of balls are equal to their square radii, the condition amounts to saying that the radii of the balls are within a factor √ M .

3 Tricolor interfaces and water molecules

The AW-BW interface

When considering an interface, an interesting question is the role played by structural water molecules2 . As these water molecules are described from the crystal as protein atoms are, we also expand their radius by the quantity r w . Notice again that this expansion aims at mimicking an implicit continuous layer of solvent molecules on the atoms found in the crystal -be they protein atoms of water molecules.

If one has three molecular types A, B, W , one can define three types of bicolor interfaces. But since we primarily care for the AB interface, contact of type AW and BW are of interest only when located near the AB interface, see Fig. 8. We therefore define: Definition 4. An interface water molecule is a ball of type W which is the vertex of at least one edge of type AW and at least one edge of type BW , both edges belonging to the α-complex of the balls B i , with α = 0. An AW (or BW ) interface edge is an edge of type AW (or BW ), with W an interface water molecule. The AW (BW ) interface is defined as the collection Voronoi facets dual of the AW (BW ) interface edges.

A further refinement consists of aggregating Voronoi facets of type AW and BW :

Definition 5. The AW-BW interface is the collection of Voronoi facets dual of edges of type AW or BW . A connected component of AW-BW interface is a collection of edge-connected Voronoi facets dual of interface edges of type AW or BW .

To study the AW or the BW or the AW-BW interface, observe that edge connected Voronoi facets of types AW and BW are defined from bicolor, tricolor or quadricolor tetrahedra. Let us analyze the last two cases. In such a tetrahedron, we identify the labels A and B -since we do not report facets dual of such edges, so that the configurations found are those of bicolor tetrahedra. More precisely, a tetrahedron of type AABW where AB edges are omitted yields the same topological configurations as a bicolor (3, 1) tetrahedron for any bicolor interface. A tricolor tetrahedron of type ABW W is similar to a bicolor (2, 2) tetrahedron for any bicolor interface. Finally, a ABW X tetrahedron is equivalent to a (2, 1, 1) tetrahedron for any bicolor interface.

Therefore, the AW , the BW , and the AW-BW interfaces have the same topological properties as the AB interface i.e. are surfaces with possibly pinched vertices.

The ABW interface

To assess the role of water molecules, and position relatively to one another the connected components of the AB and AW-BW interfaces, we define: Definition 6. The ABW interface is defined as the union of the AB and AW-BW interfaces.

But the topology of the union is more involved than that of the singletons. First, non-manifold Voronoi edges may appear -if the three facets dual of the corresponding triangle are present in the union of the two interfaces. Second, the boundary of the union may not be a one-manifold, and we call it a curve network or net for short, see Fig. 9. To deal with these difficulties, it is actually sufficient to compute the AB and AW-BW interfaces separately, run a Union-Find algorithm to maintain the connected components of the edge-connected components, and another union-find algorithm to maintain the connected components of the boundary loops of the connected components of the union. Finding the Voronoi edges along which connexions occur can be done while computing the interfaces, while running m Union-Find operations on a n-element set takes O(mα(m, n) with α(m, n) the inverse of Ackerman's function [START_REF] Tarjan | Data Structures and Network Algorithms[END_REF].

Shelling the ABW interface

Considering the edge-connectivity of interface tiles, define the depth or the Voronoi Shelling Order of a tile as the number of tiles visited to reach it from the interface boundary-any tile which has a boundary edge is at depth one. This VSO provides an integer-valued parameterization of the ABW interface, which refines the binary core-rim model discussed in section 1.1.

Conclusion and Outlook

The interface model presented in this paper proved instrumental to refine our understanding of correlations between structural properties of protein interfaces, and important bio-physical quantities. However, the topic of modeling interfaces remains largely open for several reasons.

First, as evidenced by the scoring round of the community-wise docking experiment CAPRI, the design of scoring functions is an active area of research, and structural parameters defined from interface models should prove instrumental in this context.

Second, the question of precisely aligning and comparing interfaces has barely been touched upon. The Voronoi interface model proved instrumental for the description of bio-chemical properties, and we believe that the precise topological and geometric information it encodes should ease the comparison of interfaces in exhaustive structural classification studies.

Finally, while modeling single molecules and complexes is done routinely using methods from potential theory (molecular dynamics simulations, normal modes), we are not aware of any significant work for the problem of modeling dynamic interfaces so as to possibly incorporate entropy-related terms into scoring functions.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Defining an interface based on a distance threshold creates a bias towards convex regions.

  Tile dual of pair (b 1 , w 1 ): dual of pair (a 1 , w 1 ) : AW interface Tile dual of pair (a 1 , b 1 ) : AB interface (d)

Fig. 3 .

 3 Fig. 3. (a) A fictitious complex with two atoms (red and blue) and two water molecules (in grey). The Voronoi diagram consists of the dashed-dotted line-segments. The interface comprises three pairs namely [a1; b1], [a1; w1], and [b1; w1]; water w2 is not at the interface. (b) Signal transduction complex (1tx4.pdb) : chains and interface atoms displayed with radii expanded by 1.4 Å, with interface water molecules in grey. (c) Shelling a fictitious 2D interface into three shells (d) Shelling the ABW interface of complex 1txa into concentric shells: transparent view of the shells.

Fig. 5 .Fig. 6 .Fig. 7 .

 567 Fig. 5. (a) Top view of a Delaunay triangle in 3d. Voronoi facets F1 and F2 meet along the Voronoi edge dual of the triangle, and are edge-connected (b)Side view of Delaunay tetrahedron contributing 2 bicolor interface edges. The dual Voronoi facets F1 and F2 meet at a pinched Voronoi vertex dual of a type (2, 2) tetrahedron, and are not edge-connected.

Fig. 8 .Fig. 9 .

 89 Fig.8. Water molecules centered at w1 and w2 are interface water molecules; that centered at w3 is not.

Recall that the power distance of a point p to a sphere S(ci, ri) is defined by π(p, Si) = cip

r 2 i .

A water molecule is termed structural if it is as stable as the surrounding atoms. In a crystal structure, this can be assessed thanks to B-factors.


Frédéric Cazals

Tom Dreyfus

Multi-scale Geometric Modeling of Ambiguous Shapes with Toleranced Balls and Compoundly Weighted α-shapes *

Abstract

Dealing with ambiguous data is a challenge in Science in general and geometry processing in particular. One route of choice to extract information from such data consists of replacing the ambiguous input by a continuum, typically a one-parameter family, so as to mine stable geometric and topological features within this family. This work follows this spirit and introduces a novel framework to handle 3D ambiguous geometric data which are naturally modeled by balls.

First, we introduce toleranced balls to model ambiguous geometric objects. A toleranced ball consists of two concentric balls, and interpolating between their radii provides a way to explore a range of possible geometries. We propose to model an ambiguous shape by a collection of toleranced balls, and show that the aforementioned radius interpolation is tantamount to the growth process associated with an additively-multiplicatively weighted Voronoi diagram (also called compoundly weighted or CW). Second and third, we investigate properties of the CW diagram and the associated CW α-complex, which provides a filtration called the λ-complex. Fourth, we sketch a naive algorithm to compute the CW VD. Finally, we use the λ-complex to assess the quality of models of large protein assemblies, as these models inherently feature ambiguities.

Introduction 1.Voronoi Diagrams and Applications

The Voronoi diagram of a finite collection of sites equipped with a generalized distance is the cell decomposition of the ambient space into equivalence classes of points having the same nearest sites for this distance. Voronoi diagrams are central constructions in science and engineering [START_REF] Okabe | Spatial Tessellations: Concepts and Applications of Voronoi Diagrams[END_REF], and their versatility actually comes from two sources. First, the great variability of sites and distances is a first source of diversity. While the most classical construction is the Euclidean distance diagram for points, the mere class of circles and weighted points yields as diverse diagrams as power, Apollonius and Möbius diagrams-see [START_REF] Boissonnat | Curved voronoi diagrams[END_REF] and Fig. 1. Second, the information encoded in a Voronoi diagram actually goes beyond the aforementioned cell decomposition. One can indeed consider the bisectors bounding the cells as the realization of a growth process defined by the distance, in the sense that the level sets of this distance intersect on the bisectors. This viewpoint motivated the development of α-complexes and α-shapes [START_REF] Edelsbrunner | Weighted alpha shapes[END_REF], a beautiful construction providing a filtration of the Delaunay triangulation dual of the Voronoi diagram, later complemented by the flow complex [START_REF] Giesen | The flow complex: A data structure for geometric modeling[END_REF]. From a mathematical standpoint, these developments are concerned with the topological changes undergone by the sub-level sets of the distance, which is the heart of Morse theory [START_REF] Milnor | Morse Theory[END_REF]. Ideas in this realm also motivated the development of topological persistence [START_REF] Edelsbrunner | Topological persistence and simplification[END_REF][START_REF] Cohen-Steiner | Stability of persistence diagrams[END_REF], a subject concerned with the assessment of the stability of topological features associated with the sub-level sets of a function defined on a topological space.

The success of α-shapes relies on two cornerstones. First, the aforementioned growth process gives access to a multi-scale analysis of the input sites. For example, the problem of reconstructing a shape from sample points can be tackled by considering the space-filling diagram consisting of balls grown around the sample points. Alas, a provably good reconstruction using this strategy requires a uniform sampling, which motivated the definition of more local growth processes. One may cite conformal αshapes [START_REF] Cazals | The conformal alpha shapes filtration[END_REF], where the growth process depends on the distance of the samples to the medial axis, and the scale-axis transform [START_REF] Giesen | The scale axis transform[END_REF] which provides a hierarchy of skeletal shapes based on a dilation (and retraction) of medial balls. Second, α-shapes inherently model objects represented by collections of balls-in particular molecules, and encode remarkable geometric and topological properties [START_REF] Edelsbrunner | The union of balls and its dual shape[END_REF]. For the particular case of proteins and small macro-molecular complexes, they have been instrumental to compute molecular surfaces [START_REF] Akkiraju | Triangulating the surface of a molecule[END_REF] and model interfaces [START_REF] Bouvier | Shelling the voronoi interface of proteinprotein complexes reveals patterns of residue conservation, dynamics and composition[END_REF].

Our developments are precisely motivated by the requirement to perform multi-scale analysis in computational structural biology.

Contributions

Structural proteomics studies are concerned by the identification and the modeling of molecular machines operating within the cell [GAG + 06], and a major endeavour consists of modeling assemblies involving from tens [START_REF] Lasker | Inferential Optimization for Simultaneous Fitting of Multiple Components into a CryoEM Map of Their Assembly[END_REF] to hundreds [ADV + 07] of polypeptide chains. This modeling requires integrating data coming from several experimental sources, these data being typically noisy and incomplete [AFK + 08]. In this context, the premises just discussed on α-shapes certainly hold: on the one hand, balls are the primitive of choice since we deal with atoms and molecules; on the other hand, multi-scale analysis are in order since we deal with ambiguous data and need to accommodate uncertainties on the shapes and positions of proteins within an assembly. In this context, we make the following contributions.

First, we introduce toleranced balls to model ambiguous geometric shapes. A toleranced ball consists of two concentric balls-the inner and outer balls, and interpolating between them allows one to replace an arbitrary ball by one-parameter family of balls. As illustrated on Fig. 2, the inner (outer) ball of a toleranced ball is meant to accommodate high (low) confidence regions. We note in passing that our approach bears some similarities with modeling with toleranced parts in engineering, where tolerances are generally accommodated thanks to Minkowski sums [START_REF] Latombe | Assembly sequencing with toleranced parts[END_REF]. Second, we show that the growth process associated with this interpolation is associated with a so-called additively-multiplicatively-weighted Voronoi diagram, also called compoundly weighted Voronoi diagram-CW VD for short. Third, we investigate properties of this CW diagram and its dual. Fourth, we present the filtration, called the λ-complex, induced on the dual by the growth process, and encoding all possible topologies associated with this growth process. Our analysis generalizes the so-called β-shapes [SCC + 06], i.e. the α-shape associated to an Apollonius diagram [START_REF] Boissonnat | Convex hull and voronoi diagram of additively weighted points[END_REF][START_REF] Boissonnat | Curved voronoi diagrams[END_REF][START_REF] Emiris | The predicates of the Apollonius diagram: algorithmic analysis and implementation[END_REF]. Fifth, we sketch an algorithm to compute the CW VD. Finally, we present experimental results on toleranced protein models. Due to the lack of space, proofs are omitted and the reader is referred [START_REF] Cazals | Multi-scale geometric modeling of ambiguous shapes with toleranced balls and compoundly weighted α-shapes[END_REF].

2 Toleranced Models and Compoundly Weighted Voronoi Diagram 2.1 CW-distance and toleranced balls Toleranced balls. Given a weighted point S i (c i ; µ i , α i ), with center c i and parameters (real numbers) µ i > 0 and α i , we define the additively-multiplicatively distance as follows:

λ(S i , p) = µ i || c i p || -α i . ( 1
)
This distance is associated with so-called compoundly-weighted Voronoi diagrams or CW VD for short [START_REF] Okabe | Spatial Tessellations: Concepts and Applications of Voronoi Diagrams[END_REF]. Geometrically speaking, this distance is best understood using the following growth process. Let a toleranced ball S i (c i ; r - i , r + i ) be a pair of concentric balls of radii r - i < r + i , centered at c i . These balls are called the inner and outer balls. Given a toleranced ball S i and a real parameter λ, consider the grown ball S i [λ] centered at c i and whose radius is defined by:

r i (λ) = r - i + λ(r + i -r - i ). (2)
Denoting

δ i = r + i -r - i , a point p is reached by this growth process once r i (λ) =|| c i p ||, that is λ(S i , p) = || c i p || δ i - r - i δ i . (3)
In other words, a toleranced ball S i (c i ; r - i , r + i ) is tantamount to a weighted point S i (c i ; µ i = 1/δ i , α i = r - i /δ i ); and reciprocally, a weighted point S i (c i ; µ i , α i ) is tantamount to a toleranced ball S i (c i ; r - i = α i /µ i , r + i = (1+α i )/µ i ). In the sequel, we shall use both terminologies and exchangeable refer to weighted point S i or toleranced ball S i .

Toleranced tangency and generalization of the empty ball property. For affine (Apollonius) Voronoi diagrams, it is well known that for each point centered on a Voronoi face, there exists a unique ball orthogonal (tangent) to the balls associated with the vertices of the dual simplex, and conflict free with all the other balls. To derive the analogue in the CW-case, consider a point p and two toleranced balls S i and S j such that λ(S i , p) = λ < λ(S j , p). For the pair S i and p, one gets with Eq. (1):

|| pc i || - α i µ i - λ µ i = 0 ⇔ || pc i || -r - i -λδ i = 0. ( 4
)
Similarly, for the pair S j and point p:

|| pc j || - α j µ j - λ µ j > 0 ⇔ || pc j || -r - j -λδ j > 0. ( 5
)
We summarize with the following definition, illustrated on Fig. 3:

Definition. 1. A ball B(p, λ)
which satisfies the condition of Eq. (4) w.r.t. a toleranced ball S i is called toleranced tangent (TT for short) to S i . A toleranced ball S j and a ball B(p, λ) which satisfy the condition of Eq. ( 5) are called conflict free.

Remark. 1. Equation (4) states that the inner ball B(c i , r - i ) and the ball B(p, λδ i )-which is the ball B(p, λ) scaled by δ i , are tangent. Similarly, condition (5) states that B(c j , r - j ) and B(p, λδ j ) do not intersect. We shall use this property to illustrate TT balls, see e.g. Fig. 3. Remark. 2. Let S be a collection of toleranced balls. Consider a ball B(p, λ) which is TT to a subset of balls T ⊂ S, and conflict free with the toleranced balls in S\T. The center p of this ball is found at the intersection of the spheres bounding the grown balls S i [λ] with S i ∈ T, and is located outside the grown balls S j [λ] with S j ∈ S\T.

The Compoundly Weighted Voronoi Diagram

Consider a collection S of n toleranced balls. The Compoundly Weighted Voronoi diagram is the partition of the space according to the nearest neighbor relationship, for the CW distance, that is:

V or(S i ) = {p ∈ R 3 | λ(S i , p) ≤ λ(S j , p)∀j = i}. (6)
More generally, denoting T k+1 a tuple of k + 1 toleranced balls, we are interested in V or(T k+1 ) = ∩ Si∈T k+1 V or(S i ). Naturally, we are also interested in the dual complex generalizing the Delaunay triangulation.

Bisectors in the CW case

The bisector of a tuple of toleranced balls T k+1 is the loci of points having the same CW distance w.r.t. every toleranced ball. We denote this bisector ζ(T k+1 ), and examine in turn the case for pairs, triples, and quadruples. Our analysis assumes that the δ i are not equal, as this is the Apollonius case [START_REF] Boissonnat | Curved voronoi diagrams[END_REF].

Bisector of two toleranced balls

Analysis. Let S i and S j be two toleranced balls. The following property describes the existence of the bisector ζ(i, j) of S i and S j :

Proposition. 1. S i is trivial w.r.t. toleranced ball S j iff δ i ≤ δ j and the following condition, which states that c i belongs to the interior of the Voronoi region of S j , holds:

λ(S j , c i ) < - r - i δ i . (7)
Assuming that ζ(i, j) exists, its geometry depends on the relative values of δ i and δ j . Assuming w.l.o.g. that δ i < δ j , S j grows faster than S i so that for a large enough value of λ, the grown ball S i [λ] is contained in its counterpart S j [λ], so that the bisector is a closed surface, with c i in the bounded region delimited by ζ(i, j). Matching the generalized distances shows that this surface is a degree-four algebraic surface. See Fig. 4 for a 2D illustration.

Extremal TT balls. If the bisector exists, it makes sense to track the TT balls such that the corresponding λ value is a local extremum. By radial symmetry w.r.t. the line joining the centers of the balls, such balls are necessarily centered at the intersection between the bisector and the line joining the centers. Assume w.l.o.g. that δ i < δ j . The minimal such ball, denoted

M i,j (m i,j , ρ i,j ) is such that S i [ρ i,j ] and S j [ρ i,j ] are tangent at m i,j . The maximal ball M i,j (m i,j , ρ i,j ) is such that S i [ρ i,j ] is interior-tangent to S j [ρ i,j ] at m i,j .
The parameters of these extremal TT balls are computed as follows:

Proposition. 2. The two extremal TT balls B(p, λ) of two toleranced balls are characterized by

λ = || c i c j || -(αr - i + βr - j ) αδ i + βδ j , (8)
and

c i p = α λδ i + r - i || c i c j || c i c j , (9)
where α = ±1 and β = ±1 depend on the ball processed (min or max) and the relative positions of S i and S j (case analysis in the proof ).

Bisector of three toleranced balls

Analysis. Consider three toleranced balls S i0 , S i1 , S i2 such that the bisector of each pair exists. To avoid the Apollonius case, we suppose without loss of generality that Extremal TT balls. In any case, there are two (possibly identical) extremal TT balls. If one bisector is a half straight line, these balls are found by intersecting this line with one of the other two bisectors.

δ i0 ≤ δ i1 ≤ δ i2 with δ i0 < δ i2 . If there is no intersection between ζ(i 0 , i 1 ) and ζ(i 0 , i 2 ), ζ(i 0 , i 1 , i 2 ) does
In the general case, identifying these two balls involves four equations in four unknowns-the coordinates of the center and the weight λ. Denote π the plane defined by the centers of the three balls. The growth of the balls being symmetric with respect to this plane, the fourth equation consists of constraining the center of an extremal TT ball to plane π. The calculation is covered by the following proposition for k = 2:

Proposition. 3. Let T k+1 = {S ij } j=0,.
..,k be a triple or quadruple of toleranced balls, i.e. k = 2 or k = 3. Computing the two extremal TT balls of the tuple T k+1 requires solving a degree four equation. A value solution λ of this equation is valid provided that λδ ij + r - ij ≥ 0, ∀j = 0, . . . , k. Geometrically, three intersecting spheres generically intersect in two points. The extreme TT balls correspond to the situations where these two points coalesce.

Bisector of four toleranced balls

Analysis. Consider four toleranced balls S i0 , S i1 , S i2 , S i3 such that the bisector of each pair exists. To avoid the Apollonius case, we suppose w.l.o.g. that δ i0 ≤ δ i1 ≤ δ i2 ≤ δ i3 with δ i0 < δ i3 . If the intersection of ζ(i 0 , i 1 ), ζ(i 0 , i 2 ) and ζ(i 0 , i 3 ) is empty, the intersection of all bisectors of pairs is empty and ζ(i 0 , i 1 , i 2 , i 3 ) does not exist, and reciprocally. If

ζ(i 0 , i 1 , i 2 , i 3 ) exists, we have ζ(i 0 , i 1 , i 2 , i 3 ) = ζ(i 0 , i 3 ) ∩ ζ(i 1 , i 2 , i 3
), from which the following analysis follows.

⊲ CWB.IV.1 The bisectors ζ(i 0 , i 3 ) and ζ(i 1 , i 2 , i 3 ) being a surface and a curve, their generic intersection, if any, consists of a finite set of points. As we shall see below, there are at most four such points. ⊲ CWB.IV.2 As a degenerate case, when

ζ(i 1 , i 2 , i 3 ) is a bounded curve, the intersection of ζ(i 1 , i 2 , i 3 ) and ζ(i 0 , i 3 ) may be ζ(i 1 , i 2 , i 3 ). In this case, ζ(i 0 , i 1 , i 2 , i 3 ) has the geometry of the bisector ζ(i 1 , i 2 , i 3 ) of three toleranced balls.
Extremal balls. We distinguish two cases. If ζ(i 0 , i 1 , i 2 , i 3 ) has the geometry of a bisector of three toleranced balls, we refer to the analysis carried out in section 3.1.2. Otherwise, ζ(i 0 , i 1 , i 2 , i 3 ) is reduced to at most four points, as shown by the following constructive proof of proposition 3:

Voronoi Diagram and its Dual Complex

Empty Voronoi regions. A toleranced ball whose region is empty is called trivial. Proposition 1 gives a condition of triviality for two toleranced balls. But triviality of a toleranced ball amidst a collection of balls is more complex, since a toleranced ball might not be trivial w.r.t. any other one, yet, it might be trivial with respect to their union. It can be checked that a toleranced ball S i is trivial w.r.t. a tuple of balls T provided that S i [λ] ⊂ Sj ∈T S j λ for all values of λ.

Dual Complex. The Voronoi region V or(T k+1 ) of a tuple T k+1 may have several connected components, each being termed a face. Each such face corresponds to the intersection of k + 1 Voronoi regions, so that we associate an abstract simplex or simplex for short in the dual complex. That is, if V or(T k+1 ) consists of m faces, on finds ∆ j (T k+1 ), j ∈ 1, . . . , m simplices in the dual complex. (The multiplicity is omitted if the tuple T k+1 yields a single simplex.) Assuming that the input toleranced balls are numbered from 1 to n, a simplex is identified by a list of integers, and inclusion between such lists defines a partial order on simplices. We therefore represent the dual complex by a Hasse diagram D S with one node per simplex. Note that we may also (arbitrarily) embed a simplex within the union of Voronoi faces it is associated with. See Fig. 5. Topological complications. A Voronoi region gets sandwiched between two neighbors when the corresponding toleranced ball defines a lens between the Voronoi region of two neighboring toleranced balls, a case also found in the Apollonius diagram. In the dual complex, the vertex of this toleranced balls has exactly two neighbors and the triangle corresponding to these three toleranced balls does not have any coface.

A Voronoi region might not be connected, and this may happen for tuples of size one to four. We illustrate this in 2D with Fig. 5. For a toleranced ball, consider S 4 whose Voronoi region is split into two faces, associated with the vertices (zero-dimensional simplices) ∆ 1 (4) and ∆ 2 (4) in the Hasse diagram. For two toleranced balls, note that the Voronoi region V or(S 1 , S 2 ) consists of two faces-open line segments in this case, yielding the simplices ∆ 1 (1, 2) and ∆ 2 (1, 2) in the Hasse diagram. For three toleranced balls, note that the triple (S 1 , S 2 , S 4 ) corresponds to two triangles.

A Voronoi region may not be simply connected. When one toleranced ball punches a hole into a face, the corresponding one-simplex does not have any coface. See e.g. toleranced ball S 7 and the simplex ∆(2, 7) on Fig. 5. When two toleranced balls punch a hole into a Voronoi region, the two-simplex they define does not have any coface either. Finally when three toleranced balls punch a hole into a Voronoi region, two tetrahedra of the dual complex share the same vertices, the same edges and same triangles. This latter case is illustrated in 2D, where a hole punched by two toleranced balls in a Voronoi region results in two triangles with the same vertices and the same edges. See ∆ 1 (2, 5, 6) and ∆ 2 (2, 5, 6) on Fig. 5.

Bounded and Unbounded Voronoi regions. A toleranced ball S i ∈ S is called maximal w.r.t. to S if δ i ≥ δ j , ∀j = i. A toleranced ball which is not maximal has a bounded Voronoi region in the CW VD of S, and the subset of maximal toleranced balls is denoted S max . The CW VD diagram of toleranced balls in S max is an Apollonius diagram since all δ i are equal, and a subset of balls in S max have an unbounded Voronoi region. Mimicking the affine case, a simplex is said to lie on the convex hull CH(S) of the dual complex if its dual Voronoi face is unbounded. The vertices of such simplices belong to S max .

Space-filling diagram and λ-complex

In this section, we investigate the domain F λ = ∪S i [λ] defined by the union of growing balls. We present the λ-complex filtration of the dual complex. The reader is referred to [START_REF] Edelsbrunner | Weighted alpha shapes[END_REF] for the affine weighted α-complex.

Gabriel and dominated simplices

In the affine case, changes in the α-complex are associated with Gabriel simplices: a Gabriel simplex ∆(T) is a simplex such that its minimal orthogonal ball M T is conflict free, and the simplex enters the α-complex when λ ≥ ρ T , with ρ T the weight of M T . The generalization to the CW setting is not straightforward since Voronoi regions might not be connected, and also since a tuple T generally has two extremal TT balls, respectively denoted M T (m T , ρ T ) and M T (m T , ρ T ). We now examine these two balls and refer the reader to Fig. 6 for an illustration. (To examine this figure, recall that a TT ball M (p, λ) is conflict free with a toleranced ball S i iff the scaled version of M by δ i i.e. M (p, δ i λ) does not intersect the inner ball of S i .)

Minimal TT balls and Gabriel simplices. If the center m T of the minimal TT ball M T belongs to the relative interior of a Voronoi face of the tuple, or equivalently the ball is conflict free, the simplex is called Gabriel.

Maximal TT balls and domination of simplices. For a simplex ∆(T), consider the intersection of the spheres bounding the grown balls, i.e.

I T [λ] = ∩ Si∈T ∂S i [λ]. (10)
In 3D, if T is a k + 1 tuple, I T [λ] is generically a 2 -k-sphere. Consider now a tuple such that the δ i of its balls are not all equal, and assume that T = A ∪ B, with A the balls realizing the maximum δ i in the tuple. The corresponding bisector is bounded and has a unique maximal TT ball M T . If this ball is conflict free, the spheres bounding the grown balls in T intersect until I T [λ] reduces to the point m T .

Beyond that point, the intersection of the spheres bounding grown balls in B is contained in the union of the grown balls in A. That is, as opposed to the Euclidean setting, the simplex ∆(T) does not catch a coface. The simplex ∆(T) whose Voronoi face contains m T is called dominant.

Similarly, consider a simplex ∆(U ) which is an ancestor of the dominant simplex ∆(T) in the Hasse diagram, with B ⊂ U T. (An ancestor is any node found on a path joining a zero simplex to ∆(T).) Such a simplex does not catch any coface either when point m T is reached by the growing balls. All such simplices are called dominated. To identify the moment in time where simplex ∆(U ) gets dominated, we introduce

γ ∆(U ) = ρ ∆(T) . (11)
The condition B ⊂ U T actually yields 2 cases, namely (i) U = B, or (ii) B U T. In three dimensions, enumerating these possibilities yields the following cases:

⊲ Dom.1 T = {S 1 , S 2 } with δ 1 > δ 2 : case (i) that is U = {S 2 }. ⊲ Dom.2 T = {S 1 , S 2 , S 3 } with δ 1 > δ 2 ≥ δ 3 : case (i) that is U = {S 2 , S 3 }. ⊲ Dom.3 T = {S 1 , S 2 , S 3 } with δ 1 = δ 2 > δ 3 : case (i) that is U = {S 3 }, and case (ii) that is U = {S 1 , S 3 } or U = {S 2 , S 3 }.
By convention and since a 4-tuple yields a discrete set of at most four tetrahedra, we say that a 3-simplex cannot be dominant-which prevents a 2-simplex from being dominated. Also, a 0-simplex cannot be dominant. Dominant and dominated simplices are important to describe the evolution of the boundary ∂F λ : upon getting dominated, a simplex does not contribute to ∂F λ anymore.

The λ-complex Filtration

The filtration. Equipped with Gabriel simplices, the following mimics the Euclidean setting: Definition. 2. The λ-complex K λ is a subset of the dual complex defined as follows: a simplex ∆(T) belongs to

K λ iff (i) ∆(T) is Gabriel and λ ≥ ρ ∆(T) , or (ii) ∆(T) is a face of ∆(U ) with ∆(U ) ∈ K λ .
Increasing λ results in a nested sequence of (abstract) simplicial complexes, which eventually coincide with the dual complex, so that the collection of λ-complexes forms a filtration.

Status of simplices.

The status of a simplex in the affine setting is described from the topology of its link. In the CW case, the presence of simplices without any coface as described in section 3.2 requires devising different classification criteria. For a simplex ∆(T), consider the intersection I T [λ] of Eq. (10). Upon increasing λ, this intersection sweeps the Voronoi region of the tuple. We base our classification on the portion of the Voronoi region swept by I T [λ] up to time λ. That is, a k-simplex of K λ is classified as follows:

-Singular: the region swept by I T [λ] up to time λ is contained in the relative interior of the dual of the simplex.

-Interior: the region swept by I T [λ] up to time λ contains the dual of the simplex in its interior.

-Regular: neither singular nor interior. quadruple is candidate if at least one radius of its TT balls is less than λ max .

Based on these candidate tuples, the algorithm consists of two steps. First, one 3-simplex is created for each solution of the quartic equation mentioned in proposition 3, provided that this solution defines a conflict free TT ball. Second, the k-skeleton of the CW VD is incrementally built, from k = 1 to k = 3. To build the k-skeleton, the cofaces of every possible simplex are retrieved from the (k -1)-skeleton, and these cofaces are used to build the boundary of the Voronoi faces contributed by the tuple. The reader is referred to [START_REF] Cazals | Multi-scale geometric modeling of ambiguous shapes with toleranced balls and compoundly weighted α-shapes[END_REF] for a precise description. We briefly comment on the implementation sketch which is interesting due to the interplay between the combinatorial, geometric, and algebraic levels.

Implementation

Sketch. The implementation follows the CGAL spirit, see http://www.cgal.org, and we sketch it in terms of concepts (a set of requirements) and models (a particular implementation). The class CW_dual representing the dual complex is templated by a combinatorial class providing the Hasse diagram representation, and by a geometric concept class CWGeometricKernel providing the predicates and constructions required. The corresponding generic model CW_geometric_kernel is itself templated by a concept class AlgebraicKernel providing the operations needed to deal with the extremal TT balls. As specified by propositions 2 and 3, computing these TT balls requires solving linear systems or a degree four algebraic equation, while the conflict free test requires evaluating the conflict free predicate of Eq. ( 5). We implemented a model of the AlgebraicKernel named CW_algebraic_kernel_double which uses CGAL's Algebraic_kernel_d_1-the latter provides efficient operations on univariate polynomials. The number type being double, this kernel does not provide exact predicates. Finally, the class CW_alpha_shape inherits from CW_dual and provides the tags and intervals detailed in Table 2.

Application to molecular models

Reconstructing Large Assemblies. Understanding the behaviour of living cells requires describing the structure and behaviour of a number of macro-molecular assemblies. While atomic models of small complexes can be obtained from X ray crystallography and/or NMR, the reconstruction of large assemblies such as molecular motors (cell locomotion), branched actin filaments (muscle contraction), chaperonin cavities (protein folding) or nuclear pore complexes (nucleo-cytoplasmic regulation) is more challenging. A recent trend in this context consists of performing the reconstruction from diverse experimental data [AFK + 08]. For example, cryo electron microscopy (EM) maps allows the reconstruction of envelopes of assemblies, typically at intermediate resolution (10-15 Å). Immuno-labelling combined with EM can be used to locate protein instances, but positioning uncertainties are faced due to the resolution of microscopes. Proteomics methods such as Tandem Affinity Purification provide lists of interacting proteins, but these are inherently ambiguous. The reconstruction of a model from such noisy and ambiguous data is clearly a challenge, and typical reconstruction procedures perform simulating annealing in the space of parameters describing the model, so as to maximize the agreement between this model and the experimental data available. We now examine the largest protein assembly known to date in eukaryotic cells, namely the Nuclear Pore Complex (NPC).

Application to The Nuclear Pore Complex. The NPC is a radially symmetric protein assembly regulating exchanges between the nucleus and the cytoplasm of eukaryotic cells, thanks to the lumen located in its center. The NPC involves 456 protein instances of 30 different protein types, and we term each connected subset of instances a complex in the sequel. The stoichiometry of a protein type is the number of its instances-a number in the range 8-16 for the NPC. Two remarkable papers reported putative models of the NPC, reconstructed from the integration of various experimental data [ADV + 07, AFK + 08]. A model of the NPC is a collection of balls. The reconstruction resorts to simulated annealing to define the balls (centers and radii) so as to maximize the agreement with experimental data. The whole procedure is very complex-the supplemental of the two Nature papers runs on 107 pages, and different levels of detail are actually used along the optimization procedure. At the finest level, which corresponds to the output, a given protein is represented by a number of balls in the range 1-12, depending on the protein type. The functional optimized being non convex, a total of 1000 models were selected. These models were further averaged to produce one density map per protein type, i.e. a 3D matrix where each pixel is endowed with the probability of being covered by an instance of that type. Refer to Fig. 2 for a 2D example. The maps being quite noisy, contouring a map does not in general allow one to precisely locate the instances of that type. Also, superimposing the 30 maps do not allow one to investigate the relative positions of the instances of all types. We use λ-shapes to make a collective assessment of these maps.

Applications of λ-shapes. As a pre-processing, we build a toleranced model for each map, based on its stoichiometry. The high confidence regions are defined as (clusters of) local maxima of the density. Starting from these anchors, a region growing algorithm is run until a region with prescribed volume is reached. Each connected component is then covered with one toleranced ball. Merging the toleranced models of the 30 types yields a toleranced model of the NPC consisting of 456 toleranced balls. The resulting reduced λ-complex for λ max = 1, computed in 11 minutes on an x86 64 bits architecture at 3.2HGz, is used for two purposes.

First, the topological persistence of connected components provides an assessment of the stability of complexes in the assembly. Our particular interest are the stable complexes, whose composition in terms of protein types can be discussed w.r.t. the aforementioned Tandem Affinity Purification data. Such a discussion will be reported elsewhere.

Second, we investigate the packing properties of instances : upon increasing λ, the number of connected components (#c.c.) of F λ decreases, and its volume V ol λ increases. The volume of a protein instance being estimated from its sequence of amino-acids, let V ol ref the sum of the volumes of all instances, and denote r λ = V ol λ /V ol ref .

Tracking the evolution of the number #c.c. thanks to a Union-Find algorithm applied to the simplices of the dual complex, we investigate the correlations between the three parameters (#c.c., λ, r λ ). This curve is presented on Fig. 8 for the 32 protein instances of a half-spoke, i.e. one of the 16 sub-units of the NPC. For a perfectly accurate model, one would expect one connected component for a value of r λ = 1, but we observe 10 of them in our case. Also, the last two consecutive values of λ triggering a drop of the number of c.c. are as follows: for λ = 0.62, there are two c.c. and r 0.62 = 3.46; for λ = 1.25, there is one c.c. and r 1.25 = 7.20. The corresponding grown balls are illustrated on Fig. 9. On this example, the fact that a 7-fold increase of volume occupancy is required to connect the instances hints at an imprecise positioning of selected proteins. In particular, the significant increase of r λ in-between #c.c. = 2 and #c.c. = 1 hints at a poor positioning of two instances located far away from the 30 remaining ones.

This type of analysis is being used to provide a thorough evaluation of putative pseudo-atomic NPC models, based on (i) the stability of complexes measured by topological persistence, (ii) a coherence analysis of the models w.r.t. Tandem Affinity Purification data, and (iii) quantitative statistics based on volume and surface calculations. These analysis will complement the qualitative discussions and hypothesis developed in [ADV + 07].

Conclusion and outlook

Handling ambiguous geometric shapes is non trivial, and the spirit of this work is to integrate modeling uncertainties in the geometric model, as opposed to making arbitrary decisions. As demonstrated, the problem of modeling with toleranced balls is tantamount to using a compoundly weighted Voronoi diagram, and the fact that a toleranced ball (or equivalently a weighted point) has two parameters provides additional modeling flexibility. Yet, a number of further developments are called for.

On the algorithmic side, designing an efficient algorithm to build the dual complex of the CW VD is an open question. While our algorithm fits our needs in molecular modeling, an efficient algorithm is a must for the framework to be used say in geometry processing. From a combinatorial perspective, the task is difficult though, in particular because Voronoi regions are not connected. From a numerical perspective, designing efficient predicates based on degree-four algebraic numbers is also challenging. Finally, the design of toleranced models also raises interesting questions falling in the realm of geometric optimization.

On the application side, toleranced models should have a clear leveraging power in computational structural biology. A major trend there is the reconstruction of large molecular machines from the integration of various experimental data. The models designed so far are not precise enough to be used for mechanistical simulations. We believe that toleranced models have the potential to allow for a precise assessment of such models with respect to biological data, and will help to establish atomic-resolution models.

More classical geometric applications should also benefit from toleranced models, in particular the representation of shapes based on skeletal representations and the medial axis transform, in the spirit of recent contributions such as conformal α-shapes and scale-axis transforms.

S i (c i , r i ), p) = p- c i 2 -r 2 i . (b) Apollonius diagram : d(S i (c i , r i ), p) = p-c i -r i (c) Möbius diagram : d(S i (c i , a i , r i ), p) = a i p -c i 2 -r 2 i . (a) (b) (c)

Figure 1

 1 Figure 1 Curved Voronoi diagrams of 7 circles / weighted points. (a) Power diagram d(S i (c i , r i ), p) = pc i 2 -r 2 i . (b) Apollonius diagram : d(S i (c i , r i ), p) = p-c i -r i (c) Möbius diagram : d(S i (c i , a i , r i ), p) = a i p -c i 2 -r 2 i .

Figure 2 A

 2 Figure 2 A fictitious molecule of three atoms undergoing conformational changes.(Inset) The two extreme conformations. (Main figure) Probability density map D and toleranced balls. The map D displays the probability for a given pixel to be covered by a random conformation. The toleranced balls cover the portion of the map D involving probabilities beyond a given threshold. Dashed lines represent the inner and outer balls of the toleranced balls. Note that higher the confidence / probability, the smaller the region between the inner and outer balls.

Figure 3 Figure 4

 34 Figure 3 Toleranced tangent (TT) balls and conflict free balls. In dashed lines, toleranced balls S 1 (0, 0; 1, 5), S 2 (0, 10; 2, 8), S 3 (4, -9; 1, 3). The three dotted circles represent S 1 [3/4], S 2 [3/4], S 3 [3/4]. The three circles centered at p are the scaled versions of ball B(p, 3/4); following remark 1, ball B(p, 3/4) is TT to S 1 and S 2 , and conflict free with S 3 .

Figure 5 Figure 6

 56 Figure5CW diagram and dual complex of 7 toleranced balls in 2D: S 1 = (-5, -5; 3, 7), S 2 = (5, 5; 3, 7), S 3 = (-1, 0; 4, 5), S 4 = (0, 0; 2, 5), S 5 = (8, 7; 2, 3), S 6 = (8, 5; 3, 4), S 7 = (1, 10; 1, 2). V or(S 3 ) and V or(S 1 , S 2 ) are not connected. V or(S 2 ) is not simply connected. δ 1 and δ 2 are maximal and S 1 , S 2 have unbounded Voronoi regions Conventions for the dual complex : 0-simplices: black dots; one-simplices: blue curves; two simplices: red dots. Note that S 4 is represented by two vertices ∆ 1 (4) and ∆ 2 (4). ∆ 1 (2, 5, 6) and ∆ 2 (2, 5, 6) share the three same edges. ∆(2, 7) does not bound any triangle.

Figure 7 Figure 8

 78 Figure7Restricted Voronoi regions for the CW VD of Fig.5for λ = 1. The 8 dual vertices and the 10 dual edges in the λ-complex are drawn in blue. ∆(5) and ∆(6) is interior and all other dual vertices are regular. There is no singular dual vertex. ∆(1, 3) and ∆(2, 7) are singular, ∆(2, 3), ∆(2, 5),∆(2, 6), ∆(5, 6) are interior and all other dual edges are regular. The 4 dual triangles in the λ-complex are represented by red Voronoi vertices.

Figure 9

 9 Figure 9 Half-spoke of the NPC : growing the balls in (a) so as to end up with a single connected component in (b). The volume of the right domain incurs a 7.2 fold ratio w.r.t. the volume of the isolated protein instances.

  not exist, and reciprocally. Assume that ζ(i 0 , i 1 , i 2 ) exists. Since at least one δ i differs from the other two, there is at most one Apollonius bisector. The geometry of ζ(i 0 , i 1 , i 2 ) depends on δ i0 , δ i1 and δ i2 , and one faces the following cases.⊲ CWB.III.1 If there is no Apollonius bisector, ζ(i 0 , i 1 , i 2 ) is a bounded curve resulting from the intersection of two CW bisectors. ⊲ CWB.III.2 If the Apollonius bisector is not a half straight line, ζ(i 0 , i 1 , i 2 ) is a bounded curve resulting from the intersection of one CW bisector, and one sheet of a hyperboloid (possibly degenerated to a hyperplane). ⊲ CWB.III.3 If the Apollonius bisector is a half straight line, ζ(i 0 , i 1 , i 2 ) is reduced to at most two intersection points. Note that if there are two intersection points, δ i1 = δ i2 and S i1 is included in and tangent to S i2 .

Acknowledgements. Svetlana Dokudovskaya is acknowledged for stimulating discussions. Michael Hemmer is acknowledged for his help with CGAL's algebraic kernel.

CW Classification of simplices

To classify simplices, we adopt the notations used in the affine case [START_REF] Edelsbrunner | Weighted alpha shapes[END_REF] and denote µ ∆(T) and µ ∆(T) the λ-values such that a simplex becomes regular and interior. For the affine α-complex, the classification of a simplex as singular, regular, or interior requires considering the four cases { Gabriel, not Gabriel } × { on the convex hull, not on the convex hull }. For simplices which are neither dominant nor dominated, these four possibilities are also found in the CW case-lines 1-4 of Table 2.

On the other hand, dominant and dominated simplices are not found on the convex hull-each such simplex involves at least one non-maximal ball, and always end up interior since the maximal TT ball of the tuple of a dominant simplex is conflict free. For dominant simplices, the two additional cases to be considered are Gabriel and non Gabriel-lines 5-6 in Table 2. Such a simplex becomes interior as soon as λ ≥ ρ ∆(T) . Similarly for dominated simplices, the two additional cases to be considered are Gabriel and non Gabriellines 7-8 in Table 2. Recall that a dominated simplex is always associated to a dominant simplex. Using the weight γ ∆(T) of the maximal TT ball of the tuple of the dominant simplex associated to the dominated simplex, see Eq. ( 11), the dominated simplex becomes interior as soon as λ ≥ γ ∆(T) .

These notions are illustrated on Fig. 7, which features the restricted Voronoi diagram, i.e. the grown balls restricted to their Voronoi regions. Note in particular that the status of simplices reads from the relative position of the restriction w.r.t. the associated Voronoi face, as specified in section 4.2.

Implementation and Experiments

Algorithm

We designed and implemented an output sensitive algorithm computing the dual complex, with cubic preprocessing time. The algorithm also accommodates the reduced λ-complex i.e. the λ-complex restricted to values λ ≤ λ max -that is the growth process if performed up to λ max .

The pre-processing consists of finding all tuples possibly contributing to the λ-complex for λ ≤ λ max . Up to triples, a tuple is candidate provided that its minimal TT ball has a radius less than λ max . A