Optimal 3D angular sampling with applications to cryo-EM problems.

The goal of cryo-EM experiments in the biological sciences is to determine the atomic structure of a molecule and deduce insights into its functions and mechanisms. Despite improvements in instrumentation for data collection and new software algorithms, in most cases, individual atoms are not resolved. Model building of proteins, nucleic acids, or molecules in general, is feasible from the experimentally determined density maps at resolutions up to the range of 3-4 Angstroms. For lower-resolution maps or parts of maps, fitting smaller structures obtained by modelling or experimental techniques with higher resolution is a way to resolve the issue. In practice, we have an atomic structure, generate its density map at a given resolution, and translate/rotate the map within a region of interest in the experimental map, computing a measure-of-fit score with the corresponding areas of the experimental map. This procedure is computationally intensive since we work in 6D space. An optimal ordered list of rotations will reduce the angular error and help to find the best-fitting positions faster for a coarse global search or a local refinement. It can be used for adaptive approaches to stop fitting algorithms earlier once the desired accuracy has been achieved. We demonstrate how the performance of some fitting algorithms can be improved by grouping sets of rotations. We present an approach to generate more efficient 3D angular sampling, and provide the computer code to generate lists of optimal orientations for single and grouped rotations and the lists themselves.

PerFSeeB: designing long high-weight single spaced seeds for full sensitivity alignment with a given number of mismatches.

BACKGROUND: Technical progress in computational hardware allows researchers to use new approaches for sequence alignment problems. For a given sequence, we usually use smaller subsequences (anchors) to find possible candidate positions within a reference sequence. We may create pairs ("position", "subsequence") for the reference sequence and keep all such records without compression, even on a budget computer. As sequences for new and reference genomes differ, the goal is to find anchors, so we tolerate differences and keep the number of candidate positions with the same anchors to a minimum. Spaced seeds (masks ignoring symbols at specific locations) are a way to approach the task. An ideal (full sensitivity) spaced seed should enable us to find all such positions subject to a given maximum number of mismatches permitted. RESULTS: Several algorithms to assist seed generation are presented. The first one finds all permitted spaced seeds iteratively. We observe specific patterns for the seeds of the highest weight. There are often periodic seeds with a simple relation between block size, length of the seed and read. The second algorithm produces blocks for periodic seeds for blocks of up to 50 symbols and up to nine mismatches. The third algorithm uses those lists to find spaced seeds for reads of an arbitrary length. Finally, we apply seeds to a real dataset and compare results for other popular seeds. CONCLUSIONS: PerFSeeB approach helps to significantly reduce the number of reads' possible alignment positions for a known number of mismatches. Lists of long, high-weight spaced seeds are available in Additional file 1. The seeds are best in weight compared to seeds from other papers and can usually be applied to shorter reads. Codes for all algorithms and periodic blocks can be found at https://github.com/vtman/PerFSeeB .

Theoretical and practical approaches to improve the performance of local correlation algorithms for volume data analysis and shape recognition.

In this paper, several approaches to be used to accelerate algorithms for fitting an atomic structure into a given 3D density map determined by cryo-EM are discussed. Rotation and translation of the atomic structure to find similarity scores are used and implemented with discrete Fourier transforms. Several rotations can be combined into groups to accelerate processing. The finite resolution of experimental and simulated maps allows a reduction in the number of rotations and translations needed in order to estimate similarity-score values.

Analytical formula for two-dimensional ring artefact suppression.

Ring artefacts are the most disturbing artefacts when reconstructed volumes are segmented. A lot of effort has already been put into better X-ray optics, scintillators and detectors in order to minimize the appearance of these artefacts. However, additional processing is often required after standard flat-field correction. Several methods exist to suppress artefacts. One group of methods is based on minimization of the Tikhonov functional. An analytical formula for processing of a single sinogram was developed. In this paper a similar approach is used and a formula for processing two-dimensional projections is found. Thus suppression of ring artefacts is organized as a two-dimensional convolution of `averaged' projections with a given filter. Several approaches are discussed in order to find elements of the filter in a faster and accurate way. Examples of experimental datasets processed by the proposed method are considered.

Suppression of ring artefacts when tomographing anisotropically attenuating samples.

There are many objects for which the attenuation varies significantly as they are rotated during computerized X-ray tomography, for example plate samples. This can lead to significant ring artefacts in the subsequent tomographic reconstructions. In this paper a new method is presented that can successfully suppress such ring artefacts and is applicable to both parallel and cone-beam geometries. Rapid correction is achieved via an analytical formula which involves only a matrix-vector multiplication, for which the matrix is known and depends on a regularization parameter. The efficacy of the method is demonstrated for a paleontological sample (calcified shark cartilage) and a carbon-carbon composite/Ti-SiC metal matrix composite test sample.

Improved tomographic reconstructions using adaptive time-dependent intensity normalization.

The first processing step in synchrotron-based micro-tomography is the normalization of the projection images against the background, also referred to as a white field. Owing to time-dependent variations in illumination and defects in detection sensitivity, the white field is different from the projection background. In this case standard normalization methods introduce ring and wave artefacts into the resulting three-dimensional reconstruction. In this paper the authors propose a new adaptive technique accounting for these variations and allowing one to obtain cleaner normalized data and to suppress ring and wave artefacts. The background is modelled by the product of two time-dependent terms representing the illumination and detection stages. These terms are written as unknown functions, one scaled and shifted along a fixed direction (describing the illumination term) and one translated by an unknown two-dimensional vector (describing the detection term). The proposed method is applied to two sets (a stem Salix variegata and a zebrafish Danio rerio) acquired at the parallel beam of the micro-tomography station 2-BM at the Advanced Photon Source showing significant reductions in both ring and wave artefacts. In principle the method could be used to correct for time-dependent phenomena that affect other tomographic imaging geometries such as cone beam laboratory X-ray computed tomography.

A priori information in a regularized sinogram-based method for removing ring artefacts in tomography.

Ring artefacts in X-ray computerized tomography reconstructions are considered. The authors propose a ring artefact removal method based on a priori information regarding the sinogram including smoothness along the horizontal coordinate, symmetry of the first and the final rows and consideration of small perturbations during acquisition. The method does not require prior reconstruction of the original or corrected sinograms. Its numerical implementation is based on quadratic programming. Its efficacy is examined with regard to experimental data sets collected on graphite and bone.