An exact algorithm to find a maximum weight clique in a weighted undirected graph.

We introduce a new algorithm MaxCliqueWeight for identifying a maximum weight clique in a weighted graph, and its variant MaxCliqueDynWeight with dynamically varying bounds. This algorithm uses an efficient branch-and-bound approach with a new weighted graph coloring algorithm that efficiently determines upper weight bounds for a maximum weighted clique in a graph. We evaluate our algorithm on random weighted graphs with node counts up to 10,000 and on standard DIMACS benchmark graphs used in a variety of research areas. Our findings reveal a remarkable improvement in computational speed when compared to existing algorithms, particularly evident in the case of high-density random graphs and DIMACS graphs, where our newly developed algorithm outperforms existing alternatives by several orders of magnitude. The newly developed algorithm and its variant are freely available to the broader research community at http://insilab.org/maxcliqueweight , paving the way for transformative applications in various research areas, including drug discovery.

PyRETIS 3: Conquering rare and slow events without boundaries.

We present and discuss the advancements made in PyRETIS 3, the third instalment of our Python library for an efficient and user-friendly rare event simulation, focused to execute molecular simulations with replica exchange transition interface sampling (RETIS) and its variations. Apart from a general rewiring of the internal code towards a more modular structure, several recently developed sampling strategies have been implemented. These include recently developed Monte Carlo moves to increase path decorrelation and convergence rate, and new ensemble definitions to handle the challenges of long-lived metastable states and transitions with unbounded reactant and product states. Additionally, the post-analysis software PyVisa is now embedded in the main code, allowing fast use of machine-learning algorithms for clustering and visualising collective variables in the simulation data.

Conformational dynamics of α-1 acid glycoprotein (AGP) in cancer: A comparative study of glycosylated and unglycosylated AGP.

α-1 acid glycoprotein (AGP) is one of the most abundant plasma proteins. It fulfills two important functions: immunomodulation, and binding to various drugs and receptors. These different functions are closely associated and modulated via changes in glycosylation and cancer missense mutations. From a structural point of view, glycans alter the local biophysical properties of the protein leading to a diverse ligand-binding spectrum. However, glycans can typically not be observed in the resolved X-ray crystallography structure of AGP due to their high flexibility and microheterogeneity, so limiting our understanding of AGP's conformational dynamics 70 years after its discovery. We here investigate how mutations and glycosylation interfere with AGP's conformational dynamics changing its biophysical behavior, by using molecular dynamics (MD) simulations and sequence-based dynamics predictions. The MD trajectories show that glycosylation decreases the local backbone flexibility of AGP and increases the flexibility of distant regions through allosteric effects. We observe that mutations near the glycosylation site affect glycan's conformational preferences. Thus, we conclude that mutations control glycan dynamics which modulates the protein's backbone flexibility directly affecting its accessibility. These findings may assist in the drug design targeting AGP's glycosylation and mutations in cancer.

Capric Acid and Myristic Acid Permeability Enhancers in Curved Liposome Membranes.

Liposomes are considered as advanced drug delivery systems for cancer treatment. A generation of pH-sensitive liposomes is being developed that use fatty acids (FAs) as a trigger for drug release in tumor tissues. However, FAs are also known to enhance permeability, and it is unclear whether FAs in liposomes may cause drug leakage or premature drug release. The passive permeability of the drug through the membrane of the liposome is thus a crucial factor for timely drug delivery. To investigate how the curvature and lipid composition of liposomes affect their passive permeability, coarse-grained molecular dynamics were performed. The permeability was determined with a counting method. Flat bilayers and three liposomes with varying diameters were studied, which had varying lipid compositions of dipalmitoylphosphatidylcholine, cholesterol, and deprotonated or neutral saturated FAs. The investigated permeants were water and two other small permeants, which have different free energy profiles (solubility) across the membrane. First, for the curvature effect, our results showed that curvature increases the water permeability by reducing the membrane thickness. The permeability increase for water is about a factor of 1.7 for the most curved membranes. However, a high curvature decreases permeability for permeants with free energy profiles that are a mix of wells and barriers in the headgroup region of the membrane. Importantly, the type of experimental setup is expected to play a dominant role in the permeability value, i.e., whether permeants are escaping or entering the liposomes. Second, for the composition effect, FAs decrease both the area per lipid (APL) and the membrane thickness, resulting in permeability increases of up to 55%. Cholesterol has a similar effect on the APL but has the opposite impact on membrane thickness and permeability. Therefore, FAs and cholesterol have opposing effects on permeability, with cholesterol's effect being slightly stronger in our simulated bilayers. As all permeability values were well within a factor of 2, and with liposomes usually being larger and less curved in experimental applications, it can be concluded that the passive drug release from a pH-sensitive liposome does not seem to be significantly affected by the presence of FAs.

Understanding the Role of Caveolae in Oxygen Buffering: The Effect of Membrane Curvature.

The "oxygen paradox" can be explained as two opposing biological processes with oxygen (O2) as a reactant. On the one hand, oxygen is essential to aerobic metabolism, powering oxidative phosphorylation in mitochondria. On the other hand, an excess supply of oxygen will generate reactive species which are harmful for the cell. In healthy tissues, the first process must be maximized relative to the second one. We have hypothesized that curved and cholesterol-enriched membrane invaginations called caveolae help maintain the proper oxygen level by taking up oxygen and attenuating its release to the mitochondria. The mechanism by which caveolae may help to buffer the oxygen level in cells is still unclear. Here, we aim to assess how structural aspects of caveolae, the curvature of the membrane, influence the local oxygen abundance and the membrane partitioning. We have modelled a flat bilayer and a liposome composed of dipalmitoylphosphatidylcholine (DPPC), using molecular dynamics simulation. Associated changes in the membrane-level oxygen partition coefficient and free energy profiles will be presented.

Path sampling with memory reduction and replica exchange to reach long permeation timescales.

Assessing kinetics in biological processes with molecular dynamics simulations remains a computational and conceptual challenge, given the large time and length scales involved. For kinetic transport of biochemical compounds or drug molecules, the permeability through the phospholipid membranes is a key kinetic property, but long timescales are hindering the accurate computation. Technological advances in high-performance computing therefore need to be accompanied by theoretical and methodological developments. In this contribution, the replica exchange transition interface sampling (RETIS) methodology is shown to give perspective toward observing longer permeation pathways. It is first reviewed how RETIS, a path-sampling methodology that gives in principle exact kinetics, can be used to compute membrane permeability. Next, recent and current developments in three RETIS aspects are discussed: several new Monte Carlo moves in the path-sampling algorithm, memory reduction by reducing pathlengths, and exploitation of parallel computing with CPU-imbalanced replicas. Finally, the memory reduction presenting a new replica exchange implementation, coined REPPTIS, is showcased with a permeant needing to pass a membrane with two permeation channels, either representing an entropic or energetic barrier. The REPPTIS results showed clearly that inclusion of some memory and enhancing ergodic sampling via replica exchange moves are both necessary to obtain correct permeability estimates. In an additional example, ibuprofen permeation through a dipalmitoylphosphatidylcholine membrane was modeled. REPPTIS succeeded in estimating the permeability of this amphiphilic drug molecule with metastable states along the permeation pathway. In conclusion, the presented methodological advances allow for deeper insight into membrane biophysics even if the pathways are slow, as RETIS and REPPTIS push the permeability calculations to longer timescales.

Defining permeability of curved membranes in molecular dynamics simulations.

Many phospholipid membranes in the cell have a high curvature; for instance, in caveolae, mitochondrial crystae, nanotubes, membrane pearls, small liposomes, or exosomes. Molecular dynamics (MD) simulations are a computational tool to gain insight in the transport behavior at the atomic scale. Membrane permeability is a key kinetic property that might be affected in these highly curved membranes. Unfortunately, the geometry of highly curved membranes creates ambiguity in the permeability value, even with an arbitrarily large factor purely based on geometry, caused by the radial flux not being a constant value in steady state. In this contribution, the ambiguity in permeability for liposomes is countered by providing a new permeability definition. First, the inhomogeneous solubility diffusion model based on the Smoluchowski equation is solved analytically under radial symmetry, from which the entrance and escape permeabilities are defined. Next, the liposome permeability is defined guided by the criterion that a flat and curved membrane should have equal permeability, in case these were to be carved out from an imaginary homogeneous medium. With this criterion, our new definition allows for a fair comparison of flat and curved membranes. The definition is then transferred to the counting method, which is a practical computational approach to derive permeability by counting complete membrane crossings. Finally, the usability of the approach is illustrated with MD simulations of diphosphatidylcholine (DPPC) bilayers, without or with some cholesterol content. Our new liposome permeability definition allows us to compare a spherically shaped membrane with its flat counterpart, thus showcasing how the curvature effect on membrane transport may be assessed.

Oxygen Storage in Stacked Phospholipid Membranes Under an Oxygen Gradient as a Model for Myelin Sheaths.

Axons in the brain and peripheral nervous system are enveloped by myelin sheaths, which are composed of stacked membrane bilayers containing large fractions of cholesterol, phospholipids, and glycolipids. The oxygen availability to the nearby oxygen consuming cytochrome c oxidase in the mitochondria is essential for the well-functioning of a cell. By constructing a rate network model based on molecular dynamics simulations, and solving it for steady-state conditions, this work calculates the oxygen storage in stacked membranes under an oxygen gradient. It is found that stacking membranes increases the oxygen storage capacity, indicating that myelin can function as an oxygen reservoir. However, it is found that the storage enhancement levels out for stacks with a large number of bilayers, suggesting why myelin sheaths consist of only 10-300 membranes rather than thousands. The presence of additional water between the stacked bilayers, as seen in cancer cells, is shown to diminish myelin oxygen storage enhancement.

Sampling efficiency of the counting method for permeability calculations estimated with the inhomogeneous solubility-diffusion model.

Permeability is a key property in various fields such as membrane technology for chemical separation and transport of substances through cell membranes. At the molecular scale, the counting method uses the number of membrane crossings in a conventional unbiased molecular dynamics simulation to predict the permeability. This contribution investigates under which conditions the counting method has insufficient statistics. An equation is derived for a compartmental model based on the inhomogeneous solubility-diffusion (Smoluchowski) model, giving insight into how the flux correlates with the solubility of permeants. This equation shows that a membrane crossing is a rare event not only when the membrane forms a large free energy barrier but also when the membrane forms a deep free energy well that traps permeants. Such a permeant trap has a high permeability; yet, the counting method suffers from poor statistics. To illustrate this, coarse-grained MD was run for 16 systems of dipalmitoylphosphatidylcholine bilayer membranes with different permeant types. The composition rule for permeability is shown to also hold for fluxes, and it is highlighted that the considered thickness of the membrane causes uncertainty in the permeability calculation of highly permeable membranes. In conclusion, a high permeability in itself is not an effective indicator of the sampling efficiency of the counting method, and caution should be taken for permeants whose solubility varies greatly over the simulation box. A practical consequence relevant in, e.g., drug design is that a drug with high membrane permeability might get trapped by membranes thus reducing its efficacy.

Permeation Rates of Oxygen through a Lipid Bilayer Using Replica Exchange Transition Interface Sampling.

Several simulations strategies have emerged to predict the permeability of solutes across membranes, which is important for many biological or industrial processes such as drug design. The widespread inhomogeneous solubility-diffusion (ISD) model is based on the Smoluchowski equation and describes permeation as purely diffusive. The counting method, which counts membrane transitions in a long molecular dynamics (MD) trajectory, is free of this diffusive assumption, but it lacks sufficient statistics when the permeation involves high free energy barriers. Metadynamics and variations thereof can overcome such barriers, but they generally lack the kinetics information. The milestoning framework has been used to describe permeation as a rare event, but it still relies on the Markovian assumption between the milestones. Replica Exchange Transition Interface Sampling (RETIS) has been shown to be an effective method for sampling rare events while simultaneously describing the kinetics without assumptions. This paper is the first permeation application of RETIS on an all-atom lipid bilayer consisting of 1-palmitoyl-2-oleoyl-sn-glycero-3-phosphocholine (POPC) to compute the entrance, escape and complete transition of molecular oxygen. Conventional MD was performed as a benchmark, and the MD rates from counting were converted to rate constants, giving good agreement with the RETIS values. Moreover, a correction factor was derived to convert the collective order parameter in RETIS, which was aimed to improve efficiency, to a single-particle order parameter. With this work, we showed how the exact kinetics of drug molecules permeation can be assessed with RETIS even if the permeation is truly a rare event or if the permeation is non-Markovian. RETIS will therefore be a valuable tool for future permeation studies.

Membrane permeability of small molecules from unbiased molecular dynamics simulations.

Permeation of many small molecules through lipid bilayers can be directly observed in molecular dynamics simulations on the nano- and microsecond timescale. While unbiased simulations provide an unobstructed view of the permeation process, their feasibility for computing permeability coefficients depends on various factors that differ for each permeant. The present work studies three small molecules for which unbiased simulations of permeation are feasible within less than a microsecond, one hydrophobic (oxygen), one hydrophilic (water), and one amphiphilic (ethanol). Permeabilities are computed using two approaches: counting methods and a maximum-likelihood estimation for the inhomogeneous solubility diffusion (ISD) model. Counting methods yield nearly model-free estimates of the permeability for all three permeants. While the ISD-based approach is reasonable for oxygen, it lacks precision for water due to insufficient sampling and results in misleading estimates for ethanol due to invalid model assumptions. It is also demonstrated that simulations using a Langevin thermostat with collision frequencies of 1/ps and 5/ps yield oxygen permeabilities and diffusion constants that are lower than those using Nosé-Hoover by statistically significant margins. In contrast, permeabilities from trajectories generated with Nosé-Hoover and the microcanonical ensemble do not show statistically significant differences. As molecular simulations become more affordable and accurate, calculation of permeability for an expanding range of molecules will be feasible using unbiased simulations. The present work summarizes theoretical underpinnings, identifies pitfalls, and develops best practices for such simulations.

Permeability of membranes in the liquid ordered and liquid disordered phases.

The functional significance of ordered nanodomains (or rafts) in cholesterol rich eukaryotic cell membranes has only begun to be explored. This study exploits the correspondence of cellular rafts and liquid ordered (Lo) phases of three-component lipid bilayers to examine permeability. Molecular dynamics simulations of Lo phase dipalmitoylphosphatidylcholine (DPPC), dioleoylphosphatidylcholine (DOPC), and cholesterol show that oxygen and water transit a leaflet through the DOPC and cholesterol rich boundaries of hexagonally packed DPPC microdomains, freely diffuse along the bilayer midplane, and escape the membrane along the boundary regions. Electron paramagnetic resonance experiments provide critical validation: the measured ratio of oxygen concentrations near the midplanes of liquid disordered (Ld) and Lo bilayers of DPPC/DOPC/cholesterol is 1.75 ± 0.35, in very good agreement with 1.3 ± 0.3 obtained from simulation. The results show how cellular rafts can be structurally rigid signaling platforms while remaining nearly as permeable to small molecules as the Ld phase.

Effect of Chain Unsaturation and Temperature on Oxygen Diffusion Through Lipid Membranes from Simulations.

Rafts are nanoscale ordered domains in biological membranes that are rich in saturated phospholipids. In this study, the influence of chain unsaturation and temperature on oxygen diffusion through lipid membranes is examined using advanced computational modeling. The studied phospholipids with increasing unsaturation are: 1,2-dipalmitoyl-sn-glycero-3-phosphocholine (DPPC), 1-palmitoyl-2-oleoyl-sn-glycero-3-phosphocholine (POPC), and 1,2-dioleoyl-sn-glycero-3-phosphocholine (DOPC). The unsaturation correlates with the area per lipid and the order parameter. Oxygen diffusion is found to be faster at higher temperature, and the solubility of oxygen in the membrane with respect to water decreases. Diffusion varies over a larger range across the membrane at 323 K in DPPC than in DOPC, whereas POPC has intermediate diffusivity. Oxygen diffusion in saturated lipids is faster at the membrane center and slower near the head group region than in unsaturated lipids. Oxygen solubility in DPPC is higher than in unsaturated lipids.

Membrane Permeability: Characteristic Times and Lengths for Oxygen and a Simulation-Based Test of the Inhomogeneous Solubility-Diffusion Model.

The balance of normal and radial (lateral) diffusion of oxygen in phospholipid membranes is critical for biological function. Based on the Smoluchowski equation for the inhomogeneous solubility-diffusion model, Bayesian analysis (BA) can be applied to molecular dynamics trajectories of oxygen to extract the free energy and the normal and radial diffusion profiles. This paper derives a theoretical formalism to convert these profiles into characteristic times and lengths associated with entering, escaping, or completely crossing the membrane. The formalism computes mean first passage times and holds for any process described by rate equations between discrete states. BA of simulations of eight model membranes with varying lipid composition and temperature indicate that oxygen travels 3 to 5 times further in the radial than in the normal direction when crossing the membrane in a time of 15 to 32 ns, thereby confirming the anisotropy of passive oxygen transport in membranes. Moreover, the preceding times and distances estimated from the BA are compared to the aggregate of 280 membrane exits explicitly observed in the trajectories. BA predictions for the distances of oxygen radial diffusion within the membrane are statistically indistinguishable from the corresponding simulation values, yet BA oxygen exit times from the membrane interior are approximately 20% shorter than the simulation values, averaged over seven systems. The comparison supports the BA approach and, therefore, the applicability of the Smoluchowski equation to membrane diffusion. Given the shorter trajectories required for the BA, these results validate the BA as a computationally attractive alternative to direct observation of exits when estimating characteristic times and radial distances. The effect of collective membrane undulations on the BA is also discussed.

The Importance of Cell Shape Sampling To Accurately Predict Flexibility in Metal-Organic Frameworks.

In this work, the influence of cell shape sampling on the predicted stability of the different metastable phases in flexible metal-organic frameworks at finite temperatures is investigated. The influence on the free energy by neglecting cell shape sampling is quantified for the prototypical MIL-53(Al) and the topical DUT-49(Cu). This goal is achieved by constructing free energy profiles in ensembles either in which the phase space associated with the cell shape is sampled explicitly or in which the cell shape is kept fixed. When neglecting cell shape sampling, thermodynamic integration of the hydrostatic pressure yields unreliable free energy profiles that depend on the choice of the fixed cell shape. In this work, we extend the thermodynamic integration procedure via the introduction of a generalized pressure, derived from the Lagrangian strain tensor and the second Piola-Kirchhoff tensor. Using this generalized procedure, the dependence on the unit cell shape can be eliminated, and the inaccuracy in free energy stemming from the lack of cell shape sampling can be uniquely quantified. Finally, it is shown that the inaccuracy in free energy when fixing the cell shape at room temperature stems mainly from entropic contributions for both MIL-53(Al) and DUT-49(Cu).

Position-Dependent Diffusion Tensors in Anisotropic Media from Simulation: Oxygen Transport in and through Membranes.

A Bayesian-based methodology is developed to estimate diffusion tensors from molecular dynamics simulations of permeants in anisotropic media, and is applied to oxygen in lipid bilayers. By a separation of variables in the Smoluchowski diffusion equation, the multidimensional diffusion is reduced to coupled one-dimensional diffusion problems that are treated by discretization. The resulting diffusivity profiles characterize the membrane transport dynamics as a function of the position across the membrane, discriminating between diffusion normal and parallel to the membrane. The methodology is first validated with neat water, neat hexadecane, and a hexadecane slab surrounded by water, the latter being a simple model for a lipid membrane. Next, a bilayer consisting of pure 1-palmitoyl 2-oleoylphosphatidylcholine (POPC), and a bilayer mimicking the lipid composition of the inner mitochondrial membrane, including cardiolipin, are investigated. We analyze the detailed time evolution of oxygen molecules, in terms of both normal diffusion through and radial diffusion inside the membrane. Diffusion is fast in the more loosely packed interleaflet region, and anisotropic, with oxygen spreading more rapidly in the membrane plane than normal to it. Visualization of the propagator shows that oxygen enters the membrane rapidly, reaching its thermodynamically favored center in about 1 ns, despite the free energy barrier at the headgroup region. Oxygen transport is quantified by computing the oxygen permeability of the membranes and the average radial diffusivity, which confirm the anisotropy of the diffusion. The position-dependent diffusion constants and free energies are used to construct compartmental models and test assumptions used in estimating permeability, including Overton's rule. In particular, a hexadecane slab surrounded by water is found to be a poor model of oxygen transport in membranes because the relevant energy barriers differ substantially.

Discovery of Mycobacterium tuberculosis InhA Inhibitors by Binding Sites Comparison and Ligands Prediction.

Drug discovery is usually focused on a single protein target; in this process, existing compounds that bind to related proteins are often ignored. We describe ProBiS plugin, extension of our earlier ProBiS-ligands approach, which for a given protein structure allows prediction of its binding sites and, for each binding site, the ligands from similar binding sites in the Protein Data Bank. We developed a new database of precalculated binding site comparisons of about 290000 proteins to allow fast prediction of binding sites in existing proteins. The plugin enables advanced viewing of predicted binding sites, ligands' poses, and their interactions in three-dimensional graphics. Using the InhA query protein, an enoyl reductase enzyme in the Mycobacterium tuberculosis fatty acid biosynthesis pathway, we predicted its possible ligands and assessed their inhibitory activity experimentally. This resulted in three previously unrecognized inhibitors with novel scaffolds, demonstrating the plugin's utility in the early drug discovery process.

Complex Reaction Environments and Competing Reaction Mechanisms in Zeolite Catalysis: Insights from Advanced Molecular Dynamics.

The methanol-to-olefin process is a showcase example of complex zeolite-catalyzed chemistry. At real operating conditions, many factors affect the reactivity, such as framework flexibility, adsorption of various guest molecules, and competitive reaction pathways. In this study, the strength of first principle molecular dynamics techniques to capture this complexity is shown by means of two case studies. Firstly, the adsorption behavior of methanol and water in H-SAPO-34 at 350 °C is investigated. Hereby an important degree of framework flexibility and proton mobility was observed. Secondly, the methylation of benzene by methanol through a competitive direct and stepwise pathway in the AFI topology was studied. Both case studies clearly show that a first-principle molecular dynamics approach enables unprecedented insights into zeolite-catalyzed reactions at the nanometer scale to be obtained.

Exploring the vibrational fingerprint of the electronic excitation energy via molecular dynamics.

A Fourier-based method is presented to relate changes of the molecular structure during a molecular dynamics simulation with fluctuations in the electronic excitation energy. The method implies sampling of the ground state potential energy surface. Subsequently, the power spectrum of the velocities is compared with the power spectrum of the excitation energy computed using time-dependent density functional theory. Peaks in both spectra are compared, and motions exhibiting a linear or quadratic behavior can be distinguished. The quadratically active motions are mainly responsible for the changes in the excitation energy and hence cause shifts between the dynamic and static values of the spectral property. Moreover, information about the potential energy surface of various excited states can be obtained. The procedure is illustrated with three case studies. The first electronic excitation is explored in detail and dominant vibrational motions responsible for changes in the excitation energy are identified for ethylene, biphenyl, and hexamethylbenzene. The proposed method is also extended to other low-energy excitations. Finally, the vibrational fingerprint of the excitation energy of a more complex molecule, in particular the azo dye ethyl orange in a water environment, is analyzed.