SUMMARY: We have developed a software tool to improve the image quality in focused ion beam-scanning electron microscopy (FIB-SEM) stacks: PolishEM. Based on a Gaussian blur model, it automatically estimates and compensates for the blur affecting each individual image. It also includes correction for artifacts commonly arising in FIB-SEM (e.g. curtaining). PolishEM has been optimized for an efficient processing of huge FIB-SEM stacks on standard computers. AVAILABILITY AND IMPLEMENTATION: PolishEM has been developed in C. GPL source code and binaries for Linux, OSX and Windows are available at http://www.cnb.csic.es/%7ejjfernandez/polishem. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Summary: TomoEED is an optimized software tool for fast feature-preserving noise filtering of large 3D tomographic volumes on CPUs and GPUs. The tool is based on the anisotropic nonlinear diffusion method. It has been developed with special emphasis in the reduction of the computational demands by using different strategies, from the algorithmic to the high performance computing perspectives. TomoEED manages to filter large volumes in a matter of minutes in standard computers. Availability and implementation: TomoEED has been developed in C. It is available for Linux platforms at http://www.cnb.csic.es/%7ejjfernandez/tomoeed. Supplementary information: Supplementary data are available at Bioinformatics online.

This work presents a hybrid computing approach which combines GPUs and multicore processors to fully take advantage of the computing power latent in modern computers. It also presents its application to the problem of tomographic reconstruction. One inherent characteristic of these modern platforms is their heterogeneity, which raises the issue of workload distribution among the different processing elements. Adaptive load balancing techniques are thus necessary to properly adjust the amount of work to be done by each computing element. Here, we have chosen the 'on-demand' strategy, a well-known technique in the HPC field by which the different elements asynchronously request a piece of work when they become idle, thereby keeping the system fairly well balanced. The results show that our scheme accommodates to the heterogeneous platform where it runs as it assigns more work to the faster processing elements automatically, which allows to correctly exploit all the resources available and to get complete reconstructions in less time than pure CPU or GPU approaches.

A wide range of applications in engineering and scientific computing are based on the computation of matrices products, where one of them is sparse. The computational requirements of these operations are very high when dimensions of the matrices increase. The goal of this work is the acceleration of the sparse matrix matrix product (SpMM) on Graphics Processing Units (GPUs). The operation SpMM can be computed by a set of sparse matrix vector operations (SpMV). However, this approach does not reach optimal performance because it cannot benefit from the large value of the ratio computation/memory access associated to the SpMM operation. In this work a routine called FastSpMM is described and its performance evaluated. FastSpMM can be considered as an extension of the ELLRT routine to compute SpMV on GPUs which is based on the ELLPACK-R storage format for sparse matrices. FastSpMM combines the high ratio computation/memory access with the advantages of ELLR-T to exploit the GPU architecture. The CUSPARSE library, supplied by NVIDIA, which also includes routines to compute SpMM on GPUs is used in this work as a reference for performance comparison. Experimental evaluations based on a representative set of test matrices show that FastSpMM outperforms the corresponding CUSPARSE routine in terms of performance.

Electron tomography (ET) allows elucidation of the three-dimensional (3D) structure of large complex biological specimens at molecular resolution. In order to achieve such resolution levels, large projection images have to be used to compute the 3D reconstructions. Tomographic reconstruction on this scale requires a tremendous use of computational resources and considerable processing time. Traditionally, parallel and distributed systems, and more recently GPUs, have been the key to cope with this demanding procedure. This work demonstrates that full exploitation of the impressive processing power within modern multi-core processors make them a feasible alternative. The use of parallel computing, vectorization and code optimization allows ultra-fast tomographic reconstructions on standard computers, even outperforming GPUs. Our results confirm that modern processors succeed in providing reconstructed volumes in very little time, which enables them for real-time ET.

Abstract Summary: Tomo3D implements a multithreaded vectorized approach to tomographic reconstruction that takes full advantage of the computer power in modern multicore computers. Full resolution tomograms are generated at high speed on standard computers with no special system requirements. Tomo3D has the most common reconstruction methods implemented, namely weighted Back-projection (WBP) and simultaneous iterative reconstruction technique (SIRT). It proves to be competitive with current graphic processor unit solutions in terms of processing time, in the order of a few seconds with WBP or minutes with SIRT. The program is compatible with standard packages, which easily allows integration in the electron tomography workflow. Availability: http://www.cnb.csic.es/%7ejjfernandez/tomo3d Contact: [email protected] Supplementary information: Supplementary data are available at Bioinformatics online.

Electron tomography (ET) is an important technique in biosciences that is providing new insights into the cellular ultrastructure. Iterative reconstruction methods have been shown to be robust against the noise and limited-tilt range conditions present in ET. Nevertheless, these methods are not extensively used due to their computational demands. Instead, the simpler method weighted backprojection (WBP) remains prevalent. Recently, we have demonstrated that a matrix approach to WBP allows a significant reduction in processing time both on central processing units and on graphics processing units (GPUs). In this work, we extend that matrix approach to one of the most common iterative methods in ET, simultaneous iterative reconstruction technique (SIRT). We show that it is possible to implement this method targeted at GPU directly, using sparse algebra. We also analyse this approach on different GPU platforms and confirm that these implementations exhibit high performance. This may thus help to the widespread use of SIRT.

Abstract The sparse matrix vector product (SpMV) is a key operation in engineering and scientific computing and, hence, it has been subjected to intense research for a long time. The irregular computations involved in SpMV make its optimization challenging. Therefore, enormous effort has been devoted to devise data formats to store the sparse matrix with the ultimate aim of maximizing the performance. Graphics Processing Units (GPUs) have recently emerged as platforms that yield outstanding acceleration factors. SpMV implementations for NVIDIA GPUs have already appeared on the scene. This work proposes and evaluates a new implementation of SpMV for NVIDIA GPUs based on a new format, ELLPACK‐R, that allows storage of the sparse matrix in a regular manner. A comparative evaluation against a variety of storage formats previously proposed has been carried out based on a representative set of test matrices. The results show that, although the performance strongly depends on the specific pattern of the matrix, the implementation based on ELLPACK‐R achieves higher overall performance. Moreover, a comparison with standard state‐of‐the‐art superscalar processors reveals that significant speedup factors are achieved with GPUs. Copyright © 2010 John Wiley & Sons, Ltd.

Electron tomography (ET) allows elucidation of the three-dimensional (3D) structure of large complex biological specimens at molecular resolution. In order to achieve such resolution levels, large projection images have to be used to compute the 3D reconstructions. Tomographic reconstruction on this scale requires a tremendous use of computational resources and a considerable processing time. In this work, we present and evaluate a highly optimized implementation of the Weighted Back-Projection reconstruction algorithm. Briefly, optimizations made to the code comprise (1) vector processing with SSE (Streaming SIMD Extensions) instructions, (2) an efficient use of cache memory, (3) to take advantage of the inherent image symmetry, (4) to use the FFTW (Fastest Fourier Transform in the West) library for image filtering, (5) to use regions of interest and last, but not least, (6) a wide range of minor optimizations like some data pre-calculations or an instruction level parallelism improvement. We have evaluated the method on tomographic reconstructions of several datasets and on two computing platforms. The results show that our version speeds up the method by a factor around 14 or 16, depending on the platform.

SUMMARY: Interpretation of electron tomograms is difficult due to the high noise levels. Thus, denoising techniques are needed to improve the signal-to-noise ratio. XMSF (Microscopy Mean Shift Filtering) is a fast, user-friendly application that succeeds in filtering noise while preserving the structures of interest. It is based on the extension to 3D of a method widely applied in other image processing fields under very different scenarios. XMSF has been tested for a variety of tomograms, showing a great potential to become a state-of-the-art filtering program in electron tomography. Applied iteratively, the algorithm yields pre-segmented volumes facilitating posterior segmentation tasks. Moreover, execution times remain low thanks to parallel computing techniques to exploit current multicore computers. AVAILABILITY: http://sites.google.com/site/xmsfilter/

BACKGROUND: Noise filtering techniques are needed in electron tomography to allow proper interpretation of datasets. The standard linear filtering techniques are characterized by a tradeoff between the amount of reduced noise and the blurring of the features of interest. On the other hand, sophisticated anisotropic nonlinear filtering techniques allow noise reduction with good preservation of structures. However, these techniques are computationally intensive and are difficult to be tuned to the problem at hand. RESULTS: TOMOBFLOW is a program for noise filtering with capabilities of preservation of biologically relevant information. It is an efficient implementation of the Beltrami flow, a nonlinear filtering method that locally tunes the strength of the smoothing according to an edge indicator based on geometry properties. The fact that this method does not have free parameters hard to be tuned makes TOMOBFLOW a user-friendly filtering program equipped with the power of diffusion-based filtering methods. Furthermore, TOMOBFLOW is provided with abilities to deal with different types and formats of images in order to make it useful for electron tomography in particular and bioimaging in general. CONCLUSION: TOMOBFLOW allows efficient noise filtering of bioimaging datasets with preservation of the features of interest, thereby yielding data better suited for post-processing, visualization and interpretation. It is available at the web site (http://www.ual.es/%7ejjfdez/SW/tomobflow.html).

A continuous location problem in which a firm wants to set up two or more new facilities in a competitive environment is considered. Other facilities offering the same product or service already exist in the area. Both the locations and the qualities of the new facilities are to be found so as to maximize the profit obtained by the firm. This is a global optimization problem, with many local optima. In this paper we analyze several approaches to solve it, namely, three multistart local search heuristics, a multistart simulated annealing algorithm, and two variants of an evolutionary algorithm. Through a comprehensive computational study it is shown that the evolutionary algorithms are the heuristics that provide the best solutions. Furthermore, using a set of problems for which the optimal solutions are known, only the evolutionary algorithms were able to find the optimal solutions for all the instances. The evolutionary strategies presented in this paper can be easily adapted to handle other continuous location problems.

Electron tomography allows elucidation of the three-dimensional (3D) structure of large complex biological specimens at molecular resolution. In order to achieve such resolution levels, large projection images have to be used to compute the 3D reconstructions. Tomographic reconstruction on this scale requires a tremendous use of computational resources and considerable processing time. In this work, we present and evaluate a vector approach for fast 3D reconstruction that takes advantage of the multimedia extensions in modern processors. We have implemented the standard 3D reconstruction method, weighted backprojection, using the Streaming SIMD Extensions (SSE). We have evaluated the method on tomographic reconstruction of several datasets of various sizes on a computing platform based on Intel Xeon processor. The results show that our approach speeds up the method by a factor of 3.

UNLABELLED: Electron tomography is the leading technique to elucidate the structure of complex biological specimens. Due to the resolution needs, huge reconstructions are required. Grid computing has the potential to face the significant computational demands involved. However, there are a number of key issues, such as stability or difficult user-grid interaction, that currently preclude fully exploitation of its potential. EGEETomo is a user-friendly application that facilitates the interaction with the grid for the non-specialized user and automates job submission and supervision. In addition, EGEETomo is supplied with an automated fault recovery mechanism, which is key to make all the work transparent to the user. EGEETomo significantly accelerates tomographic reconstruction by exploiting the computational resources in the EGEE grid with minimal user intervention. AVAILABILITY: http://www.ace.ual.es/~jrbcast/EGEETomo.tar.gz

This article describes and analyzes the parallelization of the Anisotropic Nonlinear Diffusion (AND) for filtering 3D images. AND is one of the most powerful denoising techniques in the field of computer vision. This technique consists in resolving the equation of diffusion tightly coupled with a massive set of eigensystems. Denoising large 3D images in biomedicine and structural cellular biology by AND has a high computational cost. In this work, we propose a portable and efficient parallel implementation of AND based on a hybrid paradigm that combines (1) the message passing model and (2)the shared address space model. The proposed parallel implementation has been evaluated on a cluster of SMPs based on a UMA Uniform Memory access. The evaluation results show that the hybrid model is more suitable for this kind of platforms.

Three-Dimensional Electron Microscopy (3DEM) has turned out to be a major player in structural proteomics. In 3DEM, tens of thousands of EM images from a macromolecule at different views are combined to derive its structure by means of a 3D reconstruction algorithm. However, for an optimal reconstruction, the most suitable algorithm has to be used and its parameters have to be tuned for the macromolecule under study and the experimental conditions found. The use of phantoms is central to objective comparison of reconstruction algorithms and optimization of their parameters. Phan3D is a tool intended to provide a fully visual and interactive environment that facilitates the design of phantoms resembling biological specimens in 3DEM. Phan3D has been developed as an alternative to the tedious, error-prone and old-fashioned phantom design that is based on hand-written text description files.

A new algorithm for three-dimensional reconstruction of two-dimensional crystals from projections is presented, and its applicability to biological macromolecules imaged using transmission electron microscopy (TEM) is investigated. Its main departures from the traditional approach is that it works in real space, rather than in Fourier space, and it is iterative. This has the advantage of making it convenient to introduce additional constraints (such as the support of the function to be reconstructed, which may be known from alternative measurements) and has the potential of more accurately modeling the TEM image formation process. Phantom experiments indicate the superiority of the new approach even without the introduction of constraints in addition to the projection data.

This work addresses the application of blob-based series expansion methods in structure determination of macromolecules from the perspective of computational speed and convergence rate. This work explores the use of traditional series expansion methods, such as algebraic reconstruction techniques, as well as other very recently developed methods: such as averaging sequential strings or component averaging methods characterized by a really fast convergence, achieving least-squares solutions in a few iterations.