Search

The number of local minima of the potential energy landscape (PEL) of molecular systems generally grows exponentially with the number of degrees of freedom, so that a crucial property of PEL exploration algorithms is their ability to identify local minima, which are low lying and diverse. In this work, we present a new exploration algorithm, retaining the ability of basin hopping (BH) to identify local minima, and that of transition based rapidly exploring random trees (T-RRT) to foster the exploration of yet unexplored regions. This ability is obtained by interleaving calls to the extension procedures of BH and T-RRT, and we show tuning the balance between these two types of calls allows the algorithm to focus on low lying regions. Computational efficiency is obtained using state-of-the art data structures, in particular for searching approximate nearest neighbors in metric spaces. We present results for the BLN69, a protein model whose conformational space has dimension 207 and whose PEL has been studied exhaustively. On this system, we show that the propensity of our algorithm to explore low lying regions of the landscape significantly outperforms those of BH and T-RRT.

Predicting protein binding affinities from structural data has remained elusive, a difficulty owing to the variety of protein binding modes. Using the structure-affinity-benchmark (SAB, 144 cases with bound/unbound crystal structures and experimental affinity measurements), prediction has been undertaken either by fitting a model using a handfull of predefined variables, or by training a complex model from a large pool of parameters (typically hundreds). The former route unnecessarily restricts the model space, while the latter is prone to overfitting. We design models in a third tier, using 12 variables describing enthalpic and entropic variations upon binding, and a model selection procedure identifying the best sparse model built from a subset of these variables. Using these models, we report three main results. First, we present models yielding a marked improvement of affinity predictions. For the whole dataset, we present a model predicting Kd within 1 and 2 orders of magnitude for 48% and 79% of cases, respectively. These statistics jump to 62% and 89% respectively, for the subset of the SAB consisting of high resolution structures. Second, we show that these performances owe to a new parameter encoding interface morphology and packing properties of interface atoms. Third, we argue that interface flexibility and prediction hardness do not correlate, and that for flexible cases, a performance matching that of the whole SAB can be achieved. Overall, our work suggests that the affinity prediction problem could be partly solved using databases of high resolution complexes whose affinity is known.

We present novel algorithms and software addressing four core problemsin computational structural biology, namely analyzing a conformationalensemble, comparing two conformational ensembles, analyzing a sampledenergy landscape, and comparing two sampled energy landscapes. Usingrecent developments in computational topology, graph theory, andcombinatorial optimization, we make two notable contributions. First,we a present a generic algorithm analyzing height fields. We then usethis algorithm to perform density based clustering of conformations,and to analyze a sampled energy landscape in terms of basins andtransitions between them. In both cases, topological persistence isused to manage ruggedness. Second, we introduce two algorithms tocompare transition graphs. The first is the classical earth mover distance metric which depends only on local minimum energyconfigurations along with their statistical weights, while the secondincorporates topological constraints inherent to conformationaltransitions.Illustrations are provided on a simplified protein model (BLN69), whosefrustrated potential energy landscape has been thoroughly studied.The software implementing our tools is also made available, and shouldprove valuable wherever conformational ensembles and energy landscapesare used.

Choosing balls that best approximate a 3D object is a non-trivial problem. To answer it, we first address the inner approximation problem, which consists of approximating an object FO defined by a union of n balls with k

Reconstruction by data integration is an emerging trend to reconstruct large protein assemblies, but uncertainties on the input data yield average models whose quantitative interpretation is challenging. This article presents methods to probe fuzzy models of large assemblies against atomic resolution models of subsystems. Consider a toleranced model (TOM) of a macromolecular assembly, namely a continuum of nested shapes representing the assembly at multiple scales. Also consider a template namely an atomic resolution 3D model of a subsystem (a complex) of this assembly. We present graph-based algorithms performing a multi-scale assessment of the complexes of the TOM, by comparing the pairwise contacts which appear in the TOM against those of the template. We apply this machinery on TOM derived from an average model of the nuclear pore complex, to explore the connections among members of its well-characterized Y-complex.

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 {\em 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 $\alpha$-complex, which provides a filtration called the $\lambda$-complex. Fourth, we propose a naive algorithm to compute the CW VD. Finally, we use the $\lambda$-complex to assess the quality of models of large protein assemblies, as these models inherently feature ambiguities.

We developed a model of macromolecular interfaces based on the Voronoi diagram and the related alpha-complex, and we tested its properties on a set of 96 protein-protein complexes taken from the Protein Data Bank. The Voronoi model provides a natural definition of the interfaces, and it yields values of the number of interface atoms and of the interface area that have excellent correlation coefficients with those of the classical model based on solvent accessibility. Nevertheless, some atoms that do not lose solvent accessibility are part of the interface defined by the Voronoi model. The Voronoi model provides robust definitions of the curvature and of the connectivity of the interfaces, and leads to estimates of these features that generally agree with other approaches. Our implementation of the model allows an analysis of protein-water contacts that highlights the role of structural water molecules at protein-protein interfaces.

Let PC be a 3D point cloud and e be a positive value called tolerance. We aim at constructing a triangulated surface S based on a subset PCU of PC such that all the points in PCL=PC∖PCU are at distance at most e from a facet of S. (PCU and PCL respectively stand for Point Cloud Used and Point Cloud Left.) We call this problem simplification with geometric guarantees. This paper presents a new framework to simplify with geometric guarantees. The approach relies on two main ingredients. First an oracle providing information on the surface being reconstructed even though the triangulated surface itself has not been computed. Second, a reconstruction algorithm providing incremental updates of the reconstructed surface, as well as a fast point-to-triangles distance computation. The oracle is used to guess a subset of the point cloud from which a triangulated surface is reconstructed. It relies on an implicit surface the triangulated surface is an approximation of, and is therefore available before the triangle mesh. The point-to-triangles distance computation and the local updates are then invoked to insert new vertices until the tolerance is met. We also present a detailed experimental study which shows the efficiency of the simplification process both in terms of simplification rate and running time. To the best of our knowledge, this algorithm is the first one performing coarse-to-fine surface simplification with geometric guarantees.

Data structures that handle very complex scenes hundreds of thousands of objects have in the past either been laboriously built by hand, or have required the determination of unintuitive parameter values by the user. It is often the case that an incorrect choice of these parameters can result in greedy memory requirements or severely degraded performance. As a remedy to this problem we propose a new data structure which is fully automatic since it does not require the user to determine any input parameters. The structure is built by first filtering the input objects by size, subsequently applying a clustering step to objects of the same size and finally building a hierarchy of uniform grids . We then show that this data structure can be efficiently constructed. The implementation of the shows that the new structure is stable since it's memory requirements grow linearly with the size of the scene, and that it presents a satisfactory compromise between memory usage and computational efficiency. A detailed comparison with previous data structures is also presented in the results.