Topology Based Selection and Curation of Level Sets

Geometric Detection Algorithms for Cavities on Protein Surfaces in Molecular Graphics: A Survey

Detecting and analyzing protein cavities provides significant information about active sites for biological processes (e.g., protein-protein or protein-ligand binding) in molecular graphics and modeling. Using the three-dimensional structure of a given protein (i.e., atom types and their locations in 3D) as retrieved from a PDB (Protein Data Bank) file, it is now computationally viable to determine a description of these cavities. Such cavities correspond to pockets, clefts, invaginations, voids, tunnels, channels, and grooves on the surface of a given protein. In this work, we survey the literature on protein cavity computation and classify algorithmic approaches into three categories: evolution-based, energy-based, and geometry-based. Our survey focuses on geometric algorithms, whose taxonomy is extended to include not only sphere-, grid-, and tessellation-based methods, but also surface-based, hybrid geometric, consensus, and time-varying methods. Finally, we detail those techniques that have been customized for GPU (Graphics Processing Unit) computing.

Interstitial and Interlayer Ion Diffusion Geometry Extraction in Graphitic Nanosphere Battery Materials

Large-scale molecular dynamics (MD) simulations are commonly used for simulating the synthesis and ion diffusion of battery materials. A good battery anode material is determined by its capacity to store ion or other diffusers. However, modeling of ion diffusion dynamics and transport properties at large length and long time scales would be impossible with current MD codes. To analyze the fundamental properties of these materials, therefore, we turn to geometric and topological analysis of their structure. In this paper, we apply a novel technique inspired by discrete Morse theory to the Delaunay triangulation of the simulated geometry of a thermally annealed carbon nanosphere. We utilize our computed structures to drive further geometric analysis to extract the interstitial diffusion structure as a single mesh. Our results provide a new approach to analyze the geometry of the simulated carbon nanosphere, and new insights into the role of carbon defect size and distribution in determining the charge capacity and charge dynamics of these carbon based battery materials.

Detection of secondary and supersecondary structures of proteins from cryo-electron microscopy

Recent advances in three-dimensional electron microscopy (3D EM) have enabled the quantitative visualization of the structural building blocks of proteins at improved resolutions. We provide algorithms to detect the secondary structures (α-helices and β-sheets) from proteins for which the volumetric maps are reconstructed at 6-10Å resolution. Additionally, we show that when the resolution is coarser than 10Å, some of the supersecondary structures can be detected from 3D EM maps. For both these algorithms, we employ tools from computational geometry and differential topology, specifically the computation of stable/unstable manifolds of certain critical points of the distance function induced by the molecular surface. Our results connect mathematically well-defined constructions with bio-chemically induced structures observed in proteins.

Voronoi-based extraction and visualization of molecular paths

Visual analysis is widely used to study the behavior of molecules. Of particular interest are the analysis of molecular interactions and the investigation of binding sites. For large molecules, however, it is difficult to detect possible binding sites and paths leading to these sites by pure visual inspection. In this paper, we present new methods for the computation and visualization of potential molecular paths. Using a novel filtering method, we extract the significant paths from the Voronoi diagram of spheres. For the interactive visualization of molecules and their paths, we present several methods using deferred shading and other state-of-the-art techniques. To allow for a fast overview of reachable regions of the molecule, we illuminate the molecular surface using a large number of light sources placed on the extracted paths. We also provide a method to compute the extension surface of selected paths and visualize it using the skin surface. Furthermore, we use the extension surface to clip the molecule to allow easy visual tracking of even deeply buried paths. The methods are applied to several proteins to demonstrate their usefulness.

Computing robustness and persistence for images

We are interested in 3-dimensional images given as arrays of voxels with intensity values. Extending these values to a continuous function, we study the robustness of homology classes in its level and interlevel sets, that is, the amount of perturbation needed to destroy these classes. The structure of the homology classes and their robustness, over all level and interlevel sets, can be visualized by a triangular diagram of dots obtained by computing the extended persistence of the function. We give a fast hierarchical algorithm using the dual complexes of oct-tree approximations of the function. In addition, we show that for balanced oct-trees, the dual complexes are geometrically realized in R³ and can thus be used to construct level and interlevel sets. We apply these tools to study 3-dimensional images of plant root systems.

A Fast Variational Method for the Construction of Resolution Adaptive C-Smooth Molecular Surfaces

We present a variational approach to smooth molecular (proteins, nucleic acids) surface constructions, starting from atomic coordinates, as available from the protein and nucleic-acid data banks. Molecular dynamics (MD) simulations traditionally used in understanding protein and nucleic-acid folding processes, are based on molecular force fields, and require smooth models of these molecular surfaces. To accelerate MD simulations, a popular methodology is to employ coarse grained molecular models, which represent clusters of atoms with similar physical properties by psuedo- atoms, resulting in coarser resolution molecular surfaces. We consider generation of these mixed-resolution or adaptive molecular surfaces. Our approach starts from deriving a general form second order geometric partial differential equation in the level-set formulation, by minimizing a first order energy functional which additionally includes a regularization term to minimize the occurrence of chemically infeasible molecular surface pockets or tunnel-like artifacts. To achieve even higher computational efficiency, a fast cubic B-spline C(2) interpolation algorithm is also utilized. A narrow band, tri-cubic B-spline level-set method is then used to provide C(2) smooth and resolution adaptive molecular surfaces.

AUTOMATIC STRUCTURE INTERPRETATION OF SINGLE PARTICLE CRYO-ELECTRON MICROSCOPY: FROM IMAGES TO PSUEDO-ATOMIC MODELS

Three dimensional Electron Microscopy (EM) and in particular single particle reconstruction using cryo-EM, has rapidly advanced over recent years, such that increasingly several macromolecular complexes can be resolved at subnanometer resolution (6-10 Å). This paper reviews some of the main volumetric image and geometric post-processing steps once a three dimensional EM map (henceforth a 3D map) has been reconstructed from single particle Cryo-EM, as essential steps in an enhanced and automated computational structure interpretation pipeline. In particular the paper addresses automated filtering, critical point calculations, symmetric and non-symmetric molecular domain segmentation, molecular surface selection, curation, and protein secondary structure (α- helices and β-sheets) elucidation from 3D maps.