most protein annotation and classification approaches depend heavily on the degree of observed amino acid sequence similarity to other related proteins .
but even when sequence similarity between two proteins is low , structure similarity can be high .
thus , one of the most important improvements in protein classification would be protein homology / analogy identification at very low levels of sequence similarity ( 1 ) . as redfern et al .
( 2 ) explain  despite the advances in sequence comparison methods , remote homologs in the  midnight zone  of sequence similarity ( < 15% identity ) described by rost , can still only be identified through protein structure comparison. redfern et al . also point out that  structure - based classifications are becoming increasingly important resources for recognizing these distant relatives and providing datasets for more far - reaching analyses of protein family evolution. in our research and development we follow these observations , and in order to detect the benefits and limitations of using purely structure - based approaches , we curently concentrated on structure similarity analyses only .
the protein data bank ( pdb ) ( 3 ) already contains more than 45 000 experimentally solved protein structures , and grows at a rate of more than 500 pdb entries per month . among current entries , approximately 40% are multi - domain proteins ( 2 ) and , thus , there have been several attempts to classify individual domains of pdb protein structures into defined clusters ( e.g. classes , folds , superfamilies , families ) based on structure similarity as measured by various criteria .
the most commonly used protein classification databases are scop ( 4 ) and cath ( 5 ) .
the structural classification of proteins ( scop ) database , a manual classification of pdb structures , is recognized by many as the gold standard of protein classification . in scop
clustering is based mainly on visual inspection of similarities between conformations of secondary structure elements and on sequence similarities
. however , scop classification lags the insertion of new structures in pdb , and manual classification can not scale to meet the demands of this rapidly growing dataset .
for example , clustering can be done by selecting a single metric ( e.g. z - score ( 6 ) used in fssp ( 7 ) dali fold classification ) or by combining different criteria to score the level of similarity , some examples of which are secondary structure content and orientation combined with calculated sequence similarities , and manual inspection , as used in the semiautomatic cath database .
depending on the algorithm , classification results may differ significantly if different criteria are used to assess the level of similarity between compared structures or if the clustering criteria are focused on different structural features .
the same set of proteins could be grouped differently by automatic sequence or structure comparison tools based on minor modifications to cutoffs or classification parameters .
the dali fold classification is based on exhaustive , all - against - all 3d structure comparisons of proteins from the pdb , and is constructed by average linkage clustering of the structural similarity score derived from calculated alignments of distance matrices .
the tree ( dendrogram ) is cut at dali z - score levels 2 , 4 , 8 , 16 , 32 and 64 , where the first level ( z > 2 ) can be used as an operational definition of folds .
a similar approach is used in ce ( 8) classification . after performing all - against - all comparisons of protein chains from the pdb , resulting ce z - score values of 4.5 and above
are used to discriminate at the family level , values between 4.0 and 4.5 at the superfamily and/or fold levels , and values between 3.5 and 4.0 are presumed to indicate possible biologically interesting similarities .
the authors of the struster ( 9 ) method explore the calculation of root mean square deviations ( rmsd ) and use their algorithm to cluster alternative structural models from the pdb ( i.e. models that correspond to different structure determination experiments ) .
in addition to the traditional rmsd measure , the struster method uses two filters to define the final scoring metric called dissimilarity measure m ( 9 ) .
these two filters are introduced in order to identify both large and small ( but significant ) backbone conformational changes by reducing the influence in local large distances ( only distances below 14.0  are considered ) and also to restrict the analysis to significant structural differences ( the distances above 1.0  ) .
an approach for structural comparisons , fundamentally different from those using rmsd , was proposed by rogen and fain ( 10 ) .
they introduced the sgm ( scaled gauss metric ) , which is a metric derived from knot theoretical ideas to cluster proteins according to their structural topologies .
they applied their method to predicting membership of proteins in cath and achieved 95% accuracy at all levels of the classification hierarchy . in order to achieve a high level of agreement with other clustering schemes , some algorithms that use a multi - criterion approach ( weighted combination of different scoring schemes ) ,
are initially trained on labeled data from an existing structural hierarchy ( scop or cath ) and use cross - validation ( or similar methods ) to select the best parameters for their classifiers .
for example , protclass ( 11 ) uses a nearest - neighbor - based classification scheme and several structural features to classify proteins at the fold level of the scop hierarchy .
their features include secondary structure elements predicted by the stride program ( 12 ) , the sequence length , and the percentage of observed helices .
scopmap ( 13 ) is an approach that achieves roughly 95% accuracy when classifying proteins into the superfamily level of the scop hierarchy .
this approach combines many existing protein sequence and structure comparison tools , including psi - blast ( 14 ) , mammoth ( 15 ) and dali ( 6 ) .
the classification results depend on the accuracy of the individual tools , so the authors use a variety of cutoffs and parameters optimized by training schemes to apply these tools in a specific order . in ref .
( 16 ) , the authors introduce a new structural representation of proteins to predict the family membership of proteins in the scop hierarchy .
they define a graph theoretic representation of protein structures with nodes being residues and edges connecting residues when the distance separating them falls below a specified cutoff . using these graphs as features , they train their support vector machine ( svm ) classifier with proteins from several scop families
. the ultimate goal of the work presented here was to define criteria and to develop an algorithm that for a given set of protein structures would automatically identify structurally conserved regions and use them to create clustering results similar to those that would be obtained by manual inspection ( e.g. scop curators ) . in our novel approach , called stralcp ( structure alignment - based clustering of proteins ) , for a given set of protein structures , we generate and combine detailed structural information about automatically detected global and local similarities between protein pairs , identify similar regions that are conserved within the set of proteins , report these regions , and use them to cluster the proteins according to their similarities in such identified structural frames .
we use the local - global alignment ( lga ) algorithm ( 17 ) to perform all necessary structure comparison calculations .
our algorithm starts from structure alignment calculations performed by lga ( with a default value of distance cutoff dist = 5  ) to determine de novo ( no sequence information is used ) residue  residue correspondences between compared proteins .
we use the lga_s measure as a scoring function to evaluate the overall level of structure similarity and to allow an initial grouping and structural clustering of proteins . in our stalcp approach ,
an optimal number of clusters is determined by grouping models according to their overall similarity ( lga_s ) combined with the information about local similarities in detected structurally conserved frames ( we call them
 spans ) . to perform a particular clustering for a set of protein structures , a suitable scoring function or , in general , a scoring algorithm that takes into account a number of characteristics of the compared proteins must be defined .
depending on the goal of the clustering , this can be done by selecting one measure or by combining different criteria to score the level of similarity .
the lga_s scoring function has two components , lcs ( longest continuous segments ) and gdt ( global distance test ) , defined for the detection of regions of local and global structure similarities between analyzed structures . in comparing two protein structures
the lcs procedure localizes and superimposes the longest segments of residues that can fit under a selected set of rmsd cutoffs . the gdt algorithm is designed to complement evaluations made with lcs searching for the largest ( not necessary continuous ) set of 
let : 
 m  the number of residues in m , t  the number of residues in t , r(r , m , t ) = 100/t * l(r , m , t ) is the percentage of the target 's ( t 's ) residues that are involved in the maximal ( longest ) continuous segment that fits within an rmsd of r  .
l(r , m , t ) is the length of such identified longest continuous segment of m : t residue pairs , x(m , t)the set of all m : t superpositions calculated by the lga algorithm , g(s , d , m , t)the number of m : t residue pairs for which the distance between ca ( alpha carbon ) atoms is not greater than d  after the superposition s  x(m , t ) is applied , d(d , m , t)=100/t * max{g(s , d , m , t):s  x(m , t ) } is the maximal detected percentage of the ca atoms in t structure that are within a distance threshold of d  from m structure upon calculated s  x(m , t ) superpositions .
the number of residues in m , t  the number of residues in t , r(r , m , t ) = 100/t * l(r , m , t ) is the percentage of the target 's ( t 's ) residues that are involved in the maximal ( longest ) continuous segment that fits within an rmsd of r  .
l(r , m , t ) is the length of such identified longest continuous segment of m : t residue pairs , x(m , t)the set of all m : t superpositions calculated by the lga algorithm , g(s , d , m , t)the number of m : t residue pairs for which the distance between ca ( alpha carbon ) atoms is not greater than d  after the superposition s  x(m , t ) is applied , d(d , m , t)=100/t * max{g(s , d , m , t):s  x(m , t ) } is the maximal detected percentage of the ca atoms in t structure that are within a distance threshold of d  from m structure upon calculated s  x(m , t ) superpositions .
lga_s(m , t ) structure similarity scoring function is defined as a function of two structures m and t calculated as a combination of r(r , m , t ) results from lcs(m , t ) calculations , and d(d , m , t ) results from gdt(m , t ) : 

 where 

 and w = 0.75 is a parameter ( 0  w  1 ) representing a weighting factor between s(lcs ) and s(gdt ) results .
s(lcs ) is a weighted sum of r(r , m , t ) values calculated for n different rmsd cutoffs r ( e.g. n = 3 ; r = 1.0 , 2.0 , 5.0 ) , and s(gdt ) is a weighted sum of d(d , m , t ) values calculated using k different distance cutoffs d ( e.g. k = 20 ; d = 0.5 , 1.0 ,  , 10.0 ) . in the formulae
s(lcs ) and s(gdt ) , the weighting schemes weight higher those r and d results that were calculated for smaller rmsd and distance cutoffs , respectively .
the range of the lga_s values is 0100 , and hierarchical clustering experiments performed on various folds from scop database showed that lga_s alone can serve as a good discriminator for the initial protein structure clustering ( see the results shown in figure 5a ) .
the essence of the stralcp algorithm is the ability to compare hundreds of protein structures in a single reference frame , identify similar fragments that are conserved within a set of analyzed proteins , and use this information to calculate the number of required clusters .
each calculated cluster is assigned with its structural fingerprint that can be defined by a representative structure and a set of spans that are shared among structures grouped together .
comparison of a new structure with a structural fingerprint determines whether the structure should be included to the particular cluster or whether it should be a member of another cluster .
our stralcp algorithm , which automatically clusters proteins and identifies representative structures , can be described as the following list of steps : 
 lga is used to perform all - against - all comparisons in which , for a given set of structures , each structure is used as a frame of reference for comparisons with others.each frame of reference is assigned a set of sequential fragments , which are defined by splitting the corresponding amino acid sequence into consecutive n - residue - long sub - sequences ( n = 10 is used as a default parameter ; e.g. a 120-residue - long protein comprises 12 fragments).after performing all - against - all structure comparisons ( step 1 ) the following information is assigned to each frame of reference : 
 lga_s values between the frame of reference and all other structures , the number of residue pairs that are superimposed locally within rmsd cutoff 0.5  ( using 3-residue - long window ) .
continuous structural segments formed by such residue pairs that are at least five residues long are marked as candidate spans , the number of non - empty fragments ( non - empty fragments are sequential fragments defined in step 2 that overlap by at least one residue with at least one detected span in compared structures).for each frame of reference , all structures having at least 80% ( default parameter ) of the non - empty fragments in common are identified .
a list consisting of maximum number of such structures is created and assigned to each frame of reference.an optimal number of clusters is determined based on the following criteria : 
 the minimum number of clusters that yields a complete set of proteins in the combined lists from ( 4),lga_s between any pair of proteins from the cluster is at least 60% ( default parameter ) , minimum value from ( iii.a).within each cluster , a representative structure is selected , which in comparison with other members of the cluster has the highest values determined in steps ( iii.a ) , ( iii.b ) and ( iii.c ) .
lga is used to perform all - against - all comparisons in which , for a given set of structures , each structure is used as a frame of reference for comparisons with others .
each frame of reference is assigned a set of sequential fragments , which are defined by splitting the corresponding amino acid sequence into consecutive n - residue - long sub - sequences ( n = 10 is used as a default parameter ; e.g. a 120-residue - long protein comprises 12 fragments ) .
after performing all - against - all structure comparisons ( step 1 ) the following information is assigned to each frame of reference : 
 lga_s values between the frame of reference and all other structures , the number of residue pairs that are superimposed locally within rmsd cutoff 0.5  ( using 3-residue - long window ) .
continuous structural segments formed by such residue pairs that are at least five residues long are marked as candidate spans , the number of non - empty fragments ( non - empty fragments are sequential fragments defined in step 2 that overlap by at least one residue with at least one detected span in compared structures ) .
lga_s values between the frame of reference and all other structures , the number of residue pairs that are superimposed locally within rmsd cutoff 0.5  ( using 3-residue - long window ) .
continuous structural segments formed by such residue pairs that are at least five residues long are marked as candidate spans , the number of non - empty fragments ( non - empty fragments are sequential fragments defined in step 2 that overlap by at least one residue with at least one detected span in compared structures ) .
for each frame of reference , all structures having at least 80% ( default parameter ) of the non - empty fragments in common are identified .
a list consisting of maximum number of such structures is created and assigned to each frame of reference .
an optimal number of clusters is determined based on the following criteria : 
 the minimum number of clusters that yields a complete set of proteins in the combined lists from ( 4),lga_s between any pair of proteins from the cluster is at least 60% ( default parameter ) , minimum value from ( iii.a ) .
the minimum number of clusters that yields a complete set of proteins in the combined lists from ( 4 ) , lga_s between any pair of proteins from the cluster is at least 60% ( default parameter ) , minimum value from ( iii.a ) . within each cluster ,
a representative structure is selected , which in comparison with other members of the cluster has the highest values determined in steps ( iii.a ) , ( iii.b ) and ( iii.c ) .
note : in step ( v.a ) a minimum number of clusters are defined based on local similarities in non - empty fragments along the protein sequence using initially selected representative frames of reference .
step ( v.b ) allows reassignment of less similar structures from one cluster to another .
it also allows sub - division of clusters in order to satisfy the requirement that within each cluster any pair of proteins has at least 60% overall structure similarity .
this way less similar structures are not grouped together even if they satisfy the requirement regarding a common set of non - empty fragments ( step 4 ) .
to perform a particular clustering for a set of protein structures , a suitable scoring function or , in general , a scoring algorithm that takes into account a number of characteristics of the compared proteins must be defined .
depending on the goal of the clustering , this can be done by selecting one measure or by combining different criteria to score the level of similarity .
the lga_s scoring function has two components , lcs ( longest continuous segments ) and gdt ( global distance test ) , defined for the detection of regions of local and global structure similarities between analyzed structures . in comparing two protein structures
the lcs procedure localizes and superimposes the longest segments of residues that can fit under a selected set of rmsd cutoffs . the gdt algorithm is designed to complement evaluations made with lcs searching for the largest ( not necessary continuous ) set of 
let : 
 m  the number of residues in m , t  the number of residues in t , r(r , m , t ) = 100/t * l(r , m , t ) is the percentage of the target 's ( t 's ) residues that are involved in the maximal ( longest ) continuous segment that fits within an rmsd of r  .
l(r , m , t ) is the length of such identified longest continuous segment of m : t residue pairs , x(m , t)the set of all m : t superpositions calculated by the lga algorithm , g(s , d , m , t)the number of m : t residue pairs for which the distance between ca ( alpha carbon ) atoms is not greater than d  after the superposition s  x(m , t ) is applied , d(d , m , t)=100/t * max{g(s , d , m , t):s  x(m , t ) } is the maximal detected percentage of the ca atoms in t structure that are within a distance threshold of d  from m structure upon calculated s  x(m , t ) superpositions .
the number of residues in m , t  the number of residues in t , r(r , m , t ) = 100/t * l(r , m , t ) is the percentage of the target 's ( t 's ) residues that are involved in the maximal ( longest ) continuous segment that fits within an rmsd of r  .
l(r , m , t ) is the length of such identified longest continuous segment of m : t residue pairs , x(m , t)the set of all m : t superpositions calculated by the lga algorithm , g(s , d , m , t)the number of m : t residue pairs for which the distance between ca ( alpha carbon ) atoms is not greater than d  after the superposition s  x(m , t ) is applied , d(d , m , t)=100/t * max{g(s , d , m , t):s  x(m , t ) } is the maximal detected percentage of the ca atoms in t structure that are within a distance threshold of d  from m structure upon calculated s  x(m , t ) superpositions .
lga_s(m , t ) structure similarity scoring function is defined as a function of two structures m and t calculated as a combination of r(r , m , t ) results from lcs(m , t ) calculations , and d(d , m , t ) results from gdt(m , t ) : 

 where 

 and w = 0.75 is a parameter ( 0  w  1 ) representing a weighting factor between s(lcs ) and s(gdt ) results .
s(lcs ) is a weighted sum of r(r , m , t ) values calculated for n different rmsd cutoffs r ( e.g. n = 3 ; r = 1.0 , 2.0 , 5.0 ) , and s(gdt ) is a weighted sum of d(d , m , t ) values calculated using k different distance cutoffs d ( e.g. k = 20 ; d = 0.5 , 1.0 ,  , 10.0 ) .
in the formulae s(lcs ) and s(gdt ) , the weighting schemes weight higher those r and d results that were calculated for smaller rmsd and distance cutoffs , respectively .
the range of the lga_s values is 0100 , and hierarchical clustering experiments performed on various folds from scop database showed that lga_s alone can serve as a good discriminator for the initial protein structure clustering ( see the results shown in figure 5a ) .
the essence of the stralcp algorithm is the ability to compare hundreds of protein structures in a single reference frame , identify similar fragments that are conserved within a set of analyzed proteins , and use this information to calculate the number of required clusters .
each calculated cluster is assigned with its structural fingerprint that can be defined by a representative structure and a set of spans that are shared among structures grouped together .
comparison of a new structure with a structural fingerprint determines whether the structure should be included to the particular cluster or whether it should be a member of another cluster .
our stralcp algorithm , which automatically clusters proteins and identifies representative structures , can be described as the following list of steps : 
 lga is used to perform all - against - all comparisons in which , for a given set of structures , each structure is used as a frame of reference for comparisons with others.each frame of reference is assigned a set of sequential fragments , which are defined by splitting the corresponding amino acid sequence into consecutive n - residue - long sub - sequences ( n = 10 is used as a default parameter ;
e.g. a 120-residue - long protein comprises 12 fragments).after performing all - against - all structure comparisons ( step 1 ) the following information is assigned to each frame of reference : 
 lga_s values between the frame of reference and all other structures , the number of residue pairs that are superimposed locally within rmsd cutoff 0.5  ( using 3-residue - long window ) .
continuous structural segments formed by such residue pairs that are at least five residues long are marked as candidate spans , the number of non - empty fragments ( non - empty fragments are sequential fragments defined in step 2 that overlap by at least one residue with at least one detected span in compared structures).for each frame of reference , all structures having at least 80% ( default parameter ) of the non - empty fragments in common are identified . a list consisting of maximum number of such structures is created and assigned to each frame of reference.an optimal number of clusters is determined based on the following criteria : 
 the minimum number of clusters that yields a complete set of proteins in the combined lists from ( 4),lga_s between any pair of proteins from the cluster is at least 60% ( default parameter ) , minimum value from ( iii.a).within each cluster , a representative structure is selected , which in comparison with other members of the cluster has the highest values determined in steps ( iii.a ) , ( iii.b ) and ( iii.c ) .
lga is used to perform all - against - all comparisons in which , for a given set of structures , each structure is used as a frame of reference for comparisons with others .
each frame of reference is assigned a set of sequential fragments , which are defined by splitting the corresponding amino acid sequence into consecutive n - residue - long sub - sequences ( n = 10 is used as a default parameter ; e.g. a 120-residue - long protein comprises 12 fragments ) .
after performing all - against - all structure comparisons ( step 1 ) the following information is assigned to each frame of reference : 
 lga_s values between the frame of reference and all other structures , the number of residue pairs that are superimposed locally within rmsd cutoff 0.5  ( using 3-residue - long window ) .
continuous structural segments formed by such residue pairs that are at least five residues long are marked as candidate spans , the number of non - empty fragments ( non - empty fragments are sequential fragments defined in step 2 that overlap by at least one residue with at least one detected span in compared structures ) .
lga_s values between the frame of reference and all other structures , the number of residue pairs that are superimposed locally within rmsd cutoff 0.5  ( using 3-residue - long window ) .
continuous structural segments formed by such residue pairs that are at least five residues long are marked as candidate spans , the number of non - empty fragments ( non - empty fragments are sequential fragments defined in step 2 that overlap by at least one residue with at least one detected span in compared structures ) .
for each frame of reference , all structures having at least 80% ( default parameter ) of the non - empty fragments in common are identified .
a list consisting of maximum number of such structures is created and assigned to each frame of reference .
an optimal number of clusters is determined based on the following criteria : 
 the minimum number of clusters that yields a complete set of proteins in the combined lists from ( 4),lga_s between any pair of proteins from the cluster is at least 60% ( default parameter ) , minimum value from ( iii.a ) .
the minimum number of clusters that yields a complete set of proteins in the combined lists from ( 4 ) , lga_s between any pair of proteins from the cluster is at least 60% ( default parameter ) , minimum value from ( iii.a ) . within each cluster ,
a representative structure is selected , which in comparison with other members of the cluster has the highest values determined in steps ( iii.a ) , ( iii.b ) and ( iii.c ) .
note : in step ( v.a ) a minimum number of clusters are defined based on local similarities in non - empty fragments along the protein sequence using initially selected representative frames of reference .
step ( v.b ) allows reassignment of less similar structures from one cluster to another .
it also allows sub - division of clusters in order to satisfy the requirement that within each cluster any pair of proteins has at least 60% overall structure similarity .
this way less similar structures are not grouped together even if they satisfy the requirement regarding a common set of non - empty fragments ( step 4 ) .
a proper protein classification is critical for better understanding and prediction of a protein 's structure , function and interaction with other proteins .
it is known that sequence similarities nearly always correspond to structure similarities , enabling structure and function prediction for uncharacterized proteins .
structural similarity , however , does not necessarily correspond to sequence similarity ( figure 2 ) . through structural comparison and classification , we identified a family of crystal structures that failed to be detected ( 18 ) by sequence - based methods like psi - blast ( 14 ) . using a structure - based method ( e.g. dali , lga )
it was found that three eap domains from staphylococcus aureus ( 18 ) , which could not be properly classified by sequence - based methods , shared a previously unrecognized similarity to another class of bacterial toxins .
for each of the eap domains [ eap2 ( pdb entry : 1yn3 ) , eaph1 ( 1yn4 ) , eaph2 ( 1yn5 ) ] , we have performed structural pdb searches using our lga server ( 19 ) . as a result , 134 domains from the scop superfamily d.15.6 ( superantigen toxins , c - terminal domain ) were identified as most similar to eap structures ( only 20 structures are shown in provided figures 1 , 3 , and 4 ; 3 eap domains and 17 domains from scop ) .
figure 1 shows that all 20 proteins are very similar in detected structurally conserved frames formed by 4 strands and 1 helix ( figure 2 ) .
the superposition of 1yn4_a and d1m4va2 ( 1m4v_a in figure 2 ) corresponds to the fourth bar in figure 1 and shows that these two structures differ in several loop regions only ( structural deviations above 2  are colored in yellow - red ) .
note that the level of sequence identity between these two proteins is only 14% ( seq_id ) , whereas the level of structure similarity is 75% ( lga_s ) . 

figure 1.structure similarities between eap domains from s. aureus ( pdb : 1yn3 , 4 and 5 ) and 17 protein domains from the scop superfamily comprising superantigen toxins .
all proteins were compared to the structure of eaph1 ( 1yn4_a ) , which serves as a frame of reference .
colored bars represent calpha  calpha distance deviation between 1yn4_a [ 99 residues ; from the left ( n - terminal ) to the right ( c - terminal ) ] superimposed with 20 structures from pdb ( first bar represents a 1yn4_a1yn4_a self - comparison ) .
colors represent distances between aligned residues and range from green ( below 2  ) to red ( above 6  ) .
the columns at the right contain information about the level of sequence identity ( seq_id ) and structure similarity ( lga_s ) . 

figure 2.a 3d plot of structural superposition between 1yn4_a and 1m4v_a ( scop domain : d1m4va2 ) that corresponds to the fourth colored bar in figure 1 . the level of sequence identity between proteins seq_id : 14% , and the level of structure similarity lga_s : 75% . 

figure 3.the results from the analysis of structure similarities between eap domains from s. aureus and proteins from the scop superfamily of superantigen toxins ( same domains as in figure 1 ) .
figure 4.stralcp clustering applied to the same set of 20 structures as in figures 1 and 3 .
stralcp calculations were performed using default parameters ( lga_s = 60% , dist = 5  ) .
each row begins from the cluster number , followed by the domain name , and the set of amino acids that are extracted from detected structurally conserved spans .
dots indicate regions that structurally deviate in at least one pairwise comparison between members of the cluster .
note : dots do not indicate the actual number of residue pairs between detected spans .
figure 5.(a ) dendrogram showing the results of an lga_s - based ( single measure ) clustering of 24 scop domains from fold a.8 .
each code ( entry_family ) represents one protein from the scop classification : entry and family number .
we used the r package ( version 2.1.1 ; http://www.r-project.org/ ) for the hierarchical clustering and visualization of calculated lga_s results from all - against - all structure comparisons .
structure similarities between eap domains from s. aureus ( pdb : 1yn3 , 4 and 5 ) and 17 protein domains from the scop superfamily comprising superantigen toxins .
all proteins were compared to the structure of eaph1 ( 1yn4_a ) , which serves as a frame of reference .
colored bars represent calpha  calpha distance deviation between 1yn4_a [ 99 residues ; from the left ( n - terminal ) to the right ( c - terminal ) ] superimposed with 20 structures from pdb (
colors represent distances between aligned residues and range from green ( below 2  ) to red ( above 6  ) .
the columns at the right contain information about the level of sequence identity ( seq_id ) and structure similarity ( lga_s ) . a 3d plot of structural superposition between 1yn4_a and 1m4v_a ( scop domain : d1m4va2 ) that corresponds to the fourth colored bar in figure 1 . the level of sequence identity between proteins seq_id : 14% , and the level of structure similarity lga_s : 75% . the results from the analysis of structure similarities between eap domains from s. aureus and proteins from the scop superfamily of superantigen toxins ( same domains as in figure 1 ) .
stralcp clustering applied to the same set of 20 structures as in figures 1 and 3 .
stralcp calculations were performed using default parameters ( lga_s = 60% , dist = 5  ) .
each row begins from the cluster number , followed by the domain name , and the set of amino acids that are extracted from detected structurally conserved spans .
dots indicate regions that structurally deviate in at least one pairwise comparison between members of the cluster .
note : dots do not indicate the actual number of residue pairs between detected spans .
( a ) dendrogram showing the results of an lga_s - based ( single measure ) clustering of 24 scop domains from fold a.8 .
each code ( entry_family ) represents one protein from the scop classification : entry and family number .
we used the r package ( version 2.1.1 ; http://www.r-project.org/ ) for the hierarchical clustering and visualization of calculated lga_s results from all - against - all structure comparisons .
( b ) clustering created using stralcp algorithm with default cutoff lga_s = 60% . in general , all eap domains have a high level of overall structure similarity ( lga_s over 60% ) to most of the other analyzed structures , whereas the level of sequence identity is very low ( below 20% ) . in figure 1 , we show the results from the structure comparisons of the set of selected 20 proteins when structure 1yn4_a was chosen as a frame of reference and in figure 3 the structure seh ( pdb : 1f77 ; scop domain d1f77a2 ) ( 20 ) was selected as a frame of reference . from the comparison of these two plots
we can conclude that d1f77a2 may serve as a better representation ( average structure ) for the analyzed set of 20 proteins ( at least for the top 13 of them ) than the structure 1yn4_a .
the obtained results suggest that a given set of 20 structures can be structurally divided into at least two clusters .
our stralcp system creates such a clustering automatically ( figure 4 ) . by this clustering the eap structures : 1yn3 - 5
are grouped together ( cluster2 ) with four other protein structures : set1 ( pdb : 1v1p ) ( 21 ) , set3 ( pdb : 1m4v ) ( 22 ) , and tsst1 ( pdb : 1aw7 , 2tss ) ( 23,24 ) .
additional tests showed that if we had introduced more strict structure similarity requirements [ e.g. lga_s cutoff 80% ( see step 5.b in stralcp algorithm ) ] , then cluster2 would have been split into two additional clusters ( data not shown ) where all three eap domains ( 1yn3 - 5 ) were separated from the set1 , set3 and tsst1 structures .
as described in the methods section the stralcp clustering approach consists of two steps : ( i ) calculating all - against - all structural alignments using lga program , and ( ii ) extracting from calculated alignments structurally conserved regions and using them to group proteins accordingly .
for example , on a single linux workstation equipped with amd-64 5000 dual core processor , the calculations of all - against - all pairwise structural alignments for 20 discussed above structures ( 3 eap domains and 17 domains from scop ) lasted about 10 min , while the clustering ( step 2 ) was completed in less than 10 s. in order to estimate the accuracy of a stralcp clustering approach , we have performed comparisons with the scop ( ver .
we tested stralcp calculations on domains from 25 different scop folds : a.5 , a.7 , a.8 , a.24 , a.29 , a.137 , b.2 , b.42 , b.43 , b.68 , b.80 , b.85 , c.8 , c.51 , c.56 , d.52 , d.68 , d.79 , d.110 , d.129 , f.1 , f.4 , f.23 , g.41 , h.4 .
we have selected these folds as a representative sample from all 7 scop classes with an additional requirement that each fold consists of at least four superfamilies . in the scop database ver .
1.71 , there are only 63 such folds that satisfy this requirement . in total , our benchmark set consisted of nd = 4620 domains from nf = 343 families , and ns = 243 superfamilies .
complete sets of results from this experiment can be found at a server website : http://as2ts.llnl.gov / as2ts / stralcp/. in figure 5 , we present the results from stralcp calculations applied to 24 domains from scop fold a.8 ( immunoglobulin / albumin - binding domain - like ) . in figure 5a
, we use scop fold a.8 , as an example to show some of the details from the hierarchical dependencies among structures calculated using lga_s as a single measure for clustering . in figure 5b , we show how the structures from fold a.8 can be automatically separated using our stralcp ( multi - criteria - based clustering ) approach . this example shows that by using stralcp we can clearly separate proteins into appropriate clusters that correspond with a high agreement to the defined scop families ( see figure 5b , right column ; scop family codes ) . in order to assess 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 , 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 using 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 ) .
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 rather how many of the created clusters are compromised ( proteins that are separated in another clustering scheme being merged ) .
the results from the evaluation of the differences between scop and stralcp clusters at the level of scop families showed that on average the level of misclustering ( mc ) is 3% .
it suggests that the proposed strictly structure - based clustering method can be considered robust in that it detects relationships at the family level with a good agreement with the manually maintained scop database .
as described in the methods section the stralcp clustering approach consists of two steps : ( i ) calculating all - against - all structural alignments using lga program , and ( ii ) extracting from calculated alignments structurally conserved regions and using them to group proteins accordingly .
for example , on a single linux workstation equipped with amd-64 5000 dual core processor , the calculations of all - against - all pairwise structural alignments for 20 discussed above structures ( 3 eap domains and 17 domains from scop ) lasted about 10 min , while the clustering ( step 2 ) was completed in less than 10 s. in order to estimate the accuracy of a stralcp clustering approach , we have performed comparisons with the scop ( ver .
we tested stralcp calculations on domains from 25 different scop folds : a.5 , a.7 , a.8 , a.24 , a.29 , a.137 , b.2 , b.42 , b.43 , b.68 , b.80 , b.85 , c.8 , c.51 , c.56 , d.52 , d.68 , d.79 , d.110 , d.129 , f.1 , f.4 , f.23 , g.41 , h.4 .
we have selected these folds as a representative sample from all 7 scop classes with an additional requirement that each fold consists of at least four superfamilies . in the scop database ver .
1.71 , there are only 63 such folds that satisfy this requirement . in total , our benchmark set consisted of nd = 4620 domains from nf = 343 families , and ns = 243 superfamilies .
complete sets of results from this experiment can be found at a server website : http://as2ts.llnl.gov / as2ts / stralcp/. in figure 5 , we present the results from stralcp calculations applied to 24 domains from scop fold a.8 ( immunoglobulin / albumin - binding domain - like ) . in figure 5a , we use scop fold a.8 , as an example to show some of the details from the hierarchical dependencies among structures calculated using lga_s as a single measure for clustering . in figure 5b , we show how the structures from fold a.8 can be automatically separated using our stralcp ( multi - criteria - based clustering ) approach .
this example shows that by using stralcp we can clearly separate proteins into appropriate clusters that correspond with a high agreement to the defined scop families ( see figure 5b , right column ; scop family codes ) . in order to assess 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 , 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 using 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 ) .
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 rather how many of the created clusters are compromised ( proteins that are separated in another clustering scheme being merged ) .
the results from the evaluation of the differences between scop and stralcp clusters at the level of scop families showed that on average the level of misclustering ( mc ) is 3% .
it suggests that the proposed strictly structure - based clustering method can be considered robust in that it detects relationships at the family level with a good agreement with the manually maintained scop database .
as discussed in ref . ( 13 ) , a strategy combining information from both sequence and structure comparisons would be expected to perform better than either method alone .
however the analysis of the clustering approach applied to the benchmark set of 25 scop folds leads to the encouraging conclusion that the stralcp algorithm , even if it is based purely on structure comparisons , exhibits a low ( on average 3% ) misclustering effect : domains from different scop families were clustered separately .
it is important to keep in mind that a purely structure - based approach to clustering may result in two proteins that are identical in sequence being clustered separately if the two structures differ in conformation ; we observed that the stralcp algorithm is able to detect the structural differences between domains from the same scop family and cluster them separately .
it is for this reason that our clustering approach may produce more clusters than the number of scop families .
for example the family a.8.6.1 ( figure 5b ) was separated by stralcp into two clusters : cluster3 ( staphylocoagulase first domain ) and cluster4 ( staphylocoagulase second domain ) , and the family a.8.4.1 was divided into two clusters : cluster5 ( dnak domain from escherichia coli ) and cluster2 ( dnak domain from rat ) .
the stralcp algorithm will also group proteins in different clusters if they significantly differ in length or if multi - domain structures are in different conformations ( e.g.  open and  closed versions of the same protein ) .
we also can observe additional sub - clustering of protein families when criteria for structure comparison are sufficiently stringent ( e.g. a higher lga_s cutoff is introduced ) .
it provides valuable information about the regions that are structurally in the same conformation , which could be useful in various studies and classification schemes .
the separation of similar or identical proteins , but in different structural conformations , could be reduced by introducing a sequence similarity analysis into the stralcp algorithm . however , in this study , in order to detect the limits of purely structure - based approaches we do not include sequence information to the scoring and clustering algorithm .
the sequence - based analysis may be considered as an option in future development efforts .
 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 . 