a need for computational methods to match, compare and dock such structures. We present here tools designed for low-to-low resolution matching and docking. By extending and smoothing of the surfaces of the objects our matching procedure FitEM2EMIN becomes resolution independent allowing comparison or fitting of objects obtained at very different resolutions without resorting to resolution modification. Such modification (that is often used in fitting of atomic structures into EM maps) requires knowledge of the target resolution, the experimental determination of which is susceptible to inaccuracies, especially in low resolution studies [38]. We show that FitEM2EMIN can match different conformers and fit a partial structure into a larger assembly. The procedure is not sensitive to the exact values of the parameters and ranges of w confer identification of correct and nearly correct matches and distinction from false matches. Similarly, small changes in the EM maps density cutoff affect the complementarity score but not the relative position of the matched objects or the rank of the correct match. The success rate of FitEM2EMIN is excellent. Thus, in every case correct matches are obtained at the top. We attribute this success to the limited search volume (the interior plus surface of object A), which allows only few matches with positive scores. When substructures are matched into the whole structure the search volume increases considerably and the results become more similar to docking results. Thus, the number of false models obtained in the partial matching tests 80S/40S and GroES-ATP7- GroEL/GroES-ATP7-(single-ring)GroEL is higher than in most other tested cases (see Table 2). Nevertheless the difference between the scores of the correct match (top rank) and the highest ranked false match is large, facilitating distinction between them. The DifferenceGrid tool highlights major structural differences between the matched objects. In the partial docking of the 40S ribosomal subunit into the 80S ribosome this tool can be used to predict the size and shape of the 60S ribosomal subunit. Docking is expected to produce weaker distinction between correct and false models than matching because the search space is much less limited. Nevertheless, our procedure FitEM2EMOUT ranked the expected docking models at the top with considerable score gap from that of the highest ranked false models. The procedures presented here can also be used for matching of atomic resolution structures to EM maps because the large grid effectively lowers the resolution of the atomic representation of an object. In this study the electron density values were used only for determining the shape of the matched or docked objects. These values can however be used to guide the matching or docking, for example by requiring that high density regions, that may represent RNA or DNA regions, overlap. The guiding can be achieved in a similar manner to the weighting procedure previously described by our group [39]. Notably, such guided matching or docking can use experimental data regarding the positions of substructures or specific interactions, from different sources. Methods Converting EM maps into easily rotateable 3D objects EM maps are given as 3D grids of electron density values and the objects are visualized by selecting one or more density cutoffs and drawing equi-density contours. Every EM grid point with density exceeding a selected cutoff value was listed as a virtual atom whose coordinates are those of the grid point and whose radius is !3G/2, where G is the EM grid interval (this representation is similar to the virtual atoms representation of the electrostatic potential by Heifetz et al. [40]). The virtual atoms thus fill the volume delimited by the selected equi-density contour. Matching & Docking EM Maps Each virtual atom is assigned the density value of the related grid point and in this way the selected part of the EM map can be easily rotated and shifted to various positions. FitEM2EMIN – a tool for matching low resolution 3D structures The FitEM2EMIN algorithm is based on the FFT docking procedure, MolFit, initially described by Katchalski-Katzir and coworkers [23]. The objects to be matched are represented by cubic grids. The center of the grid is at the centroid of the object and grid points are assigned values with regard to their position relative to the object. Grid points within the volume of any virtual atom are considered part of the object (interior or surface); other grid points are assigned ‘‘outside the object’’ values. Distinction between the interior and a surface layer is made for the stationary object A. The resultant grid representations are as follows: Object A (the stationary object): Al,m,n~ 8 r > < s >: Oa inside the object on the surf ace of the object outside the object Object B (the moving object): 8 s > < Bl,m,n~ s >: Ob inside the object on the surf ace of the object outside the object The grid representations are correlated using FFT, producing the matrix Ca,b,c (eq. 1). C holds the correlation scores for shifts of Bl,m,n with respect to Al,m,n by a, b, and c grid points along three perpendicular axes. Ca,b,c~Al,m,n6Blza,mzb,nzc 1 ð Þ By setting Oa to a negative value, s to a positive value and r and Ob to zero, the correlation scores are positive when object B is positioned within the volume of object A and overlaps its surface layer. The correlation scores reflect the degree of surface similarity between objects A and B thus higher positive scores indicate more extensive matching of the surfaces and little or no protrusion of object B outside of the volume of object A. The n highest scoring a, b, c shifts in the current correlation matrix are identified and saved. To complete a six dimensional search in the rotation-translation space the moving object is rotated to a new orientation (by applying a rotation transformation to the coordinates of the virtual atoms), its grid representation is recalculated for the new orientation, and then a new correlation matrix is calculated and new high scoring positions are identified and saved. The procedure is repeated until the stepwise rotational scan is completed and then all the saved models are sorted by their correlation scores. The surface of object A consists of at least 2 layers of voxels; it was designed such that the inner layer follows the shape of the EM object (at the selected density cutoff) and the outer layer is extended and smoothed. The extension and smoothing are achieved by increasing the virtual atoms radii to (!3/2+w)g, where g is the FitEM2EMIN grid interval and w is a free parameter. A larger value of w produces a more extended and smoother outer PLoS ONE | www.plosone.org 6 October 2008 | Volume 3 | Issue 10 | e3594