BACKGROUND
over the past few decades, major advances in the field of molecular biology, coupled with advances in genomic technologies, have led to an explosive growth of biological sequences databases.
for example, there are several well-known databases about protein: pfam  <cit>  , scop  <cit>  , swiss-prot  <cit>  , and protein information resource   <cit>  .
this deluge of databases, in turn, produces new questions to analyze protein sequences such as how to classify protein sequences, induce their evolutionary information, and predict their structures.
among protein sequence analysis, some important computational methods are similarity search, phylogenetic analysis and sequence classification.
the similarity search  <cit>  is to search a database of known function sequences and uses the structures and functions of the most closely matched known sequences to analyze the structure and function of query sequence.
phylogenetic analysis  <cit>  is the study of the evolutionary history among species.
it can also provide useful information for pharmaceutical researchers to determine which species share the medicinal qualities  <cit> .
classification protein  <cit>  is to get a biologically meaningful partition.
it has several advantages: when proteins are grouped into a family, it can provide us some clues about the general features of this family and evolutionary evidence of proteins, and further infer the biological function of a new sequence by its similarity to some function-known sequences.
moreover, protein classification can be used to facilitate protein three-dimensional structure discovery, which is very important for understanding proteins' functions.
however, these computational methods heavily rely on the similarity measures defined among biological sequences.
because of the importance of research into similarity measures, numerous efficient algorithms have been developed, but challenges remain.
moreover, we believe that further improvements in the similarity measures will allow us to design more effective tools, which can help us to look back more deeply in evolutionary time.
one kind of the most common dissimilarity measures in this area is edit distance by aligning two sequences.
it is defined as the required number of insertions, deletions, and replacements of characters from the first protein sequence to obtain the second protein sequence.
but this measure is encountered with difficulties:  computation with regard to large biological databases  <cit> ;  the score schemes chosen  <cit> .
therefore, alignment-free measures are actively pursued to overcome the limitations of protein analysis by alignment.
up to now, many efficient alignment-free measures for sequences comparison have been proposed, but they are still in the early development compared with alignment-based methods.
one of the comprehensive reviews  <cit>  reported several concepts of similarity measures, such as euclidean distance  <cit> , mahalanobis distances  <cit> , kullback-leibler discrepancy  <cit> , cosine distance  <cit>  and pearson's correlation coefficient  <cit> .
recently, several novel alignment-free measures have been designed for protein sequences analysis, such as s <dig> and s <dig>  <cit> , w-metric  <cit> , universal similarity metric  <cit> , local decoding  <cit> , cluss  <cit>  and long short-term memory  <cit> .
among the statistical measures, each sequence is mapped into an n-dimensional vector according to its k-word frequencies.
linear algebra theory is further employed to define the similarity score between sequences represented in vector spaces.
the kld extended by wu et al.
is computed in terms of two vectors of relative frequencies of k-words over a sliding window from two given dna sequences.
however, in an application where some entries of vectors are equal to  <dig> or  <dig>  kld becomes unsuitable.
in this paper, we present two statistical measures to overcome the limitation of the measure kld.
the contents can be summarized as follows:
<dig>  we present a scheme to build protein 'sequence space' based on the score or amino acid substitution matrices and calculate k-word frequencies of protein 'sequence space'.
<dig>  two statistical measures gre.k and gsm.k, as the extended jensen-shannon divergence, are proposed.
they are based on k-word frequencies and jensen-shannon divergence.
although these two concepts are not new, their generalizations result in the novel aspect of these measures.
particularly, the statistical measure, gdis.k, is proved to be a valid distance measure.
<dig>  our measures are applied to extensive tests, e.g., protein sequence classification and phylogenetic analysis.
the performances of our measures are compared with alignment-based measures and the existing statistical measures.
through the experiments, we want to address the following questions with the aid of well known statistical index:  how well our statistical measures perform compared with the existing statistical measures and alignment-based ones;  which statistical measure performs better when exploring the information on protein 'sequence space';  whether the classification abilities of statistical measures depend on the choice of score matrices;  whether our measure, gdis.k, is a valid distance measure for phylogenetic analysis.
RESULTS
classification of protein sequences
the proposed statistical measures are used to classify protein sequences.
several benchmark data sets of non-homologous protein structures have been developed in the last few years  <cit> .
in this study, we have chosen the  <dig> protein domains of  <cit> , the rost and sander data set  and the  <dig> prototype protein domains of  <cit> .
the chew-kedem data set  was introduced in  <cit>  and further studied in  <cit> .
it consists of  <dig> protein domains drawn from pdb entries of three classes .
although this data set has been extensively used, the main draw back of this data is small size and high redundant.
the rost and sander data set   was designed for the secondary structure prediction of proteins with a pair-wise sequence similarity of less than 25%  <cit> , and it was used as a test data to evaluate the performances of similarity measures  <cit> .
here, we not only compare the proteins' secondary structures, but analyse the performance of similarity measures according to the proteins' classification as given by scop, release  <dig>   <cit> .
we adopt this manually curated database as our gold standard containing expert knowledge for class level.
this data set is trimmed to exclude sequences belonging to classes with < <dig> elements, thus a data set of  <dig> protein sequences, denoted by rs, is obtained.
the sierk-pearson data set , which consists of a non-redundant subset of  <dig> protein families and  <dig> non-homologous protein families from the cath protein domain database  <cit> , was introduced in  <cit> .
we estimate the homology of the data by employing cd-hit program, which clusters protein databases at given sequence homology threshold  <cit> .
running cd-hit with 70% homology threshold reveals that there are  <dig>   <dig>   <dig> sequences for data ck, rs and sp, respectively, below the homology threshold.
this results clearly indicate that ck is high redundant, rs is low redundant, and sp is less redundant.
the experiments aim at evaluating the classification ability of the alignment-based measures and the statistical measures.
the evaluation procedure is based on a binary classification of each protein pair, where  <dig> corresponds to the two protein sequences sharing the same class,  <dig> otherwise.
given a data with size n, a n × n similarity/distance matrix can be obtained via each measure.
the entries of the upper triangular similarity/distance matrix constitute a similarity vector of length , which is used as prediction.
also, we can get a vector of length  consisted of  <dig> and  <dig> as class labels.
a perfect measure would completely separate negative from positive set.
of course, this does not happen in practice, and the classes are interspersed.
the roc curves permit to assess the level of accuracy of this separation without choosing any distance threshold for the separation point.
in particular, the auc will give us a unique number of the relative accuracy of each measure.
the measures evaluated are: alignment-based measures, our statistical measures  and the six statistical measures outlined in method section , where the alignment-based measures are clustal x, needleman-wunsch  or smith-waterman  raw scores, with no correction for statistical significance, using ten score matrices  and linear gap penalties or affine gap penalties, with a gap penalty of  <dig>  all statistical measures based on k-word frequencies of protein sequence and protein 'sequence space' run with k from  <dig> to  <dig>  where protein 'sequence space' is constructed based on the score matrix .
for each measure, separate tests are done with each combination of parameter values, and the best combination is chosen to represent the score in the performance.
roc curves are computed to evaluate and compare the performances of our methods and other similarity measures.
the roc curves obtained for the classifications are presented in figures  <dig>   <dig>   <dig>  figure  <dig>  figure  <dig> and figure  <dig> denote the roc curves of alignment-based measures and the statistical measures based on k-word frequencies of protein sequences.
figure  <dig>  figure  <dig> and figure  <dig> denote the roc curves of alignment-based measures and the statistical measures based on k-word frequencies of protein 'sequence space'.
the better similarity measures have plots with higher values of sensitivity for equal values of specificity, resulting in higher values for the areas under the curves.
the auc value is typically used as a measure of overall discrimination accuracy.
table  <dig> provides the areas under roc curves  obtained from all the similarity measures for data sets ck, rs and sp.
k-word fpsa
k-word fpsa
k-word fpsa
k-word fpssb
k-word fpssb
k-word fpssb
the comparison of the areas under roc curves  obtained from all the similarity measures for data ck, rs and sp.
k-word fpsa denotes the k-word frequencies of protein sequences.
k-word fpssb denotes the k-word frequencies of protein 'sequence space'.
all the abbreviations of similarity measures are illustrated in the "list of abbreviations" section.
question a
in the ck experiment, figure  <dig> and table  <dig> show that alignment-based measures perform better than alignment-free measures.
nw-affine.b <dig> outperforms other alignment-based measures, its area under roc curve is  <dig> .
among the statistical measures based on k-word frequencies of protein sequences, gsm.
<dig> is clearly more efficient than other measures.
its area under roc curve is  <dig> .
the next best measure is the cos. <dig>  with the area under roc curve  <dig> , and the other measures lag behind.
for the statistical measures based on k-word frequencies of protein 'sequence space', gsm.
<dig> b <dig> is significantly better than other statistical measures, the se.
<dig> b <dig> followed.
in the rs experiment, figure  <dig> and table  <dig> indicate that some statistical measures perform as well as alignment-based measures.
by exploring the information on protein 'sequence space', the statistical measure, gsm.k, performs better than alignment-base measures.
for the alignment-based measures, nw-affine.b <dig> performs better than other measures.
as for the statistical measures based on k-word frequencies of protein sequences, cos. <dig> outperforms the other measures.
among the statistical measures based on k-word frequencies of protein 'sequence space', gsm.
<dig> b <dig> is significantly better than all other measures, its area under roc curve is  <dig> , and the next best measure is gre.
<dig> b <dig>
in the sp experiment, figure  <dig> and table  <dig> illustrate that some statistical measures defined by k-word frequencies of protein sequences outperform alignment-based measures.
when the information on protein 'sequence space' is added, all the statistical measures, except for se.k and s <dig> k, perform better than alignment-base measures.
for the alignment-based measures, sw measures perform better than nw measures.
as for the statistical measures based on k-word frequencies of protein sequences, gre.
<dig> outperforms other measures, which is followed by cos. <dig> and eu.
<dig>  among the statistical measures based on k-word frequencies of protein 'sequence space', the area under roc curve of gre.
<dig> p <dig> is  <dig> , better than other statistical measures, and the next best measures are the cos. <dig> p <dig> and eu.
<dig> p <dig>
from the above three experiments, we can see that alignment-based measures have a clear advantage when the data is high redundant.
the most efficient statistical measure is the novel gsm.k introduced by this report.
when the data becomes less redundant, gre.k proposed by us achieves a better performance, but all the alignment-based and the existing measures perform poorly on all classification tasks.
the inspection of the roc curves themselves  further illustrates these comparisons between similarity measures.
question b
the main goal of construction of protein 'sequence space' is to improve the classification ability of similarity measures by extracting the information on related protein sequences.
however, it should be noted that not all the similarity measures are suitable for this scheme.
in order to find which statistical measure is suitable for this scheme, we define a function dauc  to evaluate whether the classification ability of similarity measures improve or not,
dauc =auc −auc ,
where auc  denotes the area under roc curve of the statistical measure based on the k-word frequencies of protein 'sequence space', which is constructed based on the score matrix; auc  denotes the area under roc curve of measure defined by the k-word frequencies of protein sequence.
judging from definition of dauc, it is easier to recognize that if dauc ≥  <dig>  utilizing protein 'sequence space' improves the classification ability of the similarity measures.
the dauc values for the data ck, rs and sp are presented in figures  <dig>   <dig>   <dig>
as would be expected, the dauc values of the different measures  show two clear trends:  the dauc values increase from k =  <dig> to k =  <dig> for all three data sets.
when the length of word is equal to  <dig>  almost all the statistical measures' classification abilities are improved.
it should be noted that the classification discrimination of statistical measures based on higher order word frequencies, such as eu.k, se.k and cos.k, worsens  <cit> , because the high dimension of the frequency vectors and the relative low dimension of the sequences length itself cause the frequency vector f to be very sparse.
interestingly, the construction of protein 'sequences space' maintains the accuracy and overcomes the difficulty arising from higher order word;  it is interesting to note that there is a dependency between usefulness of protein 'sequence space' and the level of data's redundant.
when the data is high redundant such as ck, the 'sequence space' is more similar.
consequently, the similarity measures based on 'sequence space' achieve a little improvement ).
but the accuracy of classification is also improved with word's length increasing.
as for the less redundant data such as rs and sp, all the statistical measures based on 'sequence space' achieve significantly improvement when word's length increases to  <dig> ).
question c
using protein 'sequence space' contributes to the accuracy of protein classification.
however, the construction of protein 'sequence space' relies heavily on the score matrix.
in order to evaluate the influence of different score matrices, the function mauc is defined by
mauc=max1≤k≤4),
where auc  denotes the area under roc curve of the statistical measure based on the k-word frequencies of protein 'sequence space' that is built based on the score matrix.
the mauc values of all the statistical measures based on ten score matrices for three data sets are presented in figure  <dig>  figure  <dig> largely confirms that the measures possess different performances based on different score matrices.
the changes of dauc for the data ck, rs and sp are similar.
for blosum score matrix, blosum <dig> and blosum <dig> perform better in improvement of the statistical measures' classification abilities.
as for pam score matrix, pam <dig> or pam <dig> improves the classification ability of all the similarity measures on the high redundant data more obviously, except for the measures eu.k and gre.k.
pam <dig> or pam <dig> contributes to improve the classification ability of the similarity measures more obviously on the less redundant data.
phylogenetic analysis
since gdis.k is a statistical distance measure, it is further tested to analyze phylogenetic relationships.
given a set of protein sequences, their phylogenetic relationships can be obtained through the following main operations: firstly, the k-word frequencies of protein 'sequence space' are calculated; secondly, the statistical distances are calculated and arranged into a distance matrix; finally, the phylogenetic relationships is obtained by neighbor-joining program in the phylip package  <cit> .
a data set includes  <dig> smc proteins,  <dig> rad <dig> proteins and  <dig> mukb proteins , which have been widely studied  <cit> .
our distance measure is applied to this data, and the results are shown in figure  <dig>  to assess the robustness of an estimated tree under perturbations of the input alignment, it is customary to perform a bootstrap analysis, where entire columns of the alignment are resampled with replacement.
the bootstrap technique is employed to evaluate the tree topologies by resampling the sequence  <dig> times.
we obtain the phylogenetic relationships drawn by mega program  <cit> , bootstrap values, lower than  <dig>  are hidden.
generally, an independent method can be developed to evaluate the accuracy of phylogenetic relationships, or the validity of phylogenetic relationships can be tested by comparing it with authoritative ones.
here, we adopt the latter one to test the validity of our measure.
question d
our results are quite consistent with the accepted taxonomy and authoritative ones  <cit>  in the following three aspects.
first of all, all the organisms are clearly separated from each other.
among the smc proteins, it is consistently observed that smc <dig> and smc <dig> are grouped closely , and the smaller subunits, smc <dig> and smc <dig>  appear to group closely.
smc <dig> and smc <dig> are grouped together, which is consonant with that they heterodimerize as part of a dna repair complex  <cit> .
secondly, it is obvious from this tree that the closest relatives to the smc proteins are the rad <dig> proteins, followed by mukb proteins.
many of these rad <dig> superfamily proteins have the conserved n-terminal fks  motif , which is presented in most of the smc proteins  <cit> .
finally, among the smc proteins, it is observed that smc <dig> protein and smc <dig> protein are closer to smc proteins, followed by smc <dig>  smc <dig>  smc <dig> and smc <dig>  <cit> .
it suggests that the duplication events giving rise to each subfamily must have occurred either before or very soon after the origin of eukaryotes.
since the rate of accepted amino acid substitution varies among different eukaryotic taxa within each subfamily.
condensin smcs appear to show a higher substitution than cohesin smcs, the mean distances within subfamilies of these proteins  are about half  the corresponding distances between smc <dig> and smc <dig> proteins  <cit> .
these reasonable results confirm that gdis.k is a reliable distance measure for phylogenetic analysis.
CONCLUSIONS
prior to this research, the statistical measures are perceived as adequate for analysis of biological data mainly because of their flexibility and scalability with data set size.
in particular, some of them are quantitatively compared for the recognition of scop relationships  <cit> .
this article presents a novel way to compare protein sequences by exploring the information on 'sequence space' and two new statistical measures: gre.k and gsm.k.
it offers the first systematic and quantitative experimental assessment of statistical measures based on protein sequence and protein 'sequence space', which naturally complements the many available comparisons based on protein sequences.
the accuracy of each similarity measure to classify protein sequence is assessed through the experiments on high redundant and less redundant data sets.
the comparative index auc is a good measure of overall accuracy of a classification scheme.
the proposed statistical distance measure, gdis.k, is further tested to analyze phylogenetic relationships.
as for the high redundant data, alignment-based measures have a clear advantage.
gsm.k, followed by cos.k, is clearly more efficient among the existing statistical measures .
when the data becomes less redundant, all the statistical measures, except for se.k and s <dig> k, outperform the alignment-based measures by exploring the information on protein 'sequence space', and gre.k proposed by us achieves the best performance .
the scheme for constructing 'sequence space' can provide more information than the protein sequence only and contributes to the accuracy of protein classification, especially for the less redundant data sets such as rs and sp.
almost all the statistical measures based on 'sequence space' achieve significantly improvement when word's length increases to  <dig> .
in addition, the reasonable results of phylogenetic analysis illustrate the validity of our distance measure for phylogenetic analysis.
overall our comparison study highlights the necessity for alignment-free measures to extract more information as possible.
thus, this understanding can then be used to guide development of more powerful measures for protein sequence comparison with future possible improvement on evolutionary, structure and function study.
but, it is worthy to note that although exploring the information on 'sequence space' improves the classification ability of some similarity measures, they all perform very poorly, near random classification values of  <dig>  for less redundant data.
that is to say, they may be useless in practice.
so we expect a further investigation on the statistical methods, especially for low redundant datasets

 over the past few decades, major advances in the field of molecular biology, coupled with advances in genomic technologies, have led to an explosive growth of biological sequences databases. for example, there are several well-known databases about protein: pfam, scop, swiss-prot, and protein information resource. this deluge of databases, in turn, produces new questions to analyze protein sequences such as how to classify protein sequences, induce their evolutionary information, and predict their structures. among protein sequence analysis, some important computational methods are similarity search, phylogenetic analysis and sequence classification. the similarity search is to search a database of known function sequences and uses the structures and functions of the most closely matched known sequences to analyze the structure and function of query sequence. phylogenetic analysis is the study of the evolutionary history among species. it can also provide useful information for pharmaceutical researchers to determine which species share the medicinal qualities. classification protein is to get a biologically meaningful partition. it has several advantages: when proteins are grouped into a family, it can provide us some clues about the general features of this family and evolutionary evidence of proteins, and further infer the biological function of a new sequence by its similarity to some function-known sequences. moreover, protein classification can be used to facilitate protein three-dimensional structure discovery, which is very important for understanding proteins' functions. however, these computational methods heavily rely on the similarity measures defined among biological sequences. because of the importance of research into similarity measures, numerous efficient algorithms have been developed, but challenges remain. moreover, we believe that further improvements in the similarity measures will allow us to design more effective tools, which can help us to look back more deeply in evolutionary time. one kind of the most common dissimilarity measures in this area is edit distance by aligning two sequences. it is defined as the required number of insertions, deletions, and replacements of characters from the first protein sequence to obtain the second protein sequence. but this measure is encountered with difficulties: computation with regard to large biological databases; the score schemes chosen. therefore, alignment-free measures are actively pursued to overcome the limitations of protein analysis by alignment. up to now, many efficient alignment-free measures for sequences comparison have been proposed, but they are still in the early development compared with alignment-based methods. one of the comprehensive reviews reported several concepts of similarity measures, such as euclidean distance, mahalanobis distances, kullback-leibler discrepancy, cosine distance and pearson's correlation coefficient. recently, several novel alignment-free measures have been designed for protein sequences analysis, such as s and s, w-metric, universal similarity metric, local decoding, cluss and long short-term memory. among the statistical measures, each sequence is mapped into an n-dimensional vector according to its k-word frequencies. linear algebra theory is further employed to define the similarity score between sequences represented in vector spaces. the kld extended by wu et al. is computed in terms of two vectors of relative frequencies of k-words over a sliding window from two given dna sequences. however, in an application where some entries of vectors are equal to or kld becomes unsuitable. in this paper, we present two statistical measures to overcome the limitation of the measure kld. the contents can be summarized as follows: we present a scheme to build protein'sequence space' based on the score or amino acid substitution matrices and calculate k-word frequencies of protein'sequence space'. two statistical measures gre.k and gsm.k, as the extended jensen-shannon divergence, are proposed. they are based on k-word frequencies and jensen-shannon divergence. although these two concepts are not new, their generalizations result in the novel aspect of these measures. particularly, the statistical measure, gdis.k, is proved to be a valid distance measure. our measures are applied to extensive tests, e.g., protein sequence classification and phylogenetic analysis. the performances of our measures are compared with alignment-based measures and the existing statistical measures. through the experiments, we want to address the following questions with the aid of well known statistical index: how well our statistical measures perform compared with the existing statistical measures and alignment-based ones; which statistical measure performs better when exploring the information on protein'sequence space'; whether the classification abilities of statistical measures depend on the choice of score matrices; whether our measure, gdis.k, is a valid distance measure for phylogenetic analysis.  classification of protein sequences the proposed statistical measures are used to classify protein sequences. several benchmark data sets of non-homologous protein structures have been developed in the last few years. in this study, we have chosen the protein domains of, the rost and sander data set and the prototype protein domains of. the chew-kedem data set was introduced in and further studied in. it consists of protein domains drawn from pdb entries of three classes. although this data set has been extensively used, the main draw back of this data is small size and high redundant. the rost and sander data set was designed for the secondary structure prediction of proteins with a pair-wise sequence similarity of less than 25%, and it was used as a test data to evaluate the performances of similarity measures. here, we not only compare the proteins' secondary structures, but analyse the performance of similarity measures according to the proteins' classification as given by scop, release. we adopt this manually curated database as our gold standard containing expert knowledge for class level. this data set is trimmed to exclude sequences belonging to classes with < elements, thus a data set of protein sequences, denoted by rs, is obtained. the sierk-pearson data set, which consists of a non-redundant subset of protein families and non-homologous protein families from the cath protein domain database, was introduced in. we estimate the homology of the data by employing cd-hit program, which clusters protein databases at given sequence homology threshold. running cd-hit with 70% homology threshold reveals that there are sequences for data ck, rs and sp, respectively, below the homology threshold. this results clearly indicate that ck is high redundant, rs is low redundant, and sp is less redundant. the experiments aim at evaluating the classification ability of the alignment-based measures and the statistical measures. the evaluation procedure is based on a binary classification of each protein pair, where corresponds to the two protein sequences sharing the same class, otherwise. given a data with size n, a n × n similarity/distance matrix can be obtained via each measure. the entries of the upper triangular similarity/distance matrix constitute a similarity vector of length, which is used as prediction. also, we can get a vector of length consisted of and as class labels. a perfect measure would completely separate negative from positive set. of course, this does not happen in practice, and the classes are interspersed. the roc curves permit to assess the level of accuracy of this separation without choosing any distance threshold for the separation point. in particular, the auc will give us a unique number of the relative accuracy of each measure. the measures evaluated are: alignment-based measures, our statistical measures and the six statistical measures outlined in method section, where the alignment-based measures are clustal x, needleman-wunsch or smith-waterman raw scores, with no correction for statistical significance, using ten score matrices and linear gap penalties or affine gap penalties, with a gap penalty of all statistical measures based on k-word frequencies of protein sequence and protein'sequence space' run with k from to where protein'sequence space' is constructed based on the score matrix. for each measure, separate tests are done with each combination of parameter values, and the best combination is chosen to represent the score in the performance. roc curves are computed to evaluate and compare the performances of our methods and other similarity measures. the roc curves obtained for the classifications are presented in figures figure figure and figure denote the roc curves of alignment-based measures and the statistical measures based on k-word frequencies of protein sequences. figure figure and figure denote the roc curves of alignment-based measures and the statistical measures based on k-word frequencies of protein'sequence space'. the better similarity measures have plots with higher values of sensitivity for equal values of specificity, resulting in higher values for the areas under the curves. the auc value is typically used as a measure of overall discrimination accuracy. table provides the areas under roc curves obtained from all the similarity measures for data sets ck, rs and sp. k-word fpsa k-word fpsa k-word fpsa k-word fpssb k-word fpssb k-word fpssb the comparison of the areas under roc curves obtained from all the similarity measures for data ck, rs and sp. k-word fpsa denotes the k-word frequencies of protein sequences. k-word fpssb denotes the k-word frequencies of protein'sequence space'. all the abbreviations of similarity measures are illustrated in the "list of abbreviations" section. question a in the ck experiment, figure and table show that alignment-based measures perform better than alignment-free measures. nw-affine.b outperforms other alignment-based measures, its area under roc curve is. among the statistical measures based on k-word frequencies of protein sequences, gsm. is clearly more efficient than other measures. its area under roc curve is. the next best measure is the cos. with the area under roc curve, and the other measures lag behind. for the statistical measures based on k-word frequencies of protein'sequence space', gsm. b is significantly better than other statistical measures, the se. b followed. in the rs experiment, figure and table indicate that some statistical measures perform as well as alignment-based measures. by exploring the information on protein'sequence space', the statistical measure, gsm.k, performs better than alignment-base measures. for the alignment-based measures, nw-affine.b performs better than other measures. as for the statistical measures based on k-word frequencies of protein sequences, cos. outperforms the other measures. among the statistical measures based on k-word frequencies of protein'sequence space', gsm. b is significantly better than all other measures, its area under roc curve is, and the next best measure is gre. b in the sp experiment, figure and table illustrate that some statistical measures defined by k-word frequencies of protein sequences outperform alignment-based measures. when the information on protein'sequence space' is added, all the statistical measures, except for se.k and s k, perform better than alignment-base measures. for the alignment-based measures, sw measures perform better than nw measures. as for the statistical measures based on k-word frequencies of protein sequences, gre. outperforms other measures, which is followed by cos. and eu. among the statistical measures based on k-word frequencies of protein'sequence space', the area under roc curve of gre. p is, better than other statistical measures, and the next best measures are the cos. p and eu. p from the above three experiments, we can see that alignment-based measures have a clear advantage when the data is high redundant. the most efficient statistical measure is the novel gsm.k introduced by this report. when the data becomes less redundant, gre.k proposed by us achieves a better performance, but all the alignment-based and the existing measures perform poorly on all classification tasks. the inspection of the roc curves themselves further illustrates these comparisons between similarity measures. question b the main goal of construction of protein'sequence space' is to improve the classification ability of similarity measures by extracting the information on related protein sequences. however, it should be noted that not all the similarity measures are suitable for this scheme. in order to find which statistical measure is suitable for this scheme, we define a function dauc to evaluate whether the classification ability of similarity measures improve or not, dauc =auc −auc, where auc denotes the area under roc curve of the statistical measure based on the k-word frequencies of protein'sequence space', which is constructed based on the score matrix; auc denotes the area under roc curve of measure defined by the k-word frequencies of protein sequence. judging from definition of dauc, it is easier to recognize that if dauc ≥ utilizing protein'sequence space' improves the classification ability of the similarity measures. the dauc values for the data ck, rs and sp are presented in figures as would be expected, the dauc values of the different measures show two clear trends: the dauc values increase from k = to k = for all three data sets. when the length of word is equal to almost all the statistical measures' classification abilities are improved. it should be noted that the classification discrimination of statistical measures based on higher order word frequencies, such as eu.k, se.k and cos.k, worsens, because the high dimension of the frequency vectors and the relative low dimension of the sequences length itself cause the frequency vector f to be very sparse. interestingly, the construction of protein'sequences space' maintains the accuracy and overcomes the difficulty arising from higher order word; it is interesting to note that there is a dependency between usefulness of protein'sequence space' and the level of data's redundant. when the data is high redundant such as ck, the'sequence space' is more similar. consequently, the similarity measures based on'sequence space' achieve a little improvement ). but the accuracy of classification is also improved with word's length increasing. as for the less redundant data such as rs and sp, all the statistical measures based on'sequence space' achieve significantly improvement when word's length increases to ). question c using protein'sequence space' contributes to the accuracy of protein classification. however, the construction of protein'sequence space' relies heavily on the score matrix. in order to evaluate the influence of different score matrices, the function mauc is defined by mauc=max1≤k≤4), where auc denotes the area under roc curve of the statistical measure based on the k-word frequencies of protein'sequence space' that is built based on the score matrix. the mauc values of all the statistical measures based on ten score matrices for three data sets are presented in figure figure largely confirms that the measures possess different performances based on different score matrices. the changes of dauc for the data ck, rs and sp are similar. for blosum score matrix, blosum and blosum perform better in improvement of the statistical measures' classification abilities. as for pam score matrix, pam or pam improves the classification ability of all the similarity measures on the high redundant data more obviously, except for the measures eu.k and gre.k. pam or pam contributes to improve the classification ability of the similarity measures more obviously on the less redundant data. phylogenetic analysis since gdis.k is a statistical distance measure, it is further tested to analyze phylogenetic relationships. given a set of protein sequences, their phylogenetic relationships can be obtained through the following main operations: firstly, the k-word frequencies of protein'sequence space' are calculated; secondly, the statistical distances are calculated and arranged into a distance matrix; finally, the phylogenetic relationships is obtained by neighbor-joining program in the phylip package. a data set includes smc proteins, rad proteins and mukb proteins, which have been widely studied. our distance measure is applied to this data, and the results are shown in figure to assess the robustness of an estimated tree under perturbations of the input alignment, it is customary to perform a bootstrap analysis, where entire columns of the alignment are resampled with replacement. the bootstrap technique is employed to evaluate the tree topologies by resampling the sequence times. we obtain the phylogenetic relationships drawn by mega program, bootstrap values, lower than are hidden. generally, an independent method can be developed to evaluate the accuracy of phylogenetic relationships, or the validity of phylogenetic relationships can be tested by comparing it with authoritative ones. here, we adopt the latter one to test the validity of our measure. question d our results are quite consistent with the accepted taxonomy and authoritative ones in the following three aspects. first of all, all the organisms are clearly separated from each other. among the smc proteins, it is consistently observed that smc and smc are grouped closely, and the smaller subunits, smc and smc appear to group closely. smc and smc are grouped together, which is consonant with that they heterodimerize as part of a dna repair complex. secondly, it is obvious from this tree that the closest relatives to the smc proteins are the rad proteins, followed by mukb proteins. many of these rad superfamily proteins have the conserved n-terminal fks motif, which is presented in most of the smc proteins. finally, among the smc proteins, it is observed that smc protein and smc protein are closer to smc proteins, followed by smc smc smc and smc. it suggests that the duplication events giving rise to each subfamily must have occurred either before or very soon after the origin of eukaryotes. since the rate of accepted amino acid substitution varies among different eukaryotic taxa within each subfamily. condensin smcs appear to show a higher substitution than cohesin smcs, the mean distances within subfamilies of these proteins are about half the corresponding distances between smc and smc proteins. these reasonable results confirm that gdis.k is a reliable distance measure for phylogenetic analysis.  prior to this research, the statistical measures are perceived as adequate for analysis of biological data mainly because of their flexibility and scalability with data set size. in particular, some of them are quantitatively compared for the recognition of scop relationships. this article presents a novel way to compare protein sequences by exploring the information on'sequence space' and two new statistical measures: gre.k and gsm.k. it offers the first systematic and quantitative experimental assessment of statistical measures based on protein sequence and protein'sequence space', which naturally complements the many available comparisons based on protein sequences. the accuracy of each similarity measure to classify protein sequence is assessed through the experiments on high redundant and less redundant data sets. the comparative index auc is a good measure of overall accuracy of a classification scheme. the proposed statistical distance measure, gdis.k, is further tested to analyze phylogenetic relationships. as for the high redundant data, alignment-based measures have a clear advantage. gsm.k, followed by cos.k, is clearly more efficient among the existing statistical measures. when the data becomes less redundant, all the statistical measures, except for se.k and s k, outperform the alignment-based measures by exploring the information on protein'sequence space', and gre.k proposed by us achieves the best performance. the scheme for constructing'sequence space' can provide more information than the protein sequence only and contributes to the accuracy of protein classification, especially for the less redundant data sets such as rs and sp. almost all the statistical measures based on'sequence space' achieve significantly improvement when word's length increases to. in addition, the reasonable results of phylogenetic analysis illustrate the validity of our distance measure for phylogenetic analysis. overall our comparison study highlights the necessity for alignment-free measures to extract more information as possible. thus, this understanding can then be used to guide development of more powerful measures for protein sequence comparison with future possible improvement on evolutionary, structure and function study. but, it is worthy to note that although exploring the information on'sequence space' improves the classification ability of some similarity measures, they all perform very poorly, near random classification values of for less redundant data. that is to say, they may be useless in practice. so we expect a further investigation on the statistical methods, especially for low redundant datasets 
given a protein sequence, the information on its related protein sequences hasn't been used for protein sequence comparison until now. the reasonable results of phylogenetic analysis confirm that gdis.k based on'sequence space' is a reliable measure for phylogenetic analysis. they share the same idea of using k-word frequencies of protein sequences. this paper proposed a scheme to construct protein'sequence space' which was associated with protein sequences related to the given protein, and the performances of statistical measures were compared when they explored the information on protein'sequence space' or not. the first one, performed via roc analysis, aims at assessing the intrinsic ability of the statistical measures to discriminate and classify protein sequences. the more efficient statistical measure is the novel gsm.k introduced by this article, the cos.k followed. based on the experiments, several conclusions can be drawn and, from them, novel valuable guidelines for the use of protein'sequence space' and statistical measures were obtained. when the data becomes less redundant, gre.k proposed by us achieves a better performance, but all the other measures perform poorly on classification tasks. this not only offers the systematic and quantitative experimental assessment of these statistical measures, but also naturally complements the available comparison of statistical measures based on protein sequence. alignment-based measures have a clear advantage when the data is high redundant. we tested statistical measures based on protein'sequence space' or not with three data sets. almost all the statistical measures achieve improvement by exploring the information on'sequence space' as word's length increases, especially for less redundant data. in summary, our quantitative analysis verifies that exploring the information on'sequence space' is a promising way to improve the abilities of statistical measures for protein comparison. many proposed statistical measures can efficiently compare protein sequence to further infer protein structure, function and evolutionary information. this paper also presented two statistical measures for protein: gre.k and gsm.k. moreover, we compared our statistical measures with alignment-based measures and the existing statistical measures. the second set of the experiments aims at assessing how well our measure does in phylogenetic analysis.
 many proposed statistical measures can efficiently compare protein sequence to further infer protein structure, function and evolutionary information. they share the same idea of using k-word frequencies of protein sequences. given a protein sequence, the information on its related protein sequences hasn't been used for protein sequence comparison until now. this paper proposed a scheme to construct protein'sequence space' which was associated with protein sequences related to the given protein, and the performances of statistical measures were compared when they explored the information on protein'sequence space' or not. this paper also presented two statistical measures for protein: gre.k and gsm.k.  we tested statistical measures based on protein'sequence space' or not with three data sets. this not only offers the systematic and quantitative experimental assessment of these statistical measures, but also naturally complements the available comparison of statistical measures based on protein sequence. moreover, we compared our statistical measures with alignment-based measures and the existing statistical measures. the experiments were grouped into two sets. the first one, performed via roc analysis, aims at assessing the intrinsic ability of the statistical measures to discriminate and classify protein sequences. the second set of the experiments aims at assessing how well our measure does in phylogenetic analysis. based on the experiments, several conclusions can be drawn and, from them, novel valuable guidelines for the use of protein'sequence space' and statistical measures were obtained.  alignment-based measures have a clear advantage when the data is high redundant. the more efficient statistical measure is the novel gsm.k introduced by this article, the cos.k followed. when the data becomes less redundant, gre.k proposed by us achieves a better performance, but all the other measures perform poorly on classification tasks. almost all the statistical measures achieve improvement by exploring the information on'sequence space' as word's length increases, especially for less redundant data. the reasonable results of phylogenetic analysis confirm that gdis.k based on'sequence space' is a reliable measure for phylogenetic analysis. in summary, our quantitative analysis verifies that exploring the information on'sequence space' is a promising way to improve the abilities of statistical measures for protein comparison. 