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.     

Encoding of polycyclic Si-containing molecules for determining species uniqueness in automated mechanism generation

Automated mechanism generation is an attractive way to understand the fundamental kinetics of complex reaction systems such as silicon hydride clustering chemistry. It relies on being able to tell molecules apart as they are generated. The graph theoretic foundation allows molecules to be identified using unique notations created from their connectivity. To apply this technique to silicon hydride clustering chemistry, a molecule canonicalization and encoding algorithm was developed to handle complex polycyclic, nonplanar species. The algorithm combines the concepts of extended connectivity and the idea of breaking ties to encode highly symmetric molecules. The connected components in the molecules are encoded separately and reassembled using a depth-first search method to obtain the correct string codes. A revised cycle-finding algorithm was also developed to properly select the cycles used for ring corrections when thermodynamic properties were calculated using group additivity. In this algorithm, the molecules are expressed explicitly as trees, and all linearly independent cycles of every size in the molecule are found. The cycles are then sorted according to their size and functionality, and the cycles with higher priorities will be used to include ring corrections. Applying this algorithm, more appropriate cycle selection and more accurate estimation of thermochemical properties of the molecules can be obtained.     

Parallel implementation of a direct method for calculating electrostatic potentials

The authors present a method for calculating the electrostatic potential directly in a straightforward manner. While traditional methods for calculating the electrostatic potential usually involve solving the Poisson equation iteratively, the authors obtain the electrostatic interaction potential by performing direct numerical integration of the Coulomb-law expression using finite-element functions defined on a grid. The singularity of the Coulomb operator is circumvented by an integral transformation and the resulting auxiliary integral is obtained using Gaussian quadrature. The three-dimensional finite-element basis is constructed as a tensor (outer) product of one-dimensional functions, yielding a partial factorization of the expressions. The resulting algorithm has, without using any prescreening or other computational tricks, a formal computational scaling of Omicron(N4/3), where N is the size of the grid. The authors show here how to implement the method for efficiently running on parallel computers. The matrix multiplications of the innermost loops are completely independent, yielding a parallel algorithm with the computational costs scaling practically linearly with the number of processors.     

Parallelizing of macro-scale pseudo-particle modeling for particle-fluid systems

Particle methods such as SPH (smoothed particlehydrodynamics)[1,2], DEM (distinct-element model)[3],DPD (dissipative particle dynamics)[4— and pseudo- 6]particle modeling (PPM)[7,8] are getting more and morepopular as numerical methods in material science andfluid dynamics, due to their flexibility in simulatingcomplicated phenomena like fluid-solid coupling,multi-phase flow and large deformation and rupture insolid materials. However, a comm…     

Cluster algorithm to perform parallel Monte Carlo simulation of atomistic systems

We propose an efficient algorithm to perform Monte Carlo simulations of dense systems using multiple particle moves. The method is intended to be used in the atomistic simulation of complex systems, where the computing requirements for a single simulation run make advisable the use of parallel computing. The algorithm is based on the use of steps in which all the particle positions of the system are perturbed simultaneously. A division of the system in clusters of particles is performed, using a bonding criterion which makes feasible that the acceptance or rejection of the new particle coordinates can be carried out independently for each cluster.     

Identification of family-specific residue packing motifs and their use for structure-based protein function prediction: II. Case studies and applications

Protein function prediction is one of the central problems in computational biology. We present a novel automated protein structure-based function prediction method using libraries of local residue packing patterns that are common to most proteins in a known functional family. Critical to this approach is the representation of a protein structure as a graph where residue vertices (residue name used as a vertex label) are connected by geometrical proximity edges. The approach employs two steps. First, it uses a fast subgraph mining algorithm to find all occurrences of family-specific labeled subgraphs for all well characterized protein structural and functional families. Second, it queries a new structure for occurrences of a set of motifs characteristic of a known family, using a graph index to speed up Ullman’s subgraph isomorphism algorithm. The confidence of function inference from structure depends on the number of family-specific motifs found in the query structure compared with their distribution in a large non-redundant database of proteins. This method can assign a new structure to a specific functional family in cases where sequence alignments, sequence patterns, structural superposition and active site templates fail to provide accurate annotation.     

Identification of family-specific residue packing motifs and their use for structure-based protein function prediction: I. Method development

Protein function prediction is one of the central problems in computational biology. We present a novel automated protein structure-based function prediction method using libraries of local residue packing patterns that are common to most proteins in a known functional family. Critical to this approach is the representation of a protein structure as a graph where residue vertices (residue name used as a vertex label) are connected by geometrical proximity edges. The approach employs two steps. First, it uses a fast subgraph mining algorithm to find all occurrences of family-specific labeled subgraphs for all well characterized protein structural and functional families. Second, it queries a new structure for occurrences of a set of motifs characteristic of a known family, using a graph index to speed up Ullman’s subgraph isomorphism algorithm. The confidence of function inference from structure depends on the number of family-specific motifs found in the query structure compared with their distribution in a large non-redundant database of proteins. This method can assign a new structure to a specific functional family in cases where sequence alignments, sequence patterns, structural superposition and active site templates fail to provide accurate annotation.     

Li + HCl RIOSA cross section calculations on parallel computers

Summary Reactive Infinite Order Sudden Approximation calculations have been performed using a computational procedure restructured to run on parallel computers. Computationally intensive sections of the code are analyzed and speedups obtained from a parallel restructuring discussed. The significant speedup obtained on a shared-memory parallel machine has allowed us to perform extensive calculations of the energy dependence of the integral and differential reactive cross sections of the Li+HCl system. A comparison with results of a quasiclassical and an experimental study is also performed.     

Computer program for finding all possible cycles in graphs

A new approach is presented for identifying all possible cycles in graphs. Input data are the total numbers of vertices and edges, as well as the vertex adjacencies using arbitrary vertex numbering. A homeomorphically reduced graph (HRG) is constructed by ignoring vertices of degree less than three. The algorithm is based on successive generation of possible edge-combinations in the HRG. If a combination yields a cycle, it is either printed or stored and then finally printed in a list of all possible cycles arranged in the order of increasing ring size. A unique numbering of the cycle is used. The computer program is listed and exemplified. Computing times are given.     

Computational algorithms for matching polynomials of graphs from the characteristic polynomials of edge-weighted graphs

Computational algorithms are described which provide for constructing the set of associated edge-weighted directed graphs such that the average of the characteristic polynomials of the edge-weighted graphs gives the matching polynomial of the parent graph. The weights were chosen to be unities or purely imaginary numbers so that the adjacency matrix is hermitian. The computer code developed earlier by one of the authors (K.B.) is generalized for complex hermitian matrices. Applications to bridged and spirographs, some lattices and all polycyclic graphs containing up to four cycles are considered.     

Heuristic Topological Decomposition Algorithm for Optimal Energy-Resource-Efficient Routing of Complex Process Pipeline Systems

A heuristic topological decomposition algorithm for optimal energy-resource-efficient routing of complex process pipeline systems was developed. The algorithm is distinguished by using an automated procedure for constructing a topological model of a hydraulic circuit as a hydraulic structural graph, a modified algorithm for finding the shortest spanning tree of the initial structural graph, and a set of heuristic rules. The developed algorithm enables one to determine the optimal energy-resource-efficient route with minimum reduced cost.     

Algorithm for topological correction of lists of simplexes of different dimensions for polyhedration of multicomponent systems

A new algorithm for polyhedration of quaternary and quaternary reciprocal systems is presented. The algorithm is based on checking all the links between vertices of a graph describing the composition diagram and selecting the polyhedration variants that correspond to the relations between the numbers of geometric elements of the complex undergoing polyhedration (graph vertices, links between them, and two-and three-dimensional complexes). Unlike Kraeva’s algorithm based on the decomposition of the graph in terms of zero elements of the adjacency matrix (absent links between vertices), the new algorithm can control the entire polyhedration process, accelerates the search for internal diagonals in the polyhedron, and takes into account their possible competition.     

TopoMS: Comprehensive topological exploration for molecular and condensed‐matter systems

We introduce Topo MS, a computational tool enabling detailed topological analysis of molecular and condensed‐matter systems, including the computation of atomic volumes and charges through the quantum theory of atoms in molecules, as well as the complete molecular graph. With roots in techniques from computational topology, and using a shared‐memory parallel approach, Topo MS provides scalable, numerically robust, and topologically consistent analysis. Topo MS can be used as a command‐line tool or with a GUI (graphical user interface), where the latter also enables an interactive exploration of the molecular graph. This paper presents algorithmic details of Topo MS and compares it with state‐of‐the‐art tools: Bader charge analysis v1.0 (Arnaldsson et al., 01/11/17) and molecular graph extraction using Critic2 (Otero‐de‐la‐Roza et al., Comput. Phys. Commun. 2014, 185, 1007). Topo MS not only combines the functionality of these individual codes but also demonstrates up to 4× performance gain on a standard laptop, faster convergence to fine‐grid solution, robustness against lattice bias, and topological consistency. Topo MS is released publicly under BSD License. © 2018 Wiley Periodicals, Inc.     

High-performance transformation of protein structure representation from internal to Cartesian coordinates

We present a highly parallel algorithm to convert internal coordinates of a polymeric molecule into Cartesian coordinates. Traditionally, converting the structures of polymers (e.g., proteins) from internal to Cartesian coordinates has been performed serially, due to an inherent linear dependency along the polymer chain. We show this dependency can be removed using a tree-based concatenation of coordinate transforms between segments, and then parallelized efficiently on graphics processing units (GPUs). The conversion algorithm is applicable to protein engineering and fitting protein structures to experimental data, and we observe an order of magnitude speedup using parallel processing on a GPU compared to serial execution on a CPU.     

Shape memory alloy-based smart module structure working under intense thermo-mechanical stress

The paper presents a complete model for a modular mechatronic structure actuated by a one-way memory effect shape memory alloy actuator. In order to claim the complete attribute of the model, the austenite transformation temperature evolution of actuator was evaluated in relation with the precision and repeatability related capabilities of the mechatronic structure. The evolution of austenite transformation temperature was obtained through determinations based on DSC method. Those determinations were performed on the shape memory alloy wire used as actuator in the modular mechatronic structure. The wire is subject of intense and repetitive operating mode. All determinations are performed on the SMA wire used as actuator system after 5,000, and 1,003,600 cycles, respectively. The results indicate a shift in both A _s and A _f temperatures, a trend that is heavily dependent on the operating history of the system. Using experimental results, authors built a graph (surface) that is based on heating time schedule, heating current, and austenite finish temperature. Also, the results lead to the conclusion that for any desired heating time, it can be identified (in a restricted but relatively wide range), at least a pair of both austenite finish temperature and heating current. If the control algorithm modifies the electrical current in accordance with the number of working cycles and austenite transformation temperature evolution, the time response and, by default, the structure repeatability are assured even after over 1 million working cycles.     

Representation, searching and discovery of patterns of bases in complex RNA structures

We describe a graph theoretic method designed to perform efficient searches for substructural patterns in nucleic acid structural coordinate databases using a simplified vectorial representation. Two vectors represent each nucleic acid base and the relative positions of bases with respect to one another are described in terms of distances between the defined start and end points of the vectors on each base. These points comprise the nodes and the distances the edges of a graph, and a pattern search can then be performed using a subgraph isomorphism algorithm. The minimal representation was designed to facilitate searches for complex patterns but was first tested on simple, well-characterised arrangements of bases such as base pairs and GNRA-tetraloop receptor interactions. The method performed very well for these interaction types. A survey of side-by-side base interactions, of which the adenosine platform is the best known example, also locates examples of similar base rearrangements that we consider to be important in structural regulation. A number of examples were found, with GU platforms being particularly prevalent. A GC platform in the RNA of the Thermus thermophilus small ribosomal subunit is in an analogous position to an adenosine platform in other species. An unusual GG platform is also observed close to one of the substrate binding sites in Haloarcula marismortui large ribosomal subunit RNA.