BACKGROUND
the structural genomics consortium  <cit>  aims to populate protein fold space using high-throughput experimental technologies.
as a result the number of known structures in the protein data bank   <cit>  is increasing rapidly every year and currently holds  <dig>  structures .
this highlights the importance of the need for fast and reliable protein structure comparison methods.
there are various methods which use detailed 3d structures for comparison; ssap  <cit>  uses a double dynamic programming method that takes into account several different features of protein structure including phi/psi angles, accessibility and inter-residue vectors to align two protein structures.
other approaches include stamp  <cit> , dali  <cit>  and the combinatorial extension method  <cit> .
on the other hand abstract level structural comparison methods are based on topological/vector models of secondary structure elements  and their relationships.
vast is a vector based protein structure comparison method  <cit> .
grath  <cit>  is a graph-based algorithm that compares the axial vectors of alpha helices and beta strands of two proteins, together with the distances, angles and chirality between these vectors.
it is based on a method by grindley et al.
<cit> .
earlier work by koch et al.
<cit>  uses a graph method to find maximal common sses in a pair of proteins.
tops is a graph-based method applied to the topological representation of the protein structures  <cit> .
although these methods perform very fast protein structure comparison in most cases the results have significantly less biological interpretation due to the abstract nature of the protein model.
moreover, the functional annotation problem is made much more complex by the fact that the number of protein folds is limited while their range of functions is very diverse.
for example, the current version of the scop database classified the  tim barrels protein fold into  <dig> distinct functional superfamilies.
this motivated our research to develop a novel topological model for protein structures, enhanced with structural and biochemical features, such as ligand interaction information and amino acid sequence length of the secondary structures, in order to permit better, more biologically significant comparison methods.
previously, we have discussed the basic mechanisms of our novel tops+ comparison method for novel topological models.
we compute the edit distance between two proteins based on tops+ strings elements using a dynamic programming approach.
we have benchmarked our method with an all-against-all pairwise comparison using a large dataset of  <dig>  non-redundant structures from the pdb <dig> and the results were validated using the standard scop superfamily classification numbers.
we have also compared our method against other methods and showed that it is faster than ssap, fatcat, dali and tops and that it has a comparable performance against tops  <cit> .
recently we developed the tops++fatcat system that exploits the tops+ strings comparison method to speedup the fatcat protein structural alignment program for fast flexible structural alignment, while preserving the accuracy of the original fatcat method  <cit> .
these promising results have facilitated the introduction of further constraints on ligand-arc matching.
in this paper, we show how the above results can be significantly improved using parameter optimization at two stages of the tops+ method:  in the generation of the dynamic programming table and  in the computation of the comparison score using a compression measure.
the dynamic programming algorithm includes weight tables for matching tops+ strings elements, the match scores take into account not only the ssetype, orientation but in addition they include scores for total in/out/ligand arcs together with their arc types such as right and left chiralities, and parallel and anti-parallel hydrogen-bonds.
this research work involved  generating the tops descriptions enhanced with in/out/ligand arc information for a large set of proteins;  designing the weight tables;  optimization of weights in the table;  designing a pairwise comparison metric based on a compression measure and optimizing different parameters to take into account the variability on both components of the topological and ligand interaction features.
the optimization of our advanced tops+ comparison method was carried out on the pdb <dig> representative dataset.
furthermore, we assess the biological significance of our method against existing protein structure comparison methods based on cluster analysis and validation using an f-measure calculation  <cit>  on the chew-kedem dataset  <cit> .
RESULTS
analysis of results for the pdb <dig> dataset
auc/f-measure values for all the comparison methods for the pdb <dig> dataset.
in alpha+beta class our advtops+ method has a 90% accuracy, which is superior when compared with both tops and our basic tops+ method, which have only 84% accuracy .
because these proteins are composed of segregated alpha and beta regions the structure-dependent ligand interactions and additional chiral, hydrogen bonds are also present.
thus our parameter optimization can handle all arcs more efficiently.
on the other hand, the alpha/beta class of proteins contains mixed alpha and beta secondary structures; more importantly although the protein domains from these classes have ligand interactions, they may not be structure-dependent ligand interactions.
in these classes for most of the protein superfamilies the ligands have a tendency to bind the clefts or binding pocket which have appropriate physiochemical properties and the correct conformational geometry of the amino acids.
furthermore it is important to note that in our tops+ and advtops+ comparison methods we have considered only the total number of ligand-arcs rather than the actual ligand property match, thus we have false positives in some scop classes.
in the case of all-beta class proteins our advtops+ method has comparable performance against tops with 87% accuracy ; in this class proteins contain a significant number of hydrogen bond and chiral arcs, and thus parameter optimization is performed more efficiently.
from the f-measure statistical evaluation analysis  we found that the advtops+ method appears to always do better than tops and tops+ except for the alpha/beta class of proteins .
the overall results show that our advtops+ method exhibits substantial improvement compared to basic tops+.
it has better performance for all-alpha and alpha+beta proteins compared to tops.
on the other scop classes the performance is comparable with tops.
since our method considers only the total number of ligand arcs rather than the actual ligand property this leads to false positives to some extent.
our advtops+ method can efficiently recognize structure-dependent ligand interactions appropriately in the case of dna-binding proteins and metal binding proteins.
analysis of results for the chew-kedem dataset
our advanced tops+ comparison method outperforms all the other methods  and groups  <dig> representative proteins from five fold families into biologically significant clusters .
in figure  <dig> each protein domain is represented in the following format "domainname_foldfamilies".
the tags of the "foldfamilies" represents protein structures from five different protein folds; where tb = tim barrel, g = globins, ab = alpha beta, b = all beta, and a = all alpha protein families.
the clusters obtained from our advanced tops+ method show that all of the protein domains are grouped according to their structural fold and biological significance except d1ct9a <dig> .
the basic tops+ method also groups most of the protein domains into correct fold families except for an all beta protein d1cdb__ and two protein domains d2hbg__, d1hlm__ from globins which are grouped together with all alpha proteins .
in comparison both the tops and ssap methods produce clusters in which there are many wrongly grouped domains .
the quantitative analysis using the f-measure calculation results in more than 98% accuracy for our advtops+ method, which is higher than ssap , tops  and basic tops+  .
when we compare our advtops+ with our basic tops+ method we have achieved a 5% improvement based on parameter optimization.
f-measure of the clusters obtained from different protein structure comparison methods.
one interesting example from our cluster analysis  is that of the asparagine synthetase b, c-terminal domain d1ct9a <dig>  which is grouped by the advanced tops+ method with the tim barrel domains .
table  <dig> provides advanced tops+ comparison scores for d1ct9a <dig>  against those protein domains belonging to alpha-beta and tim-barrel fold families, together with their sses length  and lcs pattern length .
interestingly, d1ct9a <dig> has a smaller distance score against all of the tim-barrel proteins compared to alpha-beta protein domains; specifically, for the xylose isomerase protein d6xia__.
when we closely checked the 3d structure of d1ct9a <dig>  we found that it has alpha helices in its n-terminal domain and it contains half tim-barrel like structures in its c-terminal domain .
this suggests that a sub-domain of the d1ct9a <dig> exhibits a structural drift between the alpha-beta fold and the tim-barrel fold.
the structural drift  <cit>  is a special case of gregariousness as described by  <cit> .
since our tops+ method is based on an abstraction of protein structure in the form of sses and topological features without any geometrical properties it is able to perform matching at the fold level and to include most of the sses which are common to two protein structures.
advtops+ comparison scores for alpha-beta and tim-barrel folds in the chew-kedem dataset.
CONCLUSIONS
in this paper we have reported the generation of tops+ and tops+ strings models for large datasets and have presented an improved tops+ comparison method using parameter optimization both for the computation of the dynamic programming table and the computation of the comparison score using a compression metric.
through our evaluation analysis we have showed that our advanced tops+ comparison method has a substantial improvement on all the scop classes compared to our basic tops+ method.
our advanced tops+ method has better performance compared to tops on alpha+beta and all-alpha and is comparable on all-beta and alpha/beta.
on the chew-kedem dataset our advanced tops+ comparison outperforms all the other methods.
this demonstrates that our tops+ and tops+ strings models can find more biologically significant results and has led to interesting new directions to incorporate ligand-pattern discovery in tops+ comparison  <cit> .
our method is faster than tops and ssap because it has time complexity o, where n represents the number of sses in the protein domains.
this research opens new doors to an exciting improvement to our tops+ models and advanced tops+ comparison method by the addition of features such as amino-acid sequences, biochemical properties of the protein-ligand interaction at atomic level, and arc scores  for each sse.
moreover we can improve the comparison process with additional statistical scoring values for each tops+ strings element match both at the micro  and the macro level .
furthermore our novel tops+ models, tops+ strings and comparison approaches could be applicable to different problem areas such as rna secondary structure comparison and prediction.
most of the drug-discovery process starts with in-silico chemical compound screening which is computationally expensive.
our tops+ comparison approach could be applied as an initial step to prune the search space and filter the proteins into same folds interacting with similar or different ligands and different folds interacting with similar or different ligands.

 the structural genomics consortium aims to populate protein fold space using high-throughput experimental technologies. as a result the number of known structures in the protein data bank is increasing rapidly every year and currently holds structures. this highlights the importance of the need for fast and reliable protein structure comparison methods. there are various methods which use detailed 3d structures for comparison; ssap uses a double dynamic programming method that takes into account several different features of protein structure including phi/psi angles, accessibility and inter-residue vectors to align two protein structures. other approaches include stamp, dali and the combinatorial extension method. on the other hand abstract level structural comparison methods are based on topological/vector models of secondary structure elements and their relationships. vast is a vector based protein structure comparison method. grath is a graph-based algorithm that compares the axial vectors of alpha helices and beta strands of two proteins, together with the distances, angles and chirality between these vectors. it is based on a method by grindley et al.. earlier work by koch et al. uses a graph method to find maximal common sses in a pair of proteins. tops is a graph-based method applied to the topological representation of the protein structures. although these methods perform very fast protein structure comparison in most cases the results have significantly less biological interpretation due to the abstract nature of the protein model. moreover, the functional annotation problem is made much more complex by the fact that the number of protein folds is limited while their range of functions is very diverse. for example, the current version of the scop database classified the tim barrels protein fold into distinct functional superfamilies. this motivated our research to develop a novel topological model for protein structures, enhanced with structural and biochemical features, such as ligand interaction information and amino acid sequence length of the secondary structures, in order to permit better, more biologically significant comparison methods. previously, we have discussed the basic mechanisms of our novel tops+ comparison method for novel topological models. we compute the edit distance between two proteins based on tops+ strings elements using a dynamic programming approach. we have benchmarked our method with an all-against-all pairwise comparison using a large dataset of non-redundant structures from the pdb and the results were validated using the standard scop superfamily classification numbers. we have also compared our method against other methods and showed that it is faster than ssap, fatcat, dali and tops and that it has a comparable performance against tops. recently we developed the tops++fatcat system that exploits the tops+ strings comparison method to speedup the fatcat protein structural alignment program for fast flexible structural alignment, while preserving the accuracy of the original fatcat method. these promising results have facilitated the introduction of further constraints on ligand-arc matching. in this paper, we show how the above results can be significantly improved using parameter optimization at two stages of the tops+ method: in the generation of the dynamic programming table and in the computation of the comparison score using a compression measure. the dynamic programming algorithm includes weight tables for matching tops+ strings elements, the match scores take into account not only the ssetype, orientation but in addition they include scores for total in/out/ligand arcs together with their arc types such as right and left chiralities, and parallel and anti-parallel hydrogen-bonds. this research work involved generating the tops descriptions enhanced with in/out/ligand arc information for a large set of proteins; designing the weight tables; optimization of weights in the table; designing a pairwise comparison metric based on a compression measure and optimizing different parameters to take into account the variability on both components of the topological and ligand interaction features. the optimization of our advanced tops+ comparison method was carried out on the pdb representative dataset. furthermore, we assess the biological significance of our method against existing protein structure comparison methods based on cluster analysis and validation using an f-measure calculation on the chew-kedem dataset.  analysis of results for the pdb dataset auc/f-measure values for all the comparison methods for the pdb dataset. in alpha+beta class our advtops+ method has a 90% accuracy, which is superior when compared with both tops and our basic tops+ method, which have only 84% accuracy. because these proteins are composed of segregated alpha and beta regions the structure-dependent ligand interactions and additional chiral, hydrogen bonds are also present. thus our parameter optimization can handle all arcs more efficiently. on the other hand, the alpha/beta class of proteins contains mixed alpha and beta secondary structures; more importantly although the protein domains from these classes have ligand interactions, they may not be structure-dependent ligand interactions. in these classes for most of the protein superfamilies the ligands have a tendency to bind the clefts or binding pocket which have appropriate physiochemical properties and the correct conformational geometry of the amino acids. furthermore it is important to note that in our tops+ and advtops+ comparison methods we have considered only the total number of ligand-arcs rather than the actual ligand property match, thus we have false positives in some scop classes. in the case of all-beta class proteins our advtops+ method has comparable performance against tops with 87% accuracy; in this class proteins contain a significant number of hydrogen bond and chiral arcs, and thus parameter optimization is performed more efficiently. from the f-measure statistical evaluation analysis we found that the advtops+ method appears to always do better than tops and tops+ except for the alpha/beta class of proteins. the overall results show that our advtops+ method exhibits substantial improvement compared to basic tops+. it has better performance for all-alpha and alpha+beta proteins compared to tops. on the other scop classes the performance is comparable with tops. since our method considers only the total number of ligand arcs rather than the actual ligand property this leads to false positives to some extent. our advtops+ method can efficiently recognize structure-dependent ligand interactions appropriately in the case of dna-binding proteins and metal binding proteins. analysis of results for the chew-kedem dataset our advanced tops+ comparison method outperforms all the other methods and groups representative proteins from five fold families into biologically significant clusters. in figure each protein domain is represented in the following format "domainname_foldfamilies". the tags of the "foldfamilies" represents protein structures from five different protein folds; where tb = tim barrel, g = globins, ab = alpha beta, b = all beta, and a = all alpha protein families. the clusters obtained from our advanced tops+ method show that all of the protein domains are grouped according to their structural fold and biological significance except d1ct9a. the basic tops+ method also groups most of the protein domains into correct fold families except for an all beta protein d1cdb__ and two protein domains d2hbg__, d1hlm__ from globins which are grouped together with all alpha proteins. in comparison both the tops and ssap methods produce clusters in which there are many wrongly grouped domains. the quantitative analysis using the f-measure calculation results in more than 98% accuracy for our advtops+ method, which is higher than ssap, tops and basic tops+. when we compare our advtops+ with our basic tops+ method we have achieved a 5% improvement based on parameter optimization. f-measure of the clusters obtained from different protein structure comparison methods. one interesting example from our cluster analysis is that of the asparagine synthetase b, c-terminal domain d1ct9a which is grouped by the advanced tops+ method with the tim barrel domains. table provides advanced tops+ comparison scores for d1ct9a against those protein domains belonging to alpha-beta and tim-barrel fold families, together with their sses length and lcs pattern length. interestingly, d1ct9a has a smaller distance score against all of the tim-barrel proteins compared to alpha-beta protein domains; specifically, for the xylose isomerase protein d6xia__. when we closely checked the 3d structure of d1ct9a we found that it has alpha helices in its n-terminal domain and it contains half tim-barrel like structures in its c-terminal domain. this suggests that a sub-domain of the d1ct9a exhibits a structural drift between the alpha-beta fold and the tim-barrel fold. the structural drift is a special case of gregariousness as described by. since our tops+ method is based on an abstraction of protein structure in the form of sses and topological features without any geometrical properties it is able to perform matching at the fold level and to include most of the sses which are common to two protein structures. advtops+ comparison scores for alpha-beta and tim-barrel folds in the chew-kedem dataset.  in this paper we have reported the generation of tops+ and tops+ strings models for large datasets and have presented an improved tops+ comparison method using parameter optimization both for the computation of the dynamic programming table and the computation of the comparison score using a compression metric. through our evaluation analysis we have showed that our advanced tops+ comparison method has a substantial improvement on all the scop classes compared to our basic tops+ method. our advanced tops+ method has better performance compared to tops on alpha+beta and all-alpha and is comparable on all-beta and alpha/beta. on the chew-kedem dataset our advanced tops+ comparison outperforms all the other methods. this demonstrates that our tops+ and tops+ strings models can find more biologically significant results and has led to interesting new directions to incorporate ligand-pattern discovery in tops+ comparison. our method is faster than tops and ssap because it has time complexity o, where n represents the number of sses in the protein domains. this research opens new doors to an exciting improvement to our tops+ models and advanced tops+ comparison method by the addition of features such as amino-acid sequences, biochemical properties of the protein-ligand interaction at atomic level, and arc scores for each sse. moreover we can improve the comparison process with additional statistical scoring values for each tops+ strings element match both at the micro and the macro level. furthermore our novel tops+ models, tops+ strings and comparison approaches could be applicable to different problem areas such as rna secondary structure comparison and prediction. most of the drug-discovery process starts with in-silico chemical compound screening which is computationally expensive. our tops+ comparison approach could be applied as an initial step to prune the search space and filter the proteins into same folds interacting with similar or different ligands and different folds interacting with similar or different ligands. 
we have developed a tops+ string model as an improvement to the tops graph model by considering loops as secondary structure elements in addition to helices and strands, representing ligands as first class objects, and describing interactions between sses, and sses and ligands, by incoming and outgoing arcs, annotating sses with the interaction direction and type. benchmarking results of an all-against-all pairwise comparison using a large dataset of non-redundant structures from the pdb dataset demonstrate the biological significance, in terms of scop classification at the superfamily level, of our tops+ comparison method. our advanced tops+ comparison shows better performance on the pdb dataset compared to our basic tops+ method, giving 90% accuracy for scop alpha+beta; a 6% increase in accuracy compared to the tops and basic tops+ methods. it also outperforms the tops, basic tops+ and ssap comparison methods on the chew-kedem dataset, achieving 98% accuracy. in this paper we show how these results can be significantly improved using parameter optimization, and we call the resulting optimised tops+ method as advanced tops+ comparison method i.e. previously we have discussed the basic mechanisms of our novel method for structure comparison based on our tops+ model. although methods based on highly abstract descriptions of protein structures, such as vast and tops, can perform very fast protein structure comparison, the results can lack a high degree of biological significance.
 although methods based on highly abstract descriptions of protein structures, such as vast and tops, can perform very fast protein structure comparison, the results can lack a high degree of biological significance. previously we have discussed the basic mechanisms of our novel method for structure comparison based on our tops+ model. in this paper we show how these results can be significantly improved using parameter optimization, and we call the resulting optimised tops+ method as advanced tops+ comparison method i.e. advtops+.  we have developed a tops+ string model as an improvement to the tops graph model by considering loops as secondary structure elements in addition to helices and strands, representing ligands as first class objects, and describing interactions between sses, and sses and ligands, by incoming and outgoing arcs, annotating sses with the interaction direction and type. benchmarking results of an all-against-all pairwise comparison using a large dataset of non-redundant structures from the pdb dataset demonstrate the biological significance, in terms of scop classification at the superfamily level, of our tops+ comparison method.  our advanced tops+ comparison shows better performance on the pdb dataset compared to our basic tops+ method, giving 90% accuracy for scop alpha+beta; a 6% increase in accuracy compared to the tops and basic tops+ methods. it also outperforms the tops, basic tops+ and ssap comparison methods on the chew-kedem dataset, achieving 98% accuracy. software availability the tops+ comparison server is available at http://balabio.dcs.gla.ac.uk/mallika/webtops/. 