The iterative helical real space reconstruction method: surmounting the problems posed by real polymers

Many important biological macromolecules exist as helical polymers. Examples are actin, tubulin, myosin, RecA, Rad51, flagellin, pili, and filamentous bacteriophage. The first application of three-dimensional reconstruction from electron microscopic images was to a helical polymer, and a number of laboratories today are using helical tubes of integral membrane proteins for solving the structure of these proteins in the electron microscope at near atomic resolution. We have developed a method to analyze and reconstruct electron microscopic images of macromolecular helical polymers, the iterative helical real space reconstruction (IHRSR) algorithm. We can show that when there is disorder or heterogeneity, when the specimens diffract weakly, or when Bessel functions overlap, we can do far better with our method than can be done using traditional Fourier-Bessel approaches. In many cases, structures that were not even amenable to analysis can be solved at fairly high resolution using our method. The problems inherent in the traditional approach are discussed, and examples are presented illustrating how the IHRSR approach surmounts these problems.     

An iterative refinement algorithm for consistency based multiple structural alignment methods

MOTIVATION: Multiple STructural Alignment (MSTA) provides valuable information for solving problems such as fold recognition. The consistency-based approach tries to find conflict-free subsets of alignments from a pre-computed all-to-all Pairwise Alignment Library (PAL). If large proportions of conflicts exist in the library, consistency can be hard to get. On the other hand, multiple structural superposition has been used in many MSTA methods to refine alignments. However, multiple structural superposition is dependent on alignments, and a superposition generated based on erroneous alignments is not guaranteed to be the optimal superposition. Correcting errors after making errors is not as good as avoiding errors from the beginning. Hence it is important to refine the pairwise library to reduce the number of conflicts before any consistency-based assembly. RESULTS: We present an algorithm, Iterative Refinement of Induced Structural alignment (IRIS), to refine the PAL. A new measurement for the consistency of a library is also proposed. Experiments show that our algorithm can greatly improve T-COFFEE performance for less consistent pairwise alignment libraries. The final multiple alignment outperforms most state-of-the-art MSTA algorithms at assembling 15 transglycosidases. Results on three other benchmarks showed that the algorithm consistently improves multiple alignment performance. AVAILABILITY: The C++ code of the algorithm is available upon request.     

Application of the iterative helical real-space reconstruction method to large membranous tubular crystals of P-type ATPases

Since the development of three-dimensional helical reconstruction methods in the 1960's, advances in Fourier-Bessel methods have facilitated structure determination to near-atomic resolution. A recently developed iterative helical real-space reconstruction (IHRSR) method provides an alternative that uses single-particle analysis in conjunction with the imposition of helical symmetry. In this work, we have adapted the IHRSR algorithm to work with frozen-hydrated tubular crystals of P-type ATPases. In particular, we have implemented layer-line filtering to improve the signal-to-noise ratio, Wiener-filtering to compensate for the contrast transfer function, solvent flattening to improve reference reconstructions, out-of-plane tilt compensation to deal with flexibility in three dimensions, systematic calculation of Fourier shell correlations to track the progress of the refinement, and tools to control parameters as the refinement progresses. We have tested this procedure on datasets from Na(+)/K(+)-ATPase, rabbit skeletal Ca(2+)-ATPase and scallop Ca(2+)-ATPase in order to evaluate the potential for sub-nanometer resolution as well as the robustness in the presence of disorder. We found that Fourier-Bessel methods perform better for well-ordered samples of skeletal Ca(2+)-ATPase and Na(+)/K(+)-ATPase, although improvements to IHRSR are discussed that should reduce this disparity. On the other hand, IHRSR was very effective for scallop Ca(2+)-ATPase, which was too disordered to analyze by Fourier-Bessel methods.     

An iterative network partition algorithm for accurate identification of dense network modules

A key step in network analysis is to partition a complex network into dense modules. Currently, modularity is one of the most popular benefit functions used to partition network modules. However, recent studies suggested that it has an inherent limitation in detecting dense network modules. In this study, we observed that despite the limitation, modularity has the advantage of preserving the primary network structure of the undetected modules. Thus, we have developed a simple iterative Network Partition (iNP) algorithm to partition a network. The iNP algorithm provides a general framework in which any modularity-based algorithm can be implemented in the network partition step. Here, we tested iNP with three modularity-based algorithms: multi-step greedy (MSG), spectral clustering and Qcut. Compared with the original three methods, iNP achieved a significant improvement in the quality of network partition in a benchmark study with simulated networks, identified more modules with significantly better enrichment of functionally related genes in both yeast protein complex network and breast cancer gene co-expression network, and discovered more cancer-specific modules in the cancer gene co-expression network. As such, iNP should have a broad application as a general method to assist in the analysis of biological networks.     

An algorithm for comparing multiple RNA secondary structures

A new distributed computational procedure is presented for rapidlydetermining the similarity of multiple conformations of RNAsecondary structures. A data abstraction scheme is utilizedto reduce the quantity of data that must be handled to determinethe degree of similarity among multiple structures. The methodhas been used to compare 200 structures with easy visualizationof both those structures and substructures that are similarand those that are vastly different. It has the capability ofprocessing many more conformations as a function of researchrequirements. The algorithm is described as well as some suggestionsfor future uses and extensions. Received on October 29, 1987; accepted on May 4, 1988     

MM-align: a quick algorithm for aligning multiple-chain protein complex structures using iterative dynamic programming

Structural comparison of multiple-chain protein complexes is essential in many studies of protein–protein interactions. We develop a new algorithm, MM-align, for sequence-independent alignment of protein complex structures. The algorithm is built on a heuristic iteration of a modified Needleman–Wunsch dynamic programming (DP) algorithm, with the alignment score specified by the inter-complex residue distances. The multiple chains in each complex are first joined, in every possible order, and then simultaneously aligned with cross-chain alignments prevented. The alignments of interface residues are enhanced by an interface-specific weighting factor. MM-align is tested on a large-scale benchmark set of 205 × 3897 non-homologous multiple-chain complex pairs. Compared with a naïve extension of the monomer alignment program of TM-align, the alignment accuracy of MM-align is significantly higher as judged by the average TM-score of the physically-aligned residues. MM-align is about two times faster than TM-align because of omitting the cross-alignment zone of the DP matrix. It also shows that the enhanced alignment of the interfaces helps in identifying biologically relevant protein complex pairs.     

An electrostatic spatial resonance model for coaxial helical structures with applications to the filamentous bacteriophages.

A model is presented that treats the symmetry matching problem in structures made of two interacting coaxial helices of point charges. The charges are sources of a potential field that mediates a non-specific attractive interaction between the helices. The problem is represented in Fourier space, which affords the most generality. It is found that coaxial helices with optimally mated symmetries can lock into spatial resonance configurations that maximize their interaction. The resonances are represented as vectors in a discrete three-dimensional space. Two algebraic relations are given for the four symmetry parameters of two helices in resonance. One-start inner helices interacting with coaxial one-start or NR-start outer helices are considered. Applications are made to the filamentous bacteriophages Ff, Pf1, Xf, and Pf3. The interaction given by the linearized Poisson-Boltzmann equation is calculated in this formalism to allow comparison of the electrostatic free energy of interaction of different resonance structures. Experimental nucleotide/subunit ratios are accounted for, and models for the DNA-protein interfaces are presented, with particular emphasis on Pf1.     

Assessment of homology with the helical mimicry algorithm

Homologies based on structural motifs characterize conserved structures and mechanisms of maintaining function. An algorithm was developed to quantitate homology among segments of two proteins based upon structural characteristics of an amphipathic α-helix. This helical mimicry algorithm scored homology among sequences of two proteins in terms of: (i) presence of Leu, Ile, Val, Phe, or Met in a longitudinal, hydrophobic strip-of-helix at positions n, n + 4, n + 7, n + 11, etc. in the primary sequence, (ii) identity or chemical similarity of amino acids at intervening positions and (iii) exchanges of amino acids from positions n to n − 1, n + 3, n + 4, n + 1, n − 3, n − 4 around n (on the surface of a putative helix). While such exchanges of amino acids on the surfaces of homologous helices may conserve function, they did not maintain specific interactions of those residues with apposing groups.     

An APD-based iterative reconstruction method for simultaneous technetium-99m/iodine-123 SPECT imaging

Dual-isotope SPECT (DI-SPECT) studies offer significant advantages over sequential scans, foremost among them faster acquisition and perfect image registration. However, reconstructed images may be affected by substantial cross-talk contamination rendering them inadequate for diagnosis. This effect is especially strong for isotopes with close photopeak energies, such as ^99mTc (140 keV) and ¹²³I (159 keV). In this paper we present an iterative DI-SPECT reconstruction method which includes accurate, analytically computed scatter corrections provided by the APD (analytical photon distribution) algorithm. This algorithm calculates first and second order Compton scatter (based on the Klein–Nishina formula) and first order Rayleigh scatter. Both self-scatter and cross-talk between the two isotopes are evaluated using patient specific attenuation maps and an initial activity distribution estimate. To validate our method we performed experiments using the Data Spectrum, Inc. thorax phantom and a SPECT/CT camera system. Reconstructed images demonstrate significant improvement in data quantitation. Their quantitative accuracy increases up to a factor of two, even for activity ratios which strongly enhance cross-talk effects and seriously degrade projections.     

Phasing statistics for alpha helical membrane protein structures

In this report we highlight the latest trends in phasing methods used to solve alpha helical membrane protein structures and analyze the use of heavy atom metals for the purpose of experimental phasing. Our results reveal that molecular replacement is emerging as the most successful method for phasing alpha helical membrane proteins, with the notable exception of the transporter family, where experimentally derived phase information still remains the most effective method. To facilitate selection of heavy atoms salts for experimental phasing an analysis of these was undertaken and indicates that organic mercury salts are still the most successful heavy atoms reagents. Interestingly the use of seleno‐l ‐methionine incorporated protein has increased since earlier studies into membrane protein phasing, so too the use of SAD and MAD as techniques for phase determination. Taken together this study provides a brief snapshot of phasing methods for alpha helical membrane proteins and suggests possible routes for heavy atom selection and phasing methods based on currently available data.     

A novel dual-axis iterative algorithm for electron tomography

A new algorithm for computing electron microscopy tomograms which combines iterative methods with dual-axis geometry is presented. Initial modelling using test data shows several improvements over both the weighted back-projection and simultaneous iterative reconstruction technique methods, with increased stability and tomogram fidelity under high-noise conditions. Preliminary experimental dual-axis reconstructions confirm the viability of the new algorithm.     

Refining the structure of the Halobacterium salinarum flagellar filament using the iterative helical real space reconstruction method: insights into polymorphism

The eubacterial flagellar filament is an external, self-assembling, helical polymer approximately 220 A in diameter constructed from a highly conserved monomer, flagellin, which polymerizes externally at the distal end. The archaeal filament is only approximately 100 A in diameter, assembles at the proximal end and is constructed from different, glycosylated flagellins. Although the phenomenology of swimming is similar to that of eubacteria, the symmetry of the archebacterial filament is entirely different. Here, we extend our previous study on the flagellar coiled filament structure of strain R1M1 of Halobacterium salinarum. We use strain M175 of H.salinarum, which forms poly-flagellar bundles at high yield which, under conditions of relatively low ionic-strength (0.8 M versus 5 M) and low pH ( approximately 2.5 versus approximately 6.8), form straight filaments. We demonstrated previously that a single-particle approach to helical reconstruction has many advantages over conventional Fourier-Bessel methods when dealing with variable helical symmetry and heterogeneity. We show here that when this method is applied to the ordered helical structure of the archebacterial uncoiled flagellar filament, significant extensions in resolution can be obtained readily when compared to applying traditional helical techniques. The filament population can be separated into classes of different morphologies, which may represent polymorphic states. Using cryo-negatively stained images, a resolution of approximately 10-15 A has been achieved. Single alpha-helices can be fit into the reconstruction, supporting the proposed similarity of the structure to that of type IV bacterial pili.     

Single-particle reconstruction from EM images of helical filaments

Helical filaments were the first structures to be reconstructed in three dimensions from electron microscopic images, and continue to be extensively studied due to the large number of such helical polymers found in biology. In principle, a single image of a helical polymer provides all of the different projections needed to reconstruct the three-dimensional structure. Unfortunately, many helical filaments have been refractory to the application of traditional (Fourier-Bessel) methods due to variability, heterogeneity, and weak scattering. Over the past several years, many of these problems have been surmounted using single-particle type approaches that can do substantially better than Fourier-Bessel approaches. Applications of these new methods to viruses, actin filaments, pili and many other polymers show the great advantages of the new methods.     

A reduction-based exact algorithm for the contact map overlap problem.

Aligning proteins based on their structural similarity is a fundamental problem in molecular biology with applications in many settings, including structure classification, database search, function prediction, and assessment of folding prediction methods. Structural alignment can be done via several methods, including contact map overlap (CMO) maximization that aligns proteins in a way that maximizes the number of common residue contacts. In this paper, we develop a reduction-based exact algorithm for the CMO problem. Our approach solves CMO directly rather than after transformation to other combinatorial optimization problems. We exploit the mathematical structure of the problem in order to develop a number of efficient lower bounding, upper bounding, and reduction schemes. Computational experiments demonstrate that our algorithm runs significantly faster than existing exact algorithms and solves some hard CMO instances that were not solved in the past. In addition, the algorithm produces protein clusters that are in excellent agreement with the SCOP classification. An implementation of our algorithm is accessible as an on-line server at http://eudoxus.scs.uiuc.edu/cmos/cmos.html.