STRALCP - Structure Alignment-based Clustering of Proteins

Adam Zemla¹, Brian Geisbrecht², Jason Smith¹, Marisa Lam¹, Bonnie Kirkpatrick¹, Mark Wagner¹, Tom Slezak¹ and Carol Ecale Zhou¹

¹Computing Applications and Research, Lawrence Livermore National Laboratory, Livermore, CA 94550 USA and ²Division of Cell Biology and Biophysics, University of Missouri-Kansas City, Kansas City, MO 64110 USA

 

*ABSTRACT

Protein structural annotation and classification is an important and challenging problem in bioinformatics. Research towards analysis of sequence–structure correspondences is critical for better understanding of a protein's structure, function, and its interaction with other molecules. Clustering of protein domains based on their structural similarities provides valuable information for protein classification schemes. In this article, we attempt to determine whether structure information alone is sufficient to adequately classify protein structures. We present an algorithm that identifies regions of structural similarity within a given set of protein structures, and uses those regions for clustering. In our approach, called STRALCP (STRucture ALignment-based Clustering of Proteins), we generate detailed information about global and local similarities between pairs of protein structures, identify fragments (spans) that are structurally conserved among proteins, and use these spans to group the structures accordingly. We also provide a web server at http://as2ts.llnl.gov/AS2TS/STRALCP/ for selecting protein structures, calculating structurally conserved regions and performing automated clustering.

 

Benchmark results
(supplemental results posted on STRALCP web page)

 

 

In our benchmark test – comparison with SCOP classification, we have performed STRALCP calculations for 4,620 SCOP domains classified within 25 different folds (see Table 1). Our clustering method is robust in that it detects relationships at the family level with good agreement with the manually maintained SCOP database.

In order to evaluate the accuracy of our clustering approach, we estimated the differences between SCOP (ver. 1.71) and STRALCP clustering (for example on the level of SCOP families) by introducing the following measure. Let:

·        Nc - the number of created clusters,

·        Cf(i) - the number of different families clustered together within the i cluster,

The score indicating the misclustering effect MC (when domains from different SCOP families are grouped together) can be calculated from the formula:

The range of this measure is 0.0 <= MC < 100.0, where 0.0 indicates no misclustering (i.e., agreement with SCOP families separation).

 

Table 1. Results from the evaluation of the differences between SCOP (ver. 1.71) and STRALCP clusters at the level of SCOP families. Here Nd – number of domains within the fold, Ns – number of superfamilies, Nf – number of families, Nc – number of created clusters, MC – misclustering effect calculated by the introduced formula.

 

The MC measure allows the comparison of different clustering schemes by their agreement in separating proteins from different clusters. The goal of this measure is not to calculate how many domains are clustered differently, but of how many the created clusters are compromised (merge proteins that are separated in other clustering scheme). In Table 1 we show the results from applying MC formula to the clusters calculated on selected set of 25 SCOP folds. In our selection of 25 SCOP folds we required that they consist of multiple superfamilies (at least 4). In total, in this benchmark test we have analyzed Nd=4,620 domains from Nf=343 SCOP families, and Ns=243 superfamilies.

Fold: a.5      List      LGA_summary      Clustering
Fold: a.7      List      LGA_summary      Clustering
Fold: a.8      List      LGA_summary      Clustering
Fold: a.24     List      LGA_summary      Clustering
Fold: a.29     List      LGA_summary      Clustering
Fold: a.137    List      LGA_summary      Clustering
Fold: b.2      List      LGA_summary      Clustering
Fold: b.42     List      LGA_summary      Clustering
Fold: b.43     List      LGA_summary      Clustering
Fold: b.68     List      LGA_summary      Clustering
Fold: b.80     List      LGA_summary      Clustering
Fold: b.85     List      LGA_summary      Clustering
Fold: c.8      List      LGA_summary      Clustering
Fold: c.51     List      LGA_summary      Clustering
Fold: c.56     List      LGA_summary      Clustering
Fold: d.52     List      LGA_summary      Clustering
Fold: d.68     List      LGA_summary      Clustering
Fold: d.79     List      LGA_summary      Clustering
Fold: d.110    List      LGA_summary      Clustering
Fold: d.129    List      LGA_summary      Clustering
Fold: f.1      List      LGA_summary      Clustering
Fold: f.4      List      LGA_summary      Clustering
Fold: f.23     List      LGA_summary      Clustering
Fold: g.41     List      LGA_summary      Clustering
Fold: h.4      List      LGA_summary      Clustering