ART-RRT: As-Rigid-As-Possible search for protein conformational transition paths.

The possible functions of a protein are strongly related to its structural rearrangements in the presence of other molecules or environmental changes. Hence, the evaluation of transition paths of proteins, which encodes conformational changes between stable states, is important since it may reveal the underlying mechanisms of the biochemical processes related to these motions. During the last few decades, different geometry-based methods have been proposed to predict such transition paths. However, in the cases where the solution requires complex motions, these methods, which typically constrain only locally the molecular structures, could produce physically irrelevant solutions involving self-intersection. Recently, we have proposed ART-RRT, an efficient method for finding ligand-unbinding pathways. It relies on the exploration of energy valleys in low-dimensional spaces, taking advantage of some mechanisms inspired from computer graphics to ensure the consistency of molecular structures. This article extends ART-RRT to the problem of finding probable conformational transition between two stable states for proteins. It relies on a bidirectional exploration rooted on the two end states and introduces an original strategy to attempt connections between the explored regions. The resulting method is able to produce at low computational cost biologically realistic paths free from self-intersection. These paths can serve as valuable input to other advanced methods for the study of proteins. A better understanding of conformational changes of proteins is important since it may reveal the underlying mechanisms of the biochemical processes related to such motions. Recently, the ART-RRT method has been introduced for finding ligand-unbinding pathways. This article presents an adaptation of the method for finding probable conformational transition between two stable states of a protein. The method is not only computationally cost-effective but also able to produce biologically realistic paths which are free from self-intersection.

Controlled-advancement rigid-body optimization of nanosystems.

In this study, we propose a novel optimization algorithm, with application to the refinement of molecular complexes. Particularly, we consider optimization problem as the calculation of quasi-static trajectories of rigid bodies influenced by the inverse-inertia-weighted energy gradient and introduce the concept of advancement region that guarantees displacement of a molecule strictly within a relevant region of conformational space. The advancement region helps to avoid typical energy minimization pitfalls, thus, the algorithm is suitable to work with arbitrary energy functions and arbitrary types of molecular complexes without necessary tuning of its hyper-parameters. Our method, called controlled-advancement rigid-body optimization of nanosystems (Carbon), is particularly useful for the large-scale molecular refinement, as for example, the putative binding candidates obtained with protein-protein docking pipelines. Implementation of Carbon with user-friendly interface is available in the SAMSON platform for molecular modeling at https://www.samson-connect.net. © 2019 Wiley Periodicals, Inc.

Incremental solver for orbital-free density functional theory.

First-principle calculations are still a challenge since they require a great amount of computational time. In this article, we introduce a new algorithm to perform orbital-free density functional theory (OF-DFT) calculations. Our new algorithm focuses computational efforts on important parts of the particle system, which, in the context of adaptively restrained particle simulations (ARPS) allows us to accelerate particle simulations. © 2019 Wiley Periodicals, Inc.

Generating conformational transition paths with low potential-energy barriers for proteins.

The knowledge of conformational transition paths in proteins can be useful for understanding protein mechanisms. Recently, we have introduced the As-Rigid-As-Possible (ARAP) interpolation method, for generating interpolation paths between two protein conformations. The method was shown to preserve well the rigidity of the initial conformation along the path. However, because the method is totally geometry-based, the generated paths may be inconsistent because the atom interactions are ignored. Therefore, in this article, we would like to introduce a new method to generate conformational transition paths with low potential-energy barriers for proteins. The method is composed of three processing stages. First, ARAP interpolation is used for generating an initial path. Then, the path conformations are enhanced by a clash remover. Finally, Nudged Elastic Band, a path-optimization method, is used to produce a low-energy path. Large energy reductions are found in the paths obtained from the method than in those obtained from the ARAP interpolation method alone. The results also show that ARAP interpolation is a good candidate for generating an initial path because it leads to lower potential-energy paths than two other common methods for path interpolation.

Incremental update of electrostatic interactions in adaptively restrained particle simulations.

The computation of long-range potentials is one of the demanding tasks in Molecular Dynamics. During the last decades, an inventive panoply of methods was developed to reduce the CPU time of this task. In this work, we propose a fast method dedicated to the computation of the electrostatic potential in adaptively restrained systems. We exploit the fact that, in such systems, only some particles are allowed to move at each timestep. We developed an incremental algorithm derived from a multigrid-based alternative to traditional Fourier-based methods. Our algorithm was implemented inside LAMMPS, a popular molecular dynamics simulation package. We evaluated the method on different systems. We showed that the new algorithm's computational complexity scales with the number of active particles in the simulated system, and is able to outperform the well-established Particle Particle Particle Mesh (P3M) for adaptively restrained simulations. © 2018 Wiley Periodicals, Inc.

ART-RRT: As-Rigid-As-Possible exploration of ligand unbinding pathways.

This article proposes a method to efficiently generate approximate ligand unbinding pathways. It combines an efficient tree-based exploration method with a morphing technique from Computer Graphics for dimensionality reduction. This method is computationally cheap and, unlike many existing approaches, does not require a reaction coordinate to guide the search. It can be used for finding pathways with known or unknown directions beforehand. The approach is evaluated on several benchmarks and the obtained solutions are compared with the results from other state-of-the-art approaches. We show that the method is time-efficient and produces pathways in good agreement with other state-of-the-art solutions. These paths can serve as first approximations that can be used, analyzed, or improved with more specialized methods. © 2018 Wiley Periodicals, Inc.

Single-pass incremental force updates for adaptively restrained molecular dynamics.

Adaptively restrained molecular dynamics (ARMD) allows users to perform more integration steps in wall-clock time by switching on and off positional degrees of freedoms. This article presents new, single-pass incremental force updates algorithms to efficiently simulate a system using ARMD. We assessed different algorithms for speedup measurements and implemented them in the LAMMPS MD package. We validated the single-pass incremental force update algorithm on four different benchmarks using diverse pair potentials. The proposed algorithm allows us to perform simulation of a system faster than traditional MD in both NVE and NVT ensembles. Moreover, ARMD using the new single-pass algorithm speeds up the convergence of observables in wall-clock time. © 2017 Wiley Periodicals, Inc.

IM-UFF: Extending the universal force field for interactive molecular modeling.

The universal force field (UFF) is a broadly applicable classical force field that contains parameters for almost every atom type of the periodic table. This force field is non-reactive, i.e. the topology of the system under study is considered as fixed and no creation or breaking of covalent bonds is possible. This paper introduces interactive modeling-UFF (IM-UFF), an extension of UFF that combines the possibility to significantly modify molecular structures (as with reactive force fields) with a broad diversity of supported systems thanks to the universality of UFF. Such an extension lets the user easily build and edit molecular systems interactively while being guided by physics based inter-atomic forces. This approach introduces weighted atom types and weighted bonds, used to update topologies and atom parameterizations at every time step of a simulation. IM-UFF has been evaluated on a large set of benchmarks and is proposed as a self-contained implementation integrated in a new module for the SAMSON software platform for computational nanoscience available at http://www.samson-connect.net.

As-Rigid-As-Possible molecular interpolation paths.

This paper proposes a new method to generate interpolation paths between two given molecular conformations. It relies on the As-Rigid-As-Possible (ARAP) paradigm used in Computer Graphics to manipulate complex meshes while preserving their essential structural characteristics. The adaptation of ARAP approaches to the case of molecular systems is presented in this contribution. Experiments conducted on a large set of benchmarks show how such a strategy can efficiently compute relevant interpolation paths with large conformational rearrangements.

Automatic molecular structure perception for the universal force field.

The Universal Force Field (UFF) is a classical force field applicable to almost all atom types of the periodic table. Such a flexibility makes this force field a potential good candidate for simulations involving a large spectrum of systems and, indeed, UFF has been applied to various families of molecules. Unfortunately, initializing UFF, that is, performing molecular structure perception to determine which parameters should be used to compute the UFF energy and forces, appears to be a difficult problem. Although many perception methods exist, they mostly focus on organic molecules, and are thus not well-adapted to the diversity of systems potentially considered with UFF. In this article, we propose an automatic perception method for initializing UFF that includes the identification of the system's connectivity, the assignment of bond orders as well as UFF atom types. This perception scheme is proposed as a self-contained UFF implementation integrated in a new module for the SAMSON software platform for computational nanoscience (http://www.samson-connect.net). We validate both the automatic perception method and the UFF implementation on a series of benchmarks.

Interactive chemical reactivity exploration.

Elucidating chemical reactivity in complex molecular assemblies of a few hundred atoms is, despite the remarkable progress in quantum chemistry, still a major challenge. Black-box search methods to find intermediates and transition-state structures might fail in such situations because of the high-dimensionality of the potential energy surface. Here, we propose the concept of interactive chemical reactivity exploration to effectively introduce the chemist's intuition into the search process. We employ a haptic pointer device with force feedback to allow the operator the direct manipulation of structures in three dimensions along with simultaneous perception of the quantum mechanical response upon structure modification as forces. We elaborate on the details of how such an interactive exploration should proceed and which technical difficulties need to be overcome. All reactivity-exploration concepts developed for this purpose have been implemented in the samson programming environment.

Block-adaptive quantum mechanics: an adaptive divide-and-conquer approach to interactive quantum chemistry.

We present a novel Block-Adaptive Quantum Mechanics (BAQM) approach to interactive quantum chemistry. Although quantum chemistry models are known to be computationally demanding, we achieve interactive rates by focusing computational resources on the most active parts of the system. BAQM is based on a divide-and-conquer technique and constrains some nucleus positions and some electronic degrees of freedom on the fly to simplify the simulation. As a result, each time step may be performed significantly faster, which in turn may accelerate attraction to the neighboring local minima. By applying our approach to the nonself-consistent Atom Superposition and Electron Delocalization Molecular Orbital theory, we demonstrate interactive rates and efficient virtual prototyping for systems containing more than a thousand of atoms on a standard desktop computer.

Adaptively restrained particle simulations.

Interaction potentials used in particle simulations are typically written as a sum of terms which depend on just a few relative particle positions. Traditional simulation methods move all particles at each time step, and may thus spend a lot of time updating interparticle forces. In this Letter we introduce adaptively restrained particle simulations (ARPS) to speed up particle simulations by adaptively switching on and off positional degrees of freedom, while letting momenta evolve. We illustrate ARPS on several numerical experiments, including (a) a collision cascade example that demonstrates how ARPS make it possible to smoothly trade between precision and speed and (b) a polymer-in-solvent study that shows how one may efficiently determine static equilibrium properties with ARPS.

Interactive quantum chemistry: a divide-and-conquer ASED-MO method.

We present interactive quantum chemistry simulation at the atom superposition and electron delocalization molecular orbital (ASED-MO) level of theory. Our method is based on the divide-and-conquer (D&C) approach, which we show is accurate and efficient for this non-self-consistent semiempirical theory. The method has a linear complexity in the number of atoms, scales well with the number of cores, and has a small prefactor. The time cost is completely controllable, as all steps are performed with direct algorithms, i.e., no iterative schemes are used. We discuss the errors induced by the D&C approach, first empirically on a few examples, and then via a theoretical study of two toy models that can be analytically solved for any number of atoms. Thanks to the precision and speed of the D&C approach, we are able to demonstrate interactive quantum chemistry simulations for systems up to a few hundred atoms on a current multicore desktop computer. When drawing and editing molecular systems, interactive simulations provide immediate, intuitive feedback on chemical structures. As the number of cores on personal computers increases, and larger and larger systems can be dealt with, we believe such interactive simulations-even at lower levels of theory-should thus prove most useful to effectively understand, design and prototype molecules, devices and materials.

A comparison of neighbor search algorithms for large rigid molecules.

Fast determination of neighboring atoms is an essential step in molecular dynamics simulations or Monte Carlo computations, and there exists a variety of algorithms to efficiently compute neighbor lists. However, most of these algorithms are general, and not specifically designed for a given type of application. As a result, although their average performance is satisfactory, they might be inappropriate in some specific application domains. In this article, we study the case of detecting neighbors between large rigid molecules, which has applications in, e.g., rigid body molecular docking, Monte Carlo simulations of molecular self-assembly or diffusion, and rigid body molecular dynamics simulations. More precisely, we compare the traditional grid-based algorithm to a series of hierarchy-based algorithms that use bounding volumes to rapidly eliminate large groups of irrelevant pairs of atoms during the neighbor search. We compare the performance of these algorithms based on several parameters: the size of the molecules, the average distance between them, the cutoff distance, as well as the type of bounding volume used in the culling hierarchy (AABB, OBB, wrapped, or layered spheres). We demonstrate that for relatively large systems (> 100,000 atoms) the algorithm based on the hierarchy of wrapped spheres shows the best results and the traditional grid-based algorithm gives the worst timings. For small systems, however, the grid-based algorithm and the one based on the wrapped sphere hierarchy are beneficial.

Fast construction of assembly trees for molecular graphs.

A number of modeling and simulation algorithms using internal coordinates rely on hierarchical representations of molecular systems. Given the potentially complex topologies of molecular systems, though, automatically generating such hierarchical decompositions may be difficult. In this article, we present a fast general algorithm for the complete construction of a hierarchical representation of a molecular system. This two-step algorithm treats the input molecular system as a graph in which vertices represent atoms or pseudo-atoms, and edges represent covalent bonds. The first step contracts all cycles in the input graph. The second step builds an assembly tree from the reduced graph. We analyze the complexity of this algorithm and show that the first step is linear in the number of edges in the input graph, whereas the second one is linear in the number of edges in the graph without cycles, but dependent on the branching factor of the molecular graph. We demonstrate the performance of our algorithm on a set of specifically tailored difficult cases as well as on a large subset of molecular graphs extracted from the protein data bank. In particular, we experimentally show that both steps behave linearly in the number of edges in the input graph (the branching factor is fixed for the second step). Finally, we demonstrate an application of our hierarchy construction algorithm to adaptive torsion-angle molecular mechanics.

Comparing position and force control for interactive molecular simulators with haptic feedback.

This paper presents a novel tool for the analysis of new molecular structures which enables a wide variety of manipulations. It is composed of a molecular simulator and a haptic device. The simulation software deals with systems of hundreds or thousands of degrees of freedom and computes the reconfiguration of the molecules in a few tenths of a second. For the ease of manipulation and to help the operator understand nanoscale phenomena, a haptic device is connected to the simulator. To handle a wide variety of applications, both position and force control are implemented. To our knowledge, this is the first time the applications of force control are detailed for molecular simulation. These two control modes are compared in terms of adequacy with molecular dynamics, transparency and stability sensitivity with respect to environmental conditions. Based on their specificity the operations they can realize are detailed. Experiments highlight the usability of our tool for the different steps of the analysis of molecular structures. It includes the global reconfiguration of a molecular system, the measurement of molecular properties and the comprehension of nanoscale interactions. Compared to most existing systems, the one developed in this paper offers a wide range of possible experiments. The detailed analysis of the properties of the control modes can be easily used to implement haptic feedback on other molecular simulators.

Practical modeling of molecular systems with symmetries.

A new method for efficient modeling of macromolecular systems with symmetries is presented. The method is based on a hierarchical representation of the molecular system and a novel fast binary tree-based neighbor list construction algorithm. The method supports all types of molecular symmetry, including crystallographic symmetry. Testing the proposed neighbor list construction algorithm on a number of different macromolecular systems containing up to about 200,000 of atoms shows that (1) the current binary tree-based neighbor list construction algorithm scales linearly in the number of atoms for the central subunit, and sublinearly for its replicas, (2) the overall computational overhead of the method for a system with symmetry with respect to the same system without symmetry scales linearly with the cutoff value and does not exceed 50% for all but one tested macromolecules at the cutoff distance of 12 A. (3) the method may help produce optimized molecular structures that are much closer to experimentally determined structures when compared with the optimization without symmetry, (4) the method can be applied to models of macromolecules with still unknown detailed structure.

Adaptive torsion-angle quasi-statics: a general simulation method with applications to protein structure analysis and design.

MOTIVATION: The cost of molecular quasi-statics or dynamics simulations increases with the size of the simulated systems, which is a problem when studying biological phenomena that involve large molecules over long time scales. To address this problem, one has often to either increase the processing power (which might be expensive), or make arbitrary simplifications to the system (which might bias the study). RESULTS: We introduce adaptive torsion-angle quasi-statics, a general simulation method able to rigorously and automatically predict the most mobile regions in a simulated system, under user-defined precision or time constraints. By predicting and simulating only these most important regions, the adaptive method provides the user with complete control on the balance between precision and computational cost, without requiring him or her to perform a priori, arbitrary simplifications. We build on our previous research on adaptive articulated-body simulation and show how, by taking advantage of the partial rigidification of a molecule, we are able to propose novel data structures and algorithms for adaptive update of molecular forces and energies. This results in a globally adaptive molecular quasi-statics simulation method. We demonstrate our approach on several examples and show how adaptive quasi-statics allows a user to interactively design, modify and study potentially complex protein structures.

A six degree-of-freedom god-object method for haptic display of rigid bodies with surface properties.

This paper describes a generalization of the god-object method for haptic interaction between rigid bodies. Our approach separates the computation of the motion of the six degree-of-freedom god-object from the computation of the force applied to the user. The motion of the god-object is computed using continuous collision detection and constraint-based quasi-statics, which enables high-quality haptic interaction between contacting rigid bodies. The force applied to the user is computed using a novel constraint-based quasi-static approach, which allows us to suppress force artifacts typically found in previous methods. The constraint-based force applied to the user, which handles any number of simultaneous contact points, is computed within a few microseconds, while the update of the configuration of the rigid god-object is performed within a few milliseconds for rigid bodies containing up to tens of thousands of triangles. Our approach has been successfully tested on complex benchmarks. Our results show that the separation into asynchronous processes allows us to satisfy the different update rates required by the haptic and visual displays. Force shading and textures can be added and enlarge the range of haptic perception of a virtual environment. This paper is an extension of [1].