Recipes for when physics fails: recovering robust learning of physics informed neural networks

Physics-informed neural networks (PINNs) have been shown to be effective in solving partial differential equations by capturing the physics induced constraints as a part of the training loss function. This paper shows that a PINN can be sensitive to errors in training data and overfit itself in dynamically propagating these errors over the domain of the solution of the PDE. It also shows how physical regularizations based on continuity criteria and conservation laws fail to address this issue and rather introduce problems of their own causing the deep network to converge to a physics-obeying local minimum instead of the global minimum. We introduce Gaussian process (GP) based smoothing that recovers the performance of a PINN and promises a robust architecture against noise/errors in measurements. Additionally, we illustrate an inexpensive method of quantifying the evolution of uncertainty based on the variance estimation of GPs on boundary data. Robust PINN performance is also shown to be achievable by choice of sparse sets of inducing points based on sparsely induced GPs. We demonstrate the performance of our proposed methods and compare the results from existing benchmark models in literature for time-dependent Schrödinger and Burgers' equations.

Materials for emergent silicon-integrated optical computing

Progress in computing architectures is approaching a paradigm shift: traditional computing based on digital complementary metal-oxide semiconductor technology is nearing physical limits in terms of miniaturization, speed, and, especially, power consumption. Consequently, alternative approaches are under investigation. One of the most promising is based on a "brain-like" or neuromorphic computation scheme. Another approach is quantum computing using photons. Both of these approaches can be realized using silicon photonics, and at the heart of both technologies is an efficient, ultra-low power broad band optical modulator. As silicon modulators suffer from relatively high power consumption, materials other than silicon itself have to be considered for the modulator. In this Perspective, we present our view on such materials. We focus on oxides showing a strong linear electro-optic effect that can also be integrated with Si, thus capitalizing on new materials to enable the devices and circuit architectures that exploit shifting computational machine learning paradigms, while leveraging current manufacturing infrastructure. This is expected to result in a new generation of computers that consume less power and possess a larger bandwidth.

Weighted Random Forests to Improve Arrhythmia Classification

Construction of an ensemble model is a process of combining many diverse base predictive learners. It arises questions of how to weight each model and how to tune the parameters of the weighting process. The most straightforward approach is simply to average the base models. However, numerous studies have shown that a weighted ensemble can provide superior prediction results to a simple average of models. The main goals of this article are to propose a new weighting algorithm applicable for each tree in the Random Forest model and the comprehensive examination of the optimal parameter tuning. Importantly, the approach is motivated by its flexibility, good performance, stability, and resistance to overfitting. The proposed scheme is examined and evaluated on the Physionet/Computing in Cardiology Challenge 2015 data set. It consists of signals (electrocardiograms and pulsatory waveforms) from intensive care patients which triggered an alarm for five cardiac arrhythmia types (Asystole, Bradycardia, Tachycardia, Ventricular Tachycardia, and Ventricular Fultter/Fibrillation). The classification problem regards whether the alarm should or should not have been generated. It was proved that the proposed weighting approach improved classification accuracy for the three most challenging out of the five investigated arrhythmias comparing to the standard Random Forest model.

SketchyCoreSVD: SketchySVD from Random Subsampling of the Data Matrix

We present a method called SketchyCoreSVD to compute the near-optimal rank r SVD of a data matrix by building random sketches only from its subsampled columns and rows. We provide theoretical guarantees under incoherence assumptions, and validate the performance of our SketchyCoreSVD method on various large static and time-varying datasets.

Stein Variational Gradient Descent with Matrix-Valued Kernels

Stein variational gradient descent (SVGD) is a particle-based inference algorithm that leverages gradient information for efficient approximate inference. In this work, we enhance SVGD by leveraging preconditioning matrices, such as the Hessian and Fisher information matrix, to incorporate geometric information into SVGD updates. We achieve this by presenting a generalization of SVGD that replaces the scalar-valued kernels in vanilla SVGD with more general matrix-valued kernels. This yields a significant extension of SVGD, and more importantly, allows us to flexibly incorporate various preconditioning matrices to accelerate the exploration in the probability landscape. Empirical results show that our method outperforms vanilla SVGD and a variety of baseline approaches over a range of real-world Bayesian inference tasks.

A Streaming model for Generalized Rayleigh with extension to Minimum Noise Fraction

The Rayleigh quotient optimization is the maximization of a rational function, or a max-min problem, with simultaneous maximization of the numerator function and minimization of the denominator function. Here, we describe a low-rank, streaming solution for Rayleigh quotient optimization applicable for big-data scenarios where the data matrix is too large to be fully loaded into main memory. We apply this for a maximization of the Signal to Noise ratio of big-data, of very large static and dynamic data. Our implementation is shown to achieve faster processing time compared to a standard data read into memory. We demonstrate the trade-offs with synthetic and real data, on different scales to validate the approach in terms of accuracy, speed and storage.

Tensor Maps for Synchronizing Heterogeneous Shape Collections

Establishing high-quality correspondence maps between geometric shapes has been shown to be the fundamental problem in managing geometric shape collections. Prior work has focused on computing efficient maps between pairs of shapes, and has shown a quantifiable benefit of joint map synchronization, where a collection of shapes are used to improve (denoise) the pairwise maps for consistency and correctness. However, these existing map synchronization techniques place very strong assumptions on the input shapes collection such as all the input shapes fall into the same category and/or the majority of the input pairwise maps are correct. In this paper, we present a multiple map synchronization approach that takes a heterogeneous shape collection as input and simultaneously outputs consistent dense pairwise shape maps. We achieve our goal by using a novel tensor-based representation for map synchronization, which is efficient and robust than all prior matrix-based representations. We demonstrate the usefulness of this approach across a wide range of geometric shape datasets and the applications in shape clustering and shape co-segmentation.

Dynamic Filtering with Large Sampling Field for ConvNets

We propose a dynamic filtering strategy with large sampling field for ConvNets (LS-DFN), where the position-specific kernels learn from not only the identical position but also multiple sampled neighbour regions. During sampling, residual learning is introduced to ease training and an attention mechanism is applied to fuse features from different samples. Such multiple samples enlarge the kernels receptive fields significantly without requiring more parameters. While LS-DFN inherits the advantages of DFN [5], namely avoiding feature map blurring by positionwise kernels while keeping translation invariance, it also efficiently alleviates the overfitting issue caused by much more parameters than normal CNNs. Our model is efficient and can be trained end-to-end via standard back-propagation. We demonstrate the merits of our LS-DFN on both sparse and dense prediction tasks involving object detection, semantic segmentation and flow estimation. Our results show LS-DFN enjoys stronger recognition abilities in object detection and semantic segmentation tasks on VOC benchmark [8] and sharper responses in flow estimation on FlyingChairs dataset [6] compared to strong baselines.

SMAC: Simultaneous Mapping and Clustering Using Spectral Decompositions

We introduce a principled approach for simultaneous mapping and clustering (SMAC) for establishing consistent maps across heterogeneous object collections (e.g., 2D images or 3D shapes). Our approach takes as input a heterogeneous object collection and a set of maps computed between some pairs of objects, and outputs a homogeneous object clustering together with a new set of maps possessing optimal intra- and inter-cluster consistency. Our approach is based on the spectral decomposition of a data matrix storing all pairwise maps in its blocks. We additionally provide tight theoretical guarantees for the accuracy of SMAC under established noise models. We also demonstrate the usefulness of our approach on synthetic and real datasets.

Functional Data Approximation on Bounded Domains using Polygonal Finite Elements

We construct and analyze piecewise approximations of functional data on arbitrary 2D bounded domains using generalized barycentric finite elements, and particularly quadratic serendipity elements for planar polygons. We compare approximation qualities (precision/convergence) of these partition-of-unity finite elements through numerical experiments, using Wachspress coordinates, natural neighbor coordinates, Poisson coordinates, mean value coordinates, and quadratic serendipity bases over polygonal meshes on the domain. For a convex n-sided polygon, the quadratic serendipity elements have 2n basis functions, associated in a Lagrange-like fashion to each vertex and each edge midpoint, rather than the usual n(n + 1)/2 basis functions to achieve quadratic convergence. Two greedy algorithms are proposed to generate Voronoi meshes for adaptive functional/scattered data approximations. Experimental results show space/accuracy advantages for these quadratic serendipity finite elements on polygonal domains versus traditional finite elements over simplicial meshes. Polygonal meshes and parameter coefficients of the quadratic serendipity finite elements obtained by our greedy algorithms can be further refined using an L₂-optimization to improve the piecewise functional approximation. We conduct several experiments to demonstrate the efficacy of our algorithm for modeling features/discontinuities in functional data/image approximation.

Efficient Clustering-based Noise Covariance Estimation for Maximum Noise Fraction

Most hyperspectral images (HSI) have important spectral features in specific combination of wave numbers or channels. Noise in these specific channels or bands can easily overwhelm these relevant spectral features. Maximum Noise Fraction (MNF) by Green et al. [1] has been extensively studied for noise removal in HSI data. The MNF transform maximizes the Signal to Noise Ratio (SNR) in feature space, thereby explicitly requiring an estimation of the HSI noise. We present two simple and efficient Noise Covariance Matrix (NCM) estimation methods as required for the MNF transform. Our NCM estimations improve the performance of HSI classification, even when ground objects are mixed. Both techniques rely on a superpixel based clustering of HSI data in the spatial domain. The novelty of our NCM's comes from their reduced sensitivity to HSI noise distributions and interference patterns. Experiments with both simulated and real HSI data show that our methods significantly outperforms the NCM estimation in the classical MNF transform, as well as against more recent state of the art NCM estimation methods. We quantify this improvement in terms of HSI classification accuracy and superior recovery of spectral features.

Translation Synchronization via Truncated Least Squares

In this paper, we introduce a robust algorithm, TranSync, for the 1D translation synchronization problem, in which the aim is to recover the global coordinates of a set of nodes from noisy measurements of relative coordinates along an observation graph. The basic idea of TranSync is to apply truncated least squares, where the solution at each step is used to gradually prune out noisy measurements. We analyze TranSync under both deterministic and randomized noisy models, demonstrating its robustness and stability. Experimental results on synthetic and real datasets show that TranSync is superior to state-of-the-art convex formulations in terms of both efficiency and accuracy.

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.

SHAPE BASED IMAGE RECONSTRUCTION USING LINEARIZED DEFORMATIONS

We introduce a reconstruction framework that can account for shape related a priori information in ill-posed linear inverse problems in imaging. It is a variational scheme that uses a shape functional defined using deformable templates machinery from shape theory. As proof of concept, we apply the proposed shape based reconstruction to 2D tomography with very sparse measurements, and demonstrate strong empirical results.

Uncertainty Quantified Computational Analysis of the Energetics of Virus Capsid Assembly

Most of the existing research in assembly pathway prediction/analysis of viral capsids makes the simplifying assumption that the configuration of the intermediate states can be extracted directly from the final configuration of the entire capsid. This assumption does not take into account the conformational changes of the constituent proteins as well as minor changes to the binding interfaces that continue throughout the assembly process until stabilization. This paper presents a statistical-ensemble based approach which samples the configurational space for each monomer with the relative local orientation between monomers, to capture the uncertainties in binding and conformations. Furthermore, instead of using larger capsomers (trimers, pentamers) as building blocks, we allow all possible subassemblies to bind in all possible combinations. We represent the resulting assembly graph in two different ways: First, we use the Wilcoxon signed rank measure to compare the distributions of binding free energy computed on the sampled conformations to predict likely pathways. Second, we represent chemical equilibrium aspects of the transitions as a Bayesian Factor graph where both associations and dissociations are modeled based on concentrations and the binding free energies. We applied these protocols on the feline panleukopenia virus and the Nudaurelia capensis virus. Results from these experiments showed significant departure from those one would obtain if only the static configurations of the proteins were considered. Hence, we establish the importance of an uncertainty-aware protocol for pathway analysis, and provide a statistical framework as an important first step towards assembly pathway prediction with high statistical confidence.

Statistical Framework for Uncertainty Quantification in Computational Molecular Modeling

As computational modeling, simulation, and predictions are becoming integral parts of biomedical pipelines, it behooves us to emphasize the reliability of the computational protocol. For any reported quantity of interest (QOI), one must also compute and report a measure of the uncertainty or error associated with the QOI. This is especially important in molecular modeling, since in most practical applications the inputs to the computational protocol are often noisy, incomplete, or low-resolution. Unfortunately, currently available modeling tools do not account for uncertainties and their effect on the final QOIs with sufficient rigor. We have developed a statistical framework that expresses the uncertainty of the QOI as the probability that the reported value deviates from the true value by more than some user-defined threshold. First, we provide a theoretical approach where this probability can be bounded using Azuma-Hoeffding like inequalities. Second, we approximate this probability empirically by sampling the space of uncertainties of the input and provide applications of our framework to bound uncertainties of several QOIs commonly used in molecular modeling. Finally, we also present several visualization techniques to effectively and quantitavely visualize the uncertainties: in the input, final QOIs, and also intermediate states.

CONSTRUCTION OF SCALAR AND VECTOR FINITE ELEMENT FAMILIES ON POLYGONAL AND POLYHEDRAL MESHES

We combine theoretical results from polytope domain meshing, generalized barycentric coordinates, and finite element exterior calculus to construct scalar- and vector-valued basis functions for conforming finite element methods on generic convex polytope meshes in dimensions 2 and 3. Our construction recovers well-known bases for the lowest order Nédélec, Raviart-Thomas, and Brezzi-Douglas-Marini elements on simplicial meshes and generalizes the notion of Whitney forms to non-simplicial convex polygons and polyhedra. We show that our basis functions lie in the correct function space with regards to global continuity and that they reproduce the requisite polynomial differential forms described by finite element exterior calculus. We present a method to count the number of basis functions required to ensure these two key properties.

On the construction of general cubature formula by flat extensions

We describe a new method to compute general cubature formulae. The problem is initially transformed into the computation of truncated Hankel operators with flat extensions. We then analyze the algebraic properties associated to flat extensions and show how to recover the cubature points and weights from the truncated Hankel operator. We next present an algorithm to test the flat extension property and to additionally compute the decomposition. To generate cubature formulae with a minimal number of points, we propose a new relaxation hierarchy of convex optimization problems minimizing the nuclear norm of the Hankel operators. For a suitably high order of convex relaxation, the minimizer of the optimization problem corresponds to a cubature formula. Furthermore cubature formulae with a minimal number of points are associated to faces of the convex sets. We illustrate our method on some examples, and for each we obtain a new minimal cubature formula.

Sliced Configuration Spaces for Curved Planar Bodies

We present the first practical, implemented configuration-space computation algorithm for a curved, planar object translating and rotating amidst stationary obstacles. The bodies are rigid, compact, regular, and bounded by a finite number of rational parametric curve segments. The algorithm represents the three-dimensional configu ration space as two-dimensional slices in which the moving object has a fixed orientation. It discretizes the configuration space into in tervals of equivalent slices separated by critical slices. The output is topologically correct and accurate to within a specified toler ance. We have implemented the algorithm for objects bounded by line segments and circular arcs, which is an important class for applications. The program is simple, fast, and robust. The slice representation is a natural and efficient abstract data type for geo metric computations in robotics and engineering.

PF2fit: Polar Fast Fourier Matched Alignment of Atomistic Structures with 3D Electron Microscopy Maps

There continue to be increasing occurrences of both atomistic structure models in the PDB (possibly reconstructed from X-ray diffraction or NMR data), and 3D reconstructed cryo-electron microscopy (3D EM) maps (albeit at coarser resolution) of the same or homologous molecule or molecular assembly, deposited in the EMDB. To obtain the best possible structural model of the molecule at the best achievable resolution, and without any missing gaps, one typically aligns (match and fits) the atomistic structure model with the 3D EM map. We discuss a new algorithm and generalized framework, named PF(2) fit (Polar Fast Fourier Fitting) for the best possible structural alignment of atomistic structures with 3D EM. While PF(2) fit enables only a rigid, six dimensional (6D) alignment method, it augments prior work on 6D X-ray structure and 3D EM alignment in multiple ways: Scoring. PF(2) fit includes a new scoring scheme that, in addition to rewarding overlaps between the volumes occupied by the atomistic structure and 3D EM map, rewards overlaps between the volumes complementary to them. We quantitatively demonstrate how this new complementary scoring scheme improves upon existing approaches. PF(2) fit also includes two scoring functions, the non-uniform exterior penalty and the skeleton-secondary structure score, and implements the scattering potential score as an alternative to traditional Gaussian blurring. Search. PF(2) fit utilizes a fast polar Fourier search scheme, whose main advantage is the ability to search over uniformly and adaptively sampled subsets of the space of rigid-body motions. PF(2) fit also implements a new reranking search and scoring methodology that considerably improves alignment metrics in results obtained from the initial search.

Accelerated Molecular Mechanical and Solvation Energetics on Multicore CPUs and Manycore GPUs

MOTIVATION

Despite several reported acceleration successes of programmable GPUs (Graphics Processing Units) for molecular modeling and simulation tools, the general focus has been on fast computation with small molecules. This was primarily due to the limited memory size on the GPU. Moreover simultaneous use of CPU and GPU cores for a single kernel execution - a necessity for achieving high parallelism - has also not been fully considered.

RESULTS

We present fast computation methods for molecular mechanical (Lennard-Jones and Coulombic) and generalized Born solvation energetics which run on commodity multicore CPUs and manycore GPUs. The key idea is to trade off accuracy of pairwise, long-range atomistic energetics for higher speed of execution. A simple yet efficient CUDA kernel for GPU acceleration is presented which ensures high arithmetic intensity and memory efficiency. Our CUDA kernel uses a cache-friendly, recursive and linear-space octree data structure to handle very large molecular structures with up to several million atoms. Based on this CUDA kernel, we present a hybrid method which simultaneously exploits both CPU and GPU cores to provide the best performance based on selected parameters of the approximation scheme. Our CUDA kernels achieve more than two orders of magnitude speedup over serial computation for many of the molecular energetics terms. The hybrid method is shown to be able to achieve the best performance for all values of the approximation parameter.

AVAILABILITY

The source code and binaries are freely available as PMEOPA (Parallel Molecular Energetic using Octree Pairwise Approximation) and downloadable from http://cvcweb.ices.utexas.edu/software.

Approximating the Generalized Voronoi Diagram of Closely Spaced Objects

We present an algorithm to compute an approximation of the generalized Voronoi diagram (GVD) on arbitrary collections of 2D or 3D geometric objects. In particular, we focus on datasets with closely spaced objects; GVD approximation is expensive and sometimes intractable on these datasets using previous algorithms. With our approach, the GVD can be computed using commodity hardware even on datasets with many, extremely tightly packed objects. Our approach is to subdivide the space with an octree that is represented with an adjacency structure. We then use a novel adaptive distance transform to compute the distance function on octree vertices. The computed distance field is sampled more densely in areas of close object spacing, enabling robust and parallelizable GVD surface generation. We demonstrate our method on a variety of data and show example applications of the GVD in 2D and 3D.

Highly Symmetric and Congruently Tiled Meshes for Shells and Domes

We describe the generation of all possible shell and dome shapes that can be uniquely meshed (tiled) using a single type of mesh face (tile), and following a single meshing (tiling) rule that governs the mesh (tile) arrangement with maximal vertex, edge and face symmetries. Such tiling arrangements or congruently tiled meshed shapes, are frequently found in chemical forms (fullerenes or Bucky balls, crystals, quasi-crystals, virus nano shells or capsids), and synthetic shapes (cages, sports domes, modern architectural facades). Congruently tiled meshes are both aesthetic and complete, as they support maximal mesh symmetries with minimal complexity and possess simple generation rules. Here, we generate congruent tilings and meshed shape layouts that satisfy these optimality conditions. Further, the congruent meshes are uniquely mappable to an almost regular 3D polyhedron (or its dual polyhedron) and which exhibits face-transitive (and edge-transitive) congruency with at most two types of vertices (each type transitive to the other). The family of all such congruently meshed polyhedra create a new class of meshed shapes, beyond the well-studied regular, semi-regular and quasi-regular classes, and their duals (platonic, Catalan and Johnson). While our new mesh class is infinite, we prove that there exists a unique mesh parametrization, where each member of the class can be represented by two integer lattice variables, and moreover efficiently constructable.

VolRoverN: enhancing surface and volumetric reconstruction for realistic dynamical simulation of cellular and subcellular function

Establishing meaningful relationships between cellular structure and function requires accurate morphological reconstructions. In particular, there is an unmet need for high quality surface reconstructions to model subcellular and synaptic interactions among neurons and glia at nanometer resolution. We address this need with VolRoverN, a software package that produces accurate, efficient, and automated 3D surface reconstructions from stacked 2D contour tracings. While many techniques and tools have been developed in the past for 3D visualization of cellular structure, the reconstructions from VolRoverN meet specific quality criteria that are important for dynamical simulations. These criteria include manifoldness, water-tightness, lack of self- and object-object-intersections, and geometric accuracy. These enhanced surface reconstructions are readily extensible to any cell type and are used here on spiny dendrites with complex morphology and axons from mature rat hippocampal area CA1. Both spatially realistic surface reconstructions and reduced skeletonizations are produced and formatted by VolRoverN for easy input into analysis software packages for neurophysiological simulations at multiple spatial and temporal scales ranging from ion electro-diffusion to electrical cable models.

Human heart conjugate cooling simulation: unsteady thermo-fluid-stress analysis

The main objective of this work was to demonstrate computationally that realistic human hearts can be cooled much faster by performing conjugate heat transfer consisting of pumping a cold liquid through the cardiac chambers and major veins while keeping the heart submerged in cold gelatin filling a cooling container. The human heart geometry used for simulations was obtained from three-dimensional, high resolution CT-angio scans. Two fluid flow domains for the right (pulmonic) and left (systemic) heart circulations, and two solid domains for the heart tissue and gelatin solution were defined for multi-domain numerical simulation. Detailed unsteady temperature fields within the heart tissue were calculated during the conjugate cooling process. A linear thermoelasticity analysis was performed to assess the stresses applied on the heart due to the coolant fluid shear and normal forces and to examine the thermal stress caused by temperature variation inside the heart. It was demonstrated that a conjugate cooling effort with coolant temperature at +4°C is capable of reducing the average heart temperature from +37°C to +8°C in 25 minutes for cases in which the coolant was steadily pumped only through major heart inlet veins and cavities.

Efficient Maintenance and Update of Nonbonded Lists in Macromolecular Simulations

Molecular mechanics and dynamics simulations use distance based cutoff approximations for faster computation of pairwise van der Waals and electrostatic energy terms. These approximations traditionally use a precalculated and periodically updated list of interacting atom pairs, known as the "nonbonded neighborhood lists" or nblists, in order to reduce the overhead of finding atom pairs that are within distance cutoff. The size of nblists grows linearly with the number of atoms in the system and superlinearly with the distance cutoff, and as a result, they require significant amount of memory for large molecular systems. The high space usage leads to poor cache performance, which slows computation for large distance cutoffs. Also, the high cost of updates means that one cannot afford to keep the data structure always synchronized with the configuration of the molecules when efficiency is at stake. We propose a dynamic octree data structure for implicit maintenance of nblists using space linear in the number of atoms but independent of the distance cutoff. The list can be updated very efficiently as the coordinates of atoms change during the simulation. Unlike explicit nblists, a single octree works for all distance cutoffs. In addition, octree is a cache-friendly data structure, and hence, it is less prone to cache miss slowdowns on modern memory hierarchies than nblists. Octrees use almost 2 orders of magnitude less memory, which is crucial for simulation of large systems, and while they are comparable in performance to nblists when the distance cutoff is small, they outperform nblists for larger systems and large cutoffs. Our tests show that octree implementation is approximately 1.5 times faster in practical use case scenarios as compared to nblists.

Electron tomography of cryo-immobilized plant tissue: a novel approach to studying 3D macromolecular architecture of mature plant cell walls in situ

Cost-effective production of lignocellulosic biofuel requires efficient breakdown of cell walls present in plant biomass to retrieve the wall polysaccharides for fermentation. In-depth knowledge of plant cell wall composition is therefore essential for improving the fuel production process. The precise spatial three-dimensional (3D) organization of cellulose, hemicellulose, pectin and lignin within plant cell walls remains unclear to date since the microscopy techniques used so far have been limited to two-dimensional, topographic or low-resolution imaging, or required isolation or chemical extraction of the cell walls. In this paper we demonstrate that by cryo-immobilizing fresh tissue, then either cryo-sectioning or freeze-substituting and resin embedding, followed by cryo- or room temperature (RT) electron tomography, respectively, we can visualize previously unseen details of plant cell wall architecture in 3D, at macromolecular resolution (∼2 nm), and in near-native state. Qualitative and quantitative analyses showed that wall organization of cryo-immobilized samples were preserved remarkably better than conventionally prepared samples that suffer substantial extraction. Lignin-less primary cell walls were well preserved in both self-pressurized rapidly frozen (SPRF), cryo-sectioned samples as well as high-pressure frozen, freeze-substituted and resin embedded (HPF-FS-resin) samples. Lignin-rich secondary cell walls appeared featureless in HPF-FS-resin sections presumably due to poor stain penetration, but their macromolecular features could be visualized in unprecedented details in our cryo-sections. While cryo-tomography of vitreous tissue sections is currently proving to be instrumental in developing 3D models of lignin-rich secondary cell walls, here we confirm that the technically easier method of RT-tomography of HPF-FS-resin sections could be used immediately for routine study of low-lignin cell walls. As a proof of principle, we characterized the primary cell walls of a mutant (cob-6) and wild type Arabidopsis hypocotyl parenchyma cells by RT-tomography of HPF-FS-resin sections, and detected a small but significant difference in spatial organization of cellulose microfibrils in the mutant walls.

Interpolation Error Estimates for Mean Value Coordinates over Convex Polygons

In a similar fashion to estimates shown for Harmonic, Wachspress, and Sibson coordinates in [Gillette et al., AiCM, to appear], we prove interpolation error estimates for the mean value coordinates on convex polygons suitable for standard finite element analysis. Our analysis is based on providing a uniform bound on the gradient of the mean value functions for all convex polygons of diameter one satisfying certain simple geometric restrictions. This work makes rigorous an observed practical advantage of the mean value coordinates: unlike Wachspress coordinates, the gradient of the mean value coordinates does not become large as interior angles of the polygon approach π.

Protein-protein docking with F(2)Dock 2.0 and GB-rerank

Motivation

Computational simulation of protein-protein docking can expedite the process of molecular modeling and drug discovery. This paper reports on our new F² Dock protocol which improves the state of the art in initial stage rigid body exhaustive docking search, scoring and ranking by introducing improvements in the shape-complementarity and electrostatics affinity functions, a new knowledge-based interface propensity term with FFT formulation, a set of novel knowledge-based filters and finally a solvation energy (GBSA) based reranking technique. Our algorithms are based on highly efficient data structures including the dynamic packing grids and octrees which significantly speed up the computations and also provide guaranteed bounds on approximation error.

Results

The improved affinity functions show superior performance compared to their traditional counterparts in finding correct docking poses at higher ranks. We found that the new filters and the GBSA based reranking individually and in combination significantly improve the accuracy of docking predictions with only minor increase in computation time. We compared F² Dock 2.0 with ZDock 3.0.2 and found improvements over it, specifically among 176 complexes in ZLab Benchmark 4.0, F² Dock 2.0 finds a near-native solution as the top prediction for 22 complexes; where ZDock 3.0.2 does so for 13 complexes. F² Dock 2.0 finds a near-native solution within the top 1000 predictions for 106 complexes as opposed to 104 complexes for ZDock 3.0.2. However, there are 17 and 15 complexes where F² Dock 2.0 finds a solution but ZDock 3.0.2 does not and vice versa; which indicates that the two docking protocols can also complement each other.

Availability

The docking protocol has been implemented as a server with a graphical client (TexMol) which allows the user to manage multiple docking jobs, and visualize the docked poses and interfaces. Both the server and client are available for download. Server: http://www.cs.utexas.edu/~bajaj/cvc/software/f2dock.shtml. Client: http://www.cs.utexas.edu/~bajaj/cvc/software/f2dockclient.shtml.

High-resolution cryo-electron microscopy structure of the Trypanosoma brucei ribosome

Ribosomes, the protein factories of living cells, translate genetic information carried by messenger RNAs into proteins, and are thus involved in virtually all aspects of cellular development and maintenance. The few available structures of the eukaryotic ribosome reveal that it is more complex than its prokaryotic counterpart, owing mainly to the presence of eukaryote-specific ribosomal proteins and additional ribosomal RNA insertions, called expansion segments. The structures also differ among species, partly in the size and arrangement of these expansion segments. Such differences are extreme in kinetoplastids, unicellular eukaryotic parasites often infectious to humans. Here we present a high-resolution cryo-electron microscopy structure of the ribosome of Trypanosoma brucei, the parasite that is transmitted by the tsetse fly and that causes African sleeping sickness. The atomic model reveals the unique features of this ribosome, characterized mainly by the presence of unusually large expansion segments and ribosomal-protein extensions leading to the formation of four additional inter-subunit bridges. We also find additional rRNA insertions, including one large rRNA domain that is not found in other eukaryotes. Furthermore, the structure reveals the five cleavage sites of the kinetoplastid large ribosomal subunit (LSU) rRNA chain, which is known to be cleaved uniquely into six pieces, and suggests that the cleavage is important for the maintenance of the T. brucei ribosome in the observed structure. We discuss several possible implications of the large rRNA expansion segments for the translation-regulation process. The structure could serve as a basis for future experiments aimed at understanding the functional importance of these kinetoplastid-specific ribosomal features in protein-translation regulation, an essential step towards finding effective and safe kinetoplastid-specific drugs.

Shape-based regularization of electron tomographic reconstruction

We introduce a tomographic reconstruction method implemented using a shape-based regularization technique. Spatial models of known features in the structure being reconstructed are integrated into the reconstruction process as regularizers. Our regularization scheme is driven locally through shape information obtained from segmentation and compared with a known spatial model. We demonstrated our method on tomography data from digital phantoms, simulated data, and experimental electron tomography (ET) data of virus complexes. Our reconstruction showed reduced blurring and an improvement in the resolution of the reconstructed volume was also measured. This method also produced improved demarcation of spike boundaries in viral membranes when compared with popular techniques like weighted back projection and the algebraic reconstruction technique. Improved ET reconstructions will provide better structure elucidation and improved feature visualization, which can aid in solving key biological issues. Our method can also be generalized to other tomographic modalities.

Error Estimates for Generalized Barycentric Interpolation

We prove the optimal convergence estimate for first order interpolants used in finite element methods based on three major approaches for generalizing barycentric interpolation functions to convex planar polygonal domains. The Wachspress approach explicitly constructs rational functions, the Sibson approach uses Voronoi diagrams on the vertices of the polygon to define the functions, and the Harmonic approach defines the functions as the solution of a PDE. We show that given certain conditions on the geometry of the polygon, each of these constructions can obtain the optimal convergence estimate. In particular, we show that the well-known maximum interior angle condition required for interpolants over triangles is still required for Wachspress functions but not for Sibson functions.

Macromolecular structure modeling from 3D EM using VolRover 2.0

We review tools for structure identification and model-based refinement from three-dimensional electron microscopy implemented in our in-house software package, VOLROVER 2.0. For viral density maps with icosahedral symmetry, we segment the capsid, polymeric, and monomeric subunits using techniques based on automatic symmetry detection and multidomain fast marching. For large biomolecules without symmetry information, we again use our multidomain fast-marching method with manual or fit-based multiseeding to segment meaningful substructures. In either case, we subject the resulting segmented subunit to secondary structure detection when the EM resolution is sufficiently high, and rigid-body structure fitting when the corresponding X-ray structure is available. Secondary structure elements are identified by three techniques: our earlier volume-based and boundary-based skeletonization methods as well as a new method, currently in development, based on solving the grassfire flow equation. For rigid-body fitting, we adapt our earlier fast Fourier-based correlation scheme F2Dock. Our reported segmentation, secondary structure elements identification, and rigid-body fitting techniques, implemented in VOLROVER 2.0 are applied to the PSB 2011 cryo-EM modeling challenge data, and our results are briefly compared to similar results submitted from other research groups. The comparisons show that our techniques are equally capable of segmenting relatively accurate subunits from a viral or protein assembly, and that high segmentation quality leads in turn to higher-quality results of secondary structure elements identification and correlation-based rigid-body fitting. © 2012 Wiley Periodicals, Inc. Biopolymers 97: 709-731, 2012.

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.

An algebraic spline model of molecular surfaces for energetic computations

In this paper, we describe a new method to generate a smooth algebraic spline (AS) approximation of the molecular surface (MS) based on an initial coarse triangulation derived from the atomic coordinate information of the biomolecule, resident in the Protein data bank (PDB). Our method first constructs a triangular prism scaffold covering the PDB structure, and then generates a piecewise polynomial F on the Bernstein-Bezier (BB) basis within the scaffold. An ASMS model of the molecular surface is extracted as the zero contours of F, which is nearly C1 and has dual implicit and parametric representations. The dual representations allow us easily do the point sampling on the ASMS model and apply it to the accurate estimation of the integrals involved in the electrostatic solvation energy computations. Meanwhile comparing with the trivial piecewise linear surface model, fewer number of sampling points are needed for the ASMS, which effectively reduces the complexity of the energy estimation.

Dual Formulations of Mixed Finite Element Methods with Applications

Mixed finite element methods solve a PDE using two or more variables. The theory of Discrete Exterior Calculus explains why the degrees of freedom associated to the different variables should be stored on both primal and dual domain meshes with a discrete Hodge star used to transfer information between the meshes. We show through analysis and examples that the choice of discrete Hodge star is essential to the numerical stability of the method. Additionally, we define interpolation functions and discrete Hodge stars on dual meshes which can be used to create previously unconsidered mixed methods. Examples from magnetostatics and Darcy flow are examined in detail.

Topologically correct reconstruction of tortuous contour forests

Motivated by the need for correct and robust 3D models of neuronal processes, we present a method for reconstruction of spatially realistic and topologically correct models from planar cross sections of multiple objects. Previous work in 3D reconstruction from serial contours has focused on reconstructing one object at a time, potentially producing inter-object intersections between slices. We have developed a robust algorithm that removes these intersections using a geometric approach. Our method not only removes intersections but can guarantee a given minimum separation distance between objects. This paper describes the algorithm for geometric adjustment, proves correctness, and presents several results of our high-fidelity modeling.

Regularization of B-Spline Objects

By a d-dimensional B-spline object (denoted as ), we mean a B-spline curve (d = 1), a B-spline surface (d = 2) or a B-spline volume (d = 3). By regularization of a B-spline object we mean the process of relocating the control points of such that they approximate an isometric map of its definition domain in certain directions and is shape preserving. In this paper we develop an efficient regularization method for , d = 1, 2, 3 based on solving weak form L(2)-gradient flows constructed from the minimization of certain regularizing energy functionals. These flows are integrated via the finite element method using B-spline basis functions. Our experimental results demonstrate that our new regularization method is very effective.

A dynamic data structure for flexible molecular maintenance and informatics

MOTIVATION

We present the 'Dynamic Packing Grid' (DPG), a neighborhood data structure for maintaining and manipulating flexible molecules and assemblies, for efficient computation of binding affinities in drug design or in molecular dynamics calculations.

RESULTS

DPG can efficiently maintain the molecular surface using only linear space and supports quasi-constant time insertion, deletion and movement (i.e. updates) of atoms or groups of atoms. DPG also supports constant time neighborhood queries from arbitrary points. Our results for maintenance of molecular surface and polarization energy computations using DPG exhibit marked improvement in time and space requirements.

AVAILABILITY

http://www.cs.utexas.edu/~bajaj/cvc/software/DPG.shtml.

AN EFFICIENT HIGHER-ORDER FAST MULTIPOLE BOUNDARY ELEMENT SOLUTION FOR POISSON-BOLTZMANN BASED MOLECULAR ELECTROSTATICS

In order to compute polarization energy of biomolecules, we describe a boundary element approach to solving the linearized Poisson-Boltzmann equation. Our approach combines several important features including the derivative boundary formulation of the problem and a smooth approximation of the molecular surface based on the algebraic spline molecular surface. State of the art software for numerical linear algebra and the kernel independent fast multipole method is used for both simplicity and efficiency of our implementation. We perform a variety of computational experiments, testing our method on a number of actual proteins involved in molecular docking and demonstrating the effectiveness of our solver for computing molecular polarization energy.

F2Dock: fast Fourier protein-protein docking

The functions of proteins are often realized through their mutual interactions. Determining a relative transformation for a pair of proteins and their conformations which form a stable complex, reproducible in nature, is known as docking. It is an important step in drug design, structure determination, and understanding function and structure relationships. In this paper, we extend our nonuniform fast Fourier transform-based docking algorithm to include an adaptive search phase (both translational and rotational) and thereby speed up its execution. We have also implemented a multithreaded version of the adaptive docking algorithm for even faster execution on multicore machines. We call this protein-protein docking code F2Dock (F2 = Fast Fourier). We have calibrated F2Dock based on an extensive experimental study on a list of benchmark complexes and conclude that F2Dock works very well in practice. Though all docking results reported in this paper use shape complementarity and Coulombic-potential-based scores only, F2Dock is structured to incorporate Lennard-Jones potential and reranking docking solutions based on desolvation energy .

Computational Inversion of Electron Tomography Images Using L2-Gradient Flows

In this paper, we present a stable, reliable and robust method for reconstructing a three dimensional density function from a set of two dimensional electric tomographic images. By minimizing an energy functional consisting of a fidelity term and a regularization term, an L²-gradient flow is derived. The flow is integrated by a finite element method in the spatial direction and an explicit Euler scheme in temporal direction. The experimental results show that the proposed method is efficient and effective.

Electric-Potential Reconstructions of Single Particles Using L-Gradient Flows

In this paper, we present a stable, reliable and robust method for reconstructing a three dimensional density function from a set of two dimensional electron microscopy images. By minimizing an energy functional consisting of a fidelity term and a regularization term, a L(2)-gradient flow is derived. The flow is integrated by a finite element method in the spatial direction and an explicit Euler scheme in temporal direction. The experimental results show that the proposed method is efficient and effective.

Multi-domain, Higher Order Level Set Scheme for 3D Image Segmentation on the GPU

Level set method based segmentation provides an efficient tool for topological and geometrical shape handling. Conventional level set surfaces are only C(0) continuous since the level set evolution involves linear interpolation to compute derivatives. Bajaj et al. present a higher order method to evaluate level set surfaces that are C(2) continuous, but are slow due to high computational burden. In this paper, we provide a higher order GPU based solver for fast and efficient segmentation of large volumetric images. We also extend the higher order method to multi-domain segmentation. Our streaming solver is efficient in memory usage.

Surface Smoothing and Quality Improvement of Quadrilateral/Hexahedral Meshes with Geometric Flow

This paper describes an approach to smooth the surface and improve the quality of quadrilateral/hexahedral meshes with feature preserved using geometric flow. For quadrilateral surface meshes, the surface diffusion flow is selected to remove noise by relocating vertices in the normal direction, and the aspect ratio is improved with feature preserved by adjusting vertex positions in the tangent direction. For hexahedral meshes, besides the surface vertex movement in the normal and tangent directions, interior vertices are relocated to improve the aspect ratio. Our method has the properties of noise removal, feature preservation and quality improvement of quadrilateral/hexahedral meshes, and it is especially suitable for biomolecular meshes because the surface diffusion flow preserves sphere accurately if the initial surface is close to a sphere. Several demonstration examples are provided from a wide variety of application domains. Some extracted meshes have been extensively used in finite element simulations.