High performance computing in structural determination by electron cryomicroscopy

Computational advances have significantly contributed to the current role of electron cryomicroscopy (cryoEM) in structural biology. The needs for computational power are constantly growing with the increasing complexity of algorithms and the amount of data needed to push the resolution limits. High performance computing (HPC) is becoming paramount in cryoEM to cope with those computational needs. Since the nineties, different HPC strategies have been proposed for some specific problems in cryoEM and, in fact, some of them are already available in common software packages. Nevertheless, the literature is scattered in the areas of computer science and structural biology. In this communication, the HPC approaches devised for the computation-intensive tasks in cryoEM (single particles and tomography) are retrospectively reviewed and the future trends are discussed. Moreover, the HPC capabilities available in the most common cryoEM packages are surveyed, as an evidence of the importance of HPC in addressing the future challenges.     

Implementation and performance evaluation of reconstruction algorithms on graphics processors

The high-throughput needs in electron tomography and in single particle analysis have driven the parallel implementation of several reconstruction algorithms and software packages on computing clusters. Here, we report on the implementation of popular reconstruction algorithms as weighted backprojection, simultaneous iterative reconstruction technique (SIRT) and simultaneous algebraic reconstruction technique (SART) on common graphics processors (GPUs). The speed gain achieved on the GPUs is in the order of sixty (60x) to eighty (80x) times, compared to the performance of a single central processing unit (CPU), which is comparable to the acceleration achieved on a medium-range computing cluster. This acceleration of the reconstruction is caused by the highly specialized architecture of the GPU. Further, we show that the quality of the reconstruction on the GPU is comparable to the CPU. We present detailed flow-chart diagrams of the implementation. The reconstruction software does not require special hardware apart from the commercially available graphics cards and could be easily integrated in software packages like SPIDER, XMIPP, TOM-Package and others.     

TOM software toolbox: acquisition and analysis for electron tomography

Automated data acquisition procedures have changed the perspectives of electron tomography (ET) in a profound manner. Elaborate data acquisition schemes with autotuning functions minimize exposure of the specimen to the electron beam and sophisticated image analysis routines retrieve a maximum of information from noisy data sets. "TOM software toolbox" integrates established algorithms and new concepts tailored to the special needs of low dose ET. It provides a user-friendly unified platform for all processing steps: acquisition, alignment, reconstruction, and analysis. Designed as a collection of computational procedures it is a complete software solution within a highly flexible framework. TOM represents a new way of working with the electron microscope and can serve as the basis for future high-throughput applications.     

Geographical information system parallelization for spatial big data processing: a review

With the increasing interest in large-scale, high-resolution and real-time geographic information system (GIS) applications and spatial big data processing, traditional GIS is not efficient enough to handle the required loads due to limited computational capabilities.Various attempts have been made to adopt high performance computation techniques from different applications, such as designs of advanced architectures, strategies of data partition and direct parallelization method of spatial analysis algorithm, to address such challenges. This paper surveys the current state of parallel GIS with respect to parallel GIS architectures, parallel processing strategies, and relevant topics. We present the general evolution of the GIS architecture which includes main two parallel GIS architectures based on high performance computing cluster and Hadoop cluster. Then we summarize the current spatial data partition strategies, key methods to realize parallel GIS in the view of data decomposition and progress of the special parallel GIS algorithms. We use the parallel processing of GRASS as a case study. We also identify key problems and future potential research directions of parallel GIS.     

Single particle reconstruction of membrane proteins: A tool for understanding the 3D structure of disease-related macromolecules

Membrane proteins play important roles in cell functions such as neurotransmission, muscle contraction, and hormone secretion, but their structures are mostly undetermined. Several techniques have been developed to elucidate the structure of macromolecules; X-ray or electron crystallography, nuclear magnetic resonance spectroscopy, and high-resolution electron microscopy. Electron microscopy-based single particle reconstruction, a computer-aided structure determination method, reconstructs a three-dimensional (3D) structure from projections of monodispersed protein. A large number of particle images are picked up from EM films, aligned and classified to generate two-dimensional (2D) averages, and, using the Euler angle of each 2D average, reconstructed into a 3D structure. This method is challenging due to the necessity for close collaboration between classical biochemistry and innovative information technology, including parallel computing. However, recent progress in electron microscopy, mathematical algorithms, and computational ability has greatly increased the subjects that are considered to be primarily addressable using single particle reconstruction. Membrane proteins are one of these targets to which the single particle reconstruction is successfully applied for understanding of their structures. In this paper, we will introduce recently reconstructed channel-related proteins and discuss the applicability of this technique in understanding molecular structures and their roles in pathology.     

The effect of overabundant projection directions on 3D reconstruction algorithms

The experimental process of collecting images from macromolecules in an electron microscope is such that it does not allow for prior specification of the angular distribution of the projection images. As a consequence, an uneven distribution of projection directions may occur. Concerns have been raised recently about the behavior of 3D reconstruction algorithms for the case of unevenly distributed projections. It has been illustrated on experimental data that in the case of a heavily uneven distribution of projection directions some algorithms tend to elongate the reconstructed volumes along the overloaded direction so much as to make a quantitative biological analysis impossible. In answer to these concerns we have developed a strategy for quantitative comparison and optimization of 3D reconstruction algorithms. We apply this strategy to quantitatively analyze algebraic reconstruction techniques (ART) with blobs, simultaneous iterative reconstruction techniques (SIRT) with voxels, and weighted backprojection (WBP). We show that the elongation artifacts that had been previously reported can be strongly reduced. With our specific choices for the free parameters of the three algorithms, WBP reconstructions tend to be inferior to those obtained with either SIRT or ART and the results obtained with ART are comparable to those with SIRT, but at a very small fraction of the computational cost of SIRT.     

Improved specimen reconstruction by Hilbert phase contrast tomography

The low signal-to-noise ratio (SNR) in images of unstained specimens recorded with conventional defocus phase contrast makes it difficult to interpret 3D volumes obtained by electron tomography (ET). The high defocus applied for conventional tilt series generates some phase contrast but leads to an incomplete transfer of object information. For tomography of biological weak-phase objects, optimal image contrast and subsequently an optimized SNR are essential for the reconstruction of details such as macromolecular assemblies at molecular resolution. The problem of low contrast can be partially solved by applying a Hilbert phase plate positioned in the back focal plane (BFP) of the objective lens while recording images in Gaussian focus. Images recorded with the Hilbert phase plate provide optimized positive phase contrast at low spatial frequencies, and the contrast transfer in principle extends to the information limit of the microscope. The antisymmetric Hilbert phase contrast (HPC) can be numerically converted into isotropic contrast, which is equivalent to the contrast obtained by a Zernike phase plate. Thus, in-focus HPC provides optimal structure factor information without limiting effects of the transfer function. In this article, we present the first electron tomograms of biological specimens reconstructed from Hilbert phase plate image series. We outline the technical implementation of the phase plate and demonstrate that the technique is routinely applicable for tomography. A comparison between conventional defocus tomograms and in-focus HPC volumes shows an enhanced SNR and an improved specimen visibility for in-focus Hilbert tomography.     

Three-dimensional reconstruction using an adaptive simultaneous algebraic reconstruction technique in electron tomography

Three-dimensional (3D) reconstruction of electron tomography (ET) has emerged as an important technique in analyzing structures of complex biological samples. However most of existing reconstruction methods are not suitable for extremely noisy and incomplete data conditions. We present an adaptive simultaneous algebraic reconstruction technique (ASART) in which a modified multilevel access scheme and an adaptive relaxation parameter adjustment method are developed to improve the quality of the reconstructed 3D structure. The reconstruction process is facilitated by using a column-sum substitution approach. This modified multilevel access scheme is adopted to arrange the order of projections so as to minimize the correlations between consecutive views within a limited angle range. In the adaptive relaxation parameter adjustment method, not only the weight matrix (as in the existing methods) but the gray levels of the pixels are employed to adjust the relaxation parameters so that the quality of the reconstruction is improved while the convergence process of the reconstruction is accelerated. In the column-sum substitution approach, the computation to obtain the reciprocal of the sum for the columns in each view is avoided so that the needed computations for each iteration can be reduced. Experimental results show that the proposed technique ASART is better based on objective quality measures than other methods, especially when data is noisy and limited in tilt angles. At the same time, the reconstruction by ASART outperforms that of simultaneous algebraic reconstruction technique (SART) in speed.     

New algorithms for Luria-Delbrück fluctuation analysis

Fluctuation analysis is the most widely used approach in estimating microbial mutation rates. Development of methods for point and interval estimation of mutation rates has long been hampered by lack of closed form expressions for the probability mass function of the number of mutants in a parallel culture. This paper uses sequence convolution to derive exact algorithms for computing the score function and observed Fisher information, leading to efficient computation of maximum likelihood estimates and profile likelihood based confidence intervals for the expected number of mutations occurring in a test tube. These algorithms and their implementation in SALVADOR 2.0 facilitate routine use of modern statistical techniques in fluctuation analysis by biologists engaged in mutation research.     

Three-dimensional imaging of biological complexity

Over the past 5 years, thanks to advances in both instrumentation and computational speed, three-dimensional imaging techniques using the electron microscope have been greatly improved in two areas: electron tomography of cell organelles or cell sections and reconstruction of macromolecules from single particles. Ice embedment has brought a breakthrough in the degree of preservation of specimens under close-to-native conditions. The current challenge is to push the resolution of electron tomographic imaging to a point where macromolecular signatures can be recognized within the cellular context. We show first progress toward this goal by examples in two areas of application: the structure of the muscle triad junction and the architecture and fine structure of mitochondria. As techniques of cryo-microtomy are perfected, we hope to be able to apply tomography to high-pressure frozen sections of tissue.     

XMIPP: a new generation of an open-source image processing package for electron microscopy

X-windows based microscopy image processing package (Xmipp) is a specialized suit of image processing programs, primarily aimed at obtaining the 3D reconstruction of biological specimens from large sets of projection images acquired by transmission electron microscopy. This public-domain software package was introduced to the electron microscopy field eight years ago, and since then it has changed drastically. New methodologies for the analysis of single-particle projection images have been added to classification, contrast transfer function correction, angular assignment, 3D reconstruction, reconstruction of crystals, etc. In addition, the package has been extended with functionalities for 2D crystal and electron tomography data. Furthermore, its current implementation in C++, with a highly modular design of well-documented data structures and functions, offers a convenient environment for the development of novel algorithms. In this paper, we present a general overview of a new generation of Xmipp that has been re-engineered to maximize flexibility and modularity, potentially facilitating its integration in future standardization efforts in the field. Moreover, by focusing on those developments that distinguish Xmipp from other packages available, we illustrate its added value to the electron microscopy community.     

EXCAVATOR: a computer program for efficiently mining gene expression data

Massive amounts of gene expression data are generated using microarrays for functional studies of genes and gene expression data clustering is a useful tool for studying the functional relationship among genes in a biological process. We have developed a computer package EXCAVATOR for clustering gene expression profiles based on our new framework for representing gene expression data as a minimum spanning tree. EXCAVATOR uses a number of rigorous and efficient clustering algorithms. This program has a number of unique features, including capabilities for: (i) data- constrained clustering; (ii) identification of genes with similar expression profiles to pre-specified seed genes; (iii) cluster identification from a noisy background; (iv) computational comparison between different clustering results of the same data set. EXCAVATOR can be run from a Unix/Linux/DOS shell, from a Java interface or from a Web server. The clustering results can be visualized as colored figures and 2-dimensional plots. Moreover, EXCAVATOR provides a wide range of options for data formats, distance measures, objective functions, clustering algorithms, methods to choose number of clusters, etc. The effectiveness of EXCAVATOR has been demonstrated on several experimental data sets. Its performance compares favorably against the popular K-means clustering method in terms of clustering quality and computing time.     

An improved algorithm for anisotropic nonlinear diffusion for denoising cryo-tomograms

Cryo-electron tomography is an imaging technique with an unique potential for visualizing large complex biological specimens. It ensures preservation of the biological material but the resulting cryotomograms are extremely noisy. Sophisticated denoising techniques are thus essential for allowing the visualization and interpretation of the information contained in the cryotomograms. Here a software tool based on anisotropic nonlinear diffusion is described for filtering cryotomograms. The approach reduces local noise and meanwhile enhances both curvilinear and planar structures. In the program a novel solution of the partial differential equation has been implemented, which allows a reliable estimation of derivatives and, furthermore, reduces computation time and memory requirements. Several criteria have been included to automatically select the optimal stopping time. The behaviour of the denoising approach is tested for visualizing filamentous structures in cryotomograms.     

An Efficient Augmented Lagrangian Method for Statistical X-Ray CT Image Reconstruction

Statistical iterative reconstruction (SIR) for X-ray computed tomography (CT) under the penalized weighted least-squares criteria can yield significant gains over conventional analytical reconstruction from the noisy measurement. However, due to the nonlinear expression of the objective function, most exiting algorithms related to the SIR unavoidably suffer from heavy computation load and slow convergence rate, especially when an edge-preserving or sparsity-based penalty or regularization is incorporated. In this work, to address abovementioned issues of the general algorithms related to the SIR, we propose an adaptive nonmonotone alternating direction algorithm in the framework of augmented Lagrangian multiplier method, which is termed as “ALM-ANAD”. The algorithm effectively combines an alternating direction technique with an adaptive nonmonotone line search to minimize the augmented Lagrangian function at each iteration. To evaluate the present ALM-ANAD algorithm, both qualitative and quantitative studies were conducted by using digital and physical phantoms. Experimental results show that the present ALM-ANAD algorithm can achieve noticeable gains over the classical nonlinear conjugate gradient algorithm and state-of-the-art split Bregman algorithm in terms of noise reduction, contrast-to-noise ratio, convergence rate, and universal quality index metrics.     

Energy cost evaluation of parallel algorithms for multiprocessor systems

With the continuous development of hardware and software, Graphics Processor Units (GPUs) have been used in the general-purpose computation field. They have emerged as a computational accelerator that dramatically reduces the application execution time with CPUs. To achieve high computing performance, a GPU typically includes hundreds of computing units. The high density of computing resource on a chip brings in high power consumption. Therefore power consumption has become one of the most important problems for the development of GPUs. This paper analyzes the energy consumption of parallel algorithms executed in GPUs and provides a method to evaluate the energy scalability for parallel algorithms. Then the parallel prefix sum is analyzed to illustrate the method for the energy conservation, and the energy scalability is experimentally evaluated using Sparse Matrix-Vector Multiply (SpMV). The results show that the optimal number of blocks, memory choice and task scheduling are the important keys to balance the performance and the energy consumption of GPUs.     

Efficiency of Parallel Direct Optimization

Tremendous progress has been made at the level of sequential computation in phylogenetics. However, little attention has been paid to parallel computation. Parallel computing is particularly suited to phylogenetics because of the many ways large computational problems can be broken into parts that can be analyzed concurrently. In this paper, we investigate the scaling factors and efficiency of random addition and tree refinement strategies using the direct optimization software, POY, on a small (10 slave processors) and a large (256 slave processors) cluster of networked PCs running LINUX. These algorithms were tested on several data sets composed of DNA and morphology ranging from 40 to 500 taxa. Various algorithms in POY show fundamentally different properties within and between clusters. All algorithms are efficient on the small cluster for the 40-taxon data set. On the large cluster, multibuilding exhibits excellent parallel efficiency, whereas parallel building is inefficient. These results are independent of data set size. Branch swapping in parallel shows excellent speed-up for 16 slave processors on the large cluster. However, there is no appreciable speed-up for branch swapping with the further addition of slave processors (>16). This result is independent of data set size. Ratcheting in parallel is efficient with the addition of up to 32 processors in the large cluster. This result is independent of data set size.     

Performance improvements for iterative electron tomography reconstruction using graphics processing units (GPUs)

Iterative reconstruction algorithms are becoming increasingly important in electron tomography of biological samples. These algorithms, however, impose major computational demands. Parallelization must be employed to maintain acceptable running times. Graphics Processing Units (GPUs) have been demonstrated to be highly cost-effective for carrying out these computations with a high degree of parallelism. In a recent paper by Xu et al. (2010), a GPU implementation strategy was presented that obtains a speedup of an order of magnitude over a previously proposed GPU-based electron tomography implementation. In this technical note, we demonstrate that by making alternative design decisions in the GPU implementation, an additional speedup can be obtained, again of an order of magnitude. By carefully considering memory access locality when dividing the workload among blocks of threads, the GPU’s cache is used more efficiently, making more effective use of the available memory bandwidth.     

Computational methods for protein identification from mass spectrometry data

Protein identification using mass spectrometry is an indispensable computational tool in the life sciences. A dramatic increase in the use of proteomic strategies to understand the biology of living systems generates an ongoing need for more effective, efficient, and accurate computational methods for protein identification. A wide range of computational methods, each with various implementations, are available to complement different proteomic approaches. A solid knowledge of the range of algorithms available and, more critically, the accuracy and effectiveness of these techniques is essential to ensure as many of the proteins as possible, within any particular experiment, are correctly identified. Here, we undertake a systematic review of the currently available methods and algorithms for interpreting, managing, and analyzing biological data associated with protein identification. We summarize the advances in computational solutions as they have responded to corresponding advances in mass spectrometry hardware. The evolution of scoring algorithms and metrics for automated protein identification are also discussed with a focus on the relative performance of different techniques. We also consider the relative advantages and limitations of different techniques in particular biological contexts. Finally, we present our perspective on future developments in the area of computational protein identification by considering the most recent literature on new and promising approaches to the problem as well as identifying areas yet to be explored and the potential application of methods from other areas of computational biology.     

Parallel Markov chain Monte Carlo - bridging the gap to high-performance Bayesian computation in animal breeding and genetics

Background

Most Bayesian models for the analysis of complex traits are not analytically tractable and inferences are based on computationally intensive techniques. This is true of Bayesian models for genome-enabled selection, which uses whole-genome molecular data to predict the genetic merit of candidate animals for breeding purposes. In this regard, parallel computing can overcome the bottlenecks that can arise from series computing. Hence, a major goal of the present study is to bridge the gap to high-performance Bayesian computation in the context of animal breeding and genetics.

Results

Parallel Monte Carlo Markov chain algorithms and strategies are described in the context of animal breeding and genetics. Parallel Monte Carlo algorithms are introduced as a starting point including their applications to computing single-parameter and certain multiple-parameter models. Then, two basic approaches for parallel Markov chain Monte Carlo are described: one aims at parallelization within a single chain; the other is based on running multiple chains, yet some variants are discussed as well. Features and strategies of the parallel Markov chain Monte Carlo are illustrated using real data, including a large beef cattle dataset with 50K SNP genotypes.

Conclusions

Parallel Markov chain Monte Carlo algorithms are useful for computing complex Bayesian models, which does not only lead to a dramatic speedup in computing but can also be used to optimize model parameters in complex Bayesian models. Hence, we anticipate that use of parallel Markov chain Monte Carlo will have a profound impact on revolutionizing the computational tools for genomic selection programs.     

FPGA accelerator for protein secondary structure prediction based on the GOR algorithm

Background

Protein is an important molecule that performs a wide range of functions in biological systems. Recently, the protein folding attracts much more attention since the function of protein can be generally derived from its molecular structure. The GOR algorithm is one of the most successful computational methods and has been widely used as an efficient analysis tool to predict secondary structure from protein sequence. However, the execution time is still intolerable with the steep growth in protein database. Recently, FPGA chips have emerged as one promising application accelerator to accelerate bioinformatics algorithms by exploiting fine-grained custom design.

Results

In this paper, we propose a complete fine-grained parallel hardware implementation on FPGA to accelerate the GOR-IV package for 2D protein structure prediction. To improve computing efficiency, we partition the parameter table into small segments and access them in parallel. We aggressively exploit data reuse schemes to minimize the need for loading data from external memory. The whole computation structure is carefully pipelined to overlap the sequence loading, computing and back-writing operations as much as possible. We implemented a complete GOR desktop system based on an FPGA chip XC5VLX330.

Conclusions

The experimental results show a speedup factor of more than 430x over the original GOR-IV version and 110x speedup over the optimized version with multi-thread SIMD implementation running on a PC platform with AMD Phenom 9650 Quad CPU for 2D protein structure prediction. However, the power consumption is only about 30% of that of current general-propose CPUs.