Enhanced fold recognition using efficient short fragment clustering

Abstract

The main structure aligner in the CCP4 Software Suite, SSM (Secondary Structure Matching) has a limited applicability on the intermediate stages of the structure solution process, when the secondary structure cannot be reliably computed due to structural incompleteness or a fragmented mainchain. In this study, we describe a new algorithm for the alignment and comparison of protein structures in CCP4, which was designed to overcome SSM's limitations but retain its quality and speed. The new algorithm, named GESAMT (General Efficient Structural Alignment of Macromolecular Targets), employs the old idea of deriving the global structure similarity from a promising set of locally similar short fragments, but uses a few technical solutions that make it considerably faster. A comparative sensitivity and selectivity analysis revealed an unexpected significant improvement in the fold recognition properties of the new algorithm, which also makes it useful for applications in the structural bioinformatics domain. The new tool is included in the CCP4 Software Suite starting from version 6.3.

Figure 1. Schematic of structure alignment process in GESAMT.

The left part of Figure 1 represents the fragment similarity matrix for the given chains A and B. Every short section in the matrix represents an SFS. SFSs with similar transformation matrices are collected into clusters, which after further refinement are brought to the common superposition matrix T₀.

Figure 2. Discrimination properties of selected structure alignment algorithms.

FATCAT-Rigid, FATCAT-Flexible (Ye & Godzik 2003), SSM (Krissinel & Henrick 2004) and GESAMT (present study) are compared. N(S) gives the probability of getting a score higher than S for dissimilar structures, P(S) corresponds to the probability of getting a score lower than S for similar structures. For FATCAT, S corresponds to the “raw” scores, contained in the FATCAT benchmark set. For SSM and GESAMT, the Q-score was used. Different-color curves correspond to similarity detected at various levels of SCOP hierarchy, as indicated in the figure.

Figure 3. Coverage vs. Error plots (Brenner et al. 1998) for selected structure alignment algorithms.

FATCAT-Rigid (green lines), FATCAT-Flexible (magenta lines), SSM (blue lines) and GESAMT in Normal (red lines) and High (black lines) mode are compared. The optimal discrimination scores from Table 2 were used as similarity thresholds. Different plots correspond to similarity detection at various levels of SCOP hierarchy, as indicated in the figure.

Figure 4. Comparison of Q-scores produced by SSM and GESAMT in Normal (left panel) and High (right panel) mode.

Each dot represents a pair of alignments, produced by SSM and GESAMT for the same protein pair from the benchmark set used.

Figure 5. Comparison of computation times used by SSM and GESAMT in Normal (left panel) and High (right panel) modes for individual alignments.

Each dot represents a pair of alignments, produced by SSM and GESAMT for the same protein pair from the benchmark set used. Total computation time used by SSM is 4,746 secs, GESAMT in Normal mode: 1,107 secs, GESAMT in High mode: 12,167 secs.

Figure 6. Correlation between computation time and product of chain lengths for SSM (red dots) and GESAMT (black dots).

Each dot represents a pair of alignments, produced by SSM and GESAMT for the same protein pair from the benchmark set used.