BACKGROUND
the increasing proliferation of biological sequence data has created tremendous opportunities for biologists and medical researchers to address both fundamental issues  and practical problems .
on the other hand, it poses many computational challenges for theoretical scientists to create efficient and reliable methods or algorithms for sequence analyses and knowledge mining.
sequence comparison, an essential operation for gene finding and protein function annotation, is one such challenge.
the methods for sequence comparison are classified into two categories, alignment-based and alignment-free.
the alignment-based sequence analysis methods have both fundamental and computational limitations  <cit> .
for example, these methods cannot deal with changes like chromosome reversal or gene translocation.
they also encounter difficulties in aligning dissimilar sequences.
another drawback with sequence alignment is its computational complexity, where no optimal solution can be achieved when a large number of sequences are compared.
consequently, considerable efforts have been made to seek for alternative, i.e., alignment-free, methods for sequence comparison.
the alignment-free methods seen in the past few decades can be divided into three categories: gene contents  <cit> , data compression  <cit> , and string  composition  <cit> .
of these methods, the string-composition-based methods, especially the composition vector  method  <cit>  and the complete composition vector  method  <cit> , have received substantial attention.
the cv method uses strings of a fixed length whereas the ccv method uses strings of multiple lengths.
the ccv method was found to provide finer evolutionary information than the cv method; however, it has disadvantages regarding computing time and memory usage.
both of the above mentioned methods apply a markov model assumption to estimate the random background of observed frequencies, which has been found to be problematic, as detailed in section  <dig>  in this paper, we will provide an improved ccv  method and demonstrate that this new method is more robust and efficient in performing sequence comparison compared with the existing ccv method.
the issue of how to build a more informative ccv, i.e., how to select the maximum vector string length for better evolutionary information representation, will be addressed as well.
the contents of this paper are arranged as follows.
in the methods section, we point out the two aforementioned problems in the existing cv or ccv methods and describe our new iccv method.
in the results section, we compare the ccv and iccv methods through simulations and experimental data analysis.
in the discussion section, we discuss the potential impact of the simple assumption of a uniform and independent model and issues related to selecting the maximum string length for ccv construction.
methods
existing cv and ccv methods
define s as a dna sequence consisting of n nucleotides.
let f be the observed frequency of the k-mer string α <dig> ..αk, where αi is one of the four nucleotides a, c, t, or g and k is the string length .
we define sk= as a vector of observed frequencies for a given k, where 4k is the number of k-mer strings, and let γk =  as a combined vector for some constant k , where k is the maximum string length considered.
from the perspective of molecular evolution, sk or γk reflects both random mutation and selection, and the random background needs to be normalized in order to represent genetic information contributed by natural selection.
after the normalization of observed frequencies, sk is converted into a composition vector , and γk is transformed into a complete composition vector .
the method to normalize the observed frequencies of different k-mer strings in s was originally proposed by brendel et al.
<cit>  and has been used with minor modifications for phylogenetic studies of prokaryotes and viruses  <cit> .
we have found two problems associated with string frequency normalization in existing methods.
to explicate these problems, we reiterate the normalization equation of the observed frequency of α <dig> ..αk, i.e., f, described in  <cit>  as below:
a=f−f0f <dig>
where f0=fff.
<dig> for k ≥  <dig>
first, there is a positive correlation between the observed frequency f and the estimated expected frequency f <dig>  we computed both quantities for k =  <dig>   <dig>   <dig> using a randomly chosen virus sequence.
the correlation coefficients between f <dig> and f are  <dig> ,  <dig>  and  <dig> , respectively, for k =  <dig>   <dig>   <dig> with p <  <dig>  .
define e <dig> as the true expected frequency of k-mer string α <dig> ..αk in s. since there exists a highly positive correlation between f <dig> and f, the difference between them tends to be smaller than the difference between f and e <dig>  indicating the information contributed by selective evolution is underestimated.
another problem associated with eq.
<cit>  is the denominator.
as originally proposed in  <cit> , a square root needs to be applied to the denominator.
without such an operation, the normalized frequency tends to be over-standardized.
improved ccv  method
we assume that the four bases a, c, t, and g occur randomly with equal chance and derive the expected frequency of a k-mer string and the frequency variance in a given sequence s based upon this simple assumption.
define xi as follows:
xi={ <dig> if the k-mer string begins at position i <dig> otherwise,
where i =  <dig>   <dig>   <dig>  ..., n - k +  <dig> and n - k +  <dig> is the maximum frequency one can observe for string α <dig> ..αk in dna sequence s of length n. therefore, it can be shown that f=∑i=1n−k+1xi.
the expectation and variance of f are given as
e=∑i=1n−k+1e=n−k+14k,
and
var=4k−242k+24k∑t=1k−1jt4t,
where jt={ <dig>   if = f−evar,
for k ≥  <dig>
we construct an improved ccv  with the normalized frequencies of all k-mer strings computed using eq.
<cit> .
since e is a theoretical value based on n and k, it is independent of f for a fixed k. therefore, the iccv method we proposed does not experience the underestimation problem of the existing ccv methods.
another advantage of iccv over ccv is that iccv is constructed for any k but ccv is constructed for k >  <dig>  the latter neglects the evolutionary information contained in 1-mer and 2-mer strings.
distance measurement
let α =  and β =  be the ccv or the iccv of two dna sequences a and b, respectively.
to calculate d, the distance between a and b, we adopt a distance measurement in this paper as detailed below:
d=1−c <dig>
where c=∑i=1tai×bi1/ <dig>  c is the cosine of the angle between α and β.
data sets
to generate simulation data sets to compare the performance of the iccv and the ccv methods, we adopted a similar approach as in  <cit> .
in brief, an ancestor sequence was randomly picked from our influenza virus database; and the progeny sequences were derived through simulation using different types of mutations  and following a pre-defined tree topology .
six types of mutations at the rate of 9–15% were applied to generate a <dig> and a <dig> from a, and b <dig> and b <dig> from b. three types of mutations  at the rate of 2–5% were used to generate a <dig> from a and b <dig> from b. a total of  <dig> data sets were generated for phylogenetic analysis.
besides the simulated data sets, we used a real dataset to compare the iccv and the ccv methods.
fifty-four influenza a viral ha sequences were used.
each has approximately  <dig>  base pairs.
based upon alignment-based phylogenetic analyses, each sequence was assigned a clade number by the international h5n <dig> evolution working group   <cit> .
data analysis and visualization
statistical package r version  <dig> .
<dig> was used for programming and implementation of the ccv and iccv methods.
the trees were generated using the neighbor-joining program in the phylip  <dig> .
<dig> package.
the resulting phylogenetic trees were displayed with mega  <dig>
RESULTS
analysis of simulation data sets
both ccv and iccv trees for k =  <dig> show the same topology of six sequences, as shown in fig.
<dig>  however, the iccv tree provides much higher bootstrapping values in support of two major clades.
this indicates the iccv method is more robust in resolving phylogenetic relationships of remotely related clades than the existing ccv method.
application on influenza a virus lineage analysis
as shown in fig.
<dig>  iccv and ccv trees for k =  <dig> agree with each other in the clade designation , but at the sub-clade level it appears that the designation based on the iccv method is more convincing.
for example, it is logical to assign the viral strain dk/guangxi/13/ <dig> to sub-clade  <dig>  as shown in the iccv tree.
however, this is not the case when examining the ccv tree.
in addition, the positions of clade  <dig>  clade  <dig> and sub-clade  <dig> .
<dig> on the iccv tree are not the same as on the ccv tree.
when comparing trees generated from different methods, both the iccv tree and the tree constructed by the h5n <dig> working group have exactly the same topology, which suggests that the iccv method is more dependable than the existing ccv method.
discussion
does the uniform and independent assumption matter?
as we can envision, the only potential weakness associated with the iccv method is the assumption of a uniform and independent model.
it has been shown that the null hypothesis of equiprobable occurrence of different nucleotides is reasonable in the context of the dna structures that have evolved from a "primordial soup' or 'base pool' containing equal quantities of each base  <cit> .
sege and saxberg   <cit>  have discussed this issue thoroughly.
the hypothesis of independent occurrence of different nucleotides has also been accepted in numerous situations, particularly in the analysis of relatively short strings  <cit> .
arritia et al.
<cit>  showed that the approximation of actual dependence in a dna sequence to the theory of independence of bases is quite good.
we used our influenza h5n <dig> virus sequence database to examine the assumptions of uniformity and independence.
chi-square tests reject that the four nucleotides a, c, t, and g occur in equal probabilites  or occur independently of one another .
although the assumption does not generally hold, both results from the analyses of simulated data and experimental data showed that our improved method is more robust than the existing ccv method, indicating that the violation of the assumption on base composition has no significant impact on the accuracy of the iccv method.
is increasing the maximum string length necessary?
wu et al.
<cit>  suggested that increasing the maximum string length results in a vector containing finer evolutionary information.
to investigate this issue, we used the same simulated sequences data as in section  <dig> , and constructed the iccv trees for k =  <dig>   <dig>   <dig>   <dig>   <dig>   <dig>   <dig> .
for the purpose of comparison, we also show the iccv tree for k =  <dig> from fig.
<dig>  in fig.
<dig>  it is clearly shown that as k increases from  <dig> to  <dig>  the supporting values significantly improve.
however, this trend declines as k increases from  <dig> to  <dig>  obviously, in this case, k =  <dig> or  <dig> is a cutoff point, which means increasing k after a certain number may not necessarily improve the result.
therefore, it might not be the case that increasing the maximum string length would result in a vector containing finer evolutionary information.
the reason for this is that the overlapping nature of strings with multiple lengths causes the overlap of evolutionary information carried by each individual cv.
as multiple cvs are combined into a complete cv, the complete cv collects the exclusive evolutionary information that each cv contains, but at the same time the overlapping information that individual cvs contain is also summed up.
therefore, increasing the string length k to a certain point will certainly improve the result, but the trend of improvement reaches its peak and afterwards declines.
the question is how to choose an optimal string length for construction of the ccv, which will be discussed next.
how to choose an optimal string length for the ccv
firstly, all the dna sequences in the dataset are concatenated into a single sequence w of length m, which provides an empirical nucleotide distribution for the class of sequences in the dataset.
then sk for w is computed.
since sk is the vector of observed frequencies of all the k-mer strings in w, skm−k+1=,q,...,qk) is the observed probability for all the k-mer strings.
as for a random sequence, the probability for all the k-mer strings is p=, where pi=14k for i =  <dig>   <dig> ...., 4k.
therefore, we can determine the difference between these two probability distributions by their kullback-leibler distance:
dk=∑i=14kqklog⁡2pi).
dk would be small if the two distributions are close to each other, which indicates that sk does not contain rich evolutionary information and should be excluded from calculating the iccvs.
to apply the above method to the experimental dataset in section  <dig> , we concatenated all  <dig> sequences in the experimental dataset into sequence a and calculated dk for k =  <dig>   <dig>  ...,  <dig>  similarly, we calculated dk for k =  <dig>   <dig>  ...,  <dig>  where b is a randomly generated sequence with the same length as sequence a. then we computed q=dkdk for k =  <dig>   <dig>  ....,  <dig> .
in fig.
<dig>  we can see that the magnitude of q is fairly large when k is small.
as k increases, q starts to decrease, and then it reaches a steady state at q =  <dig> when k is larger than  <dig>  the reason for this is that the effect of selective evolution is more significant on shorter strings than it is on longer strings.
therefore, dk is much larger than dk when k is small.
however, as k increases, the effect of selective evolution on k-mer strings starts to decline.
thus, the behavior of k-mer strings in sequence a becomes more similar to that of a random sequence and dk becomes closer to dk, which indicates that less evolutionary information is carried by sk.
for the experimental dataset, since q is fairly close to  <dig> when k is larger than  <dig>  an appropriate choice for the maximum  string length k would be  <dig>
CONCLUSIONS
in this paper, we show that the existing cv and ccv methods underestimate the evolutionary information contained in a dna sequence due to the markov model assumption and the denominator used for the normalization of observed string frequencies.
experiments using simulated and experimental data sets demonstrated that our iccv method generates more accurate and robust results compared with the currently used ccv method.
the consistency between the iccv tree and the alignment-based tree recommended by the international h5n <dig> evolution working group indicates that the iccv method is a valuable alternative to the alignment-based methods.
it is also shown that the violation of the assumption about base composition has no significant impact on the accuracy of the iccv method.
as to the issue related to maximum string length, we believe that it is not necessary to use relatively long strings to construct the ccv due to the overlapping nature of strings with variable length.
we suggest a practical approach for choosing the optimal string length for the ccv.
competing interests
the authors declare that they have no competing interests.
authors' contributions
gl conceived of the study, participated in the experimental design and implementation, and revised the manuscript.
sz conceived of the study, supervised the theoretical design of the improved method, and revised the manuscript.
xf participated in the experimental design and theoretical development of the method, carried out the implementation, and drafted the manuscript.
all authors read and approved the final manuscript.

 the increasing proliferation of biological sequence data has created tremendous opportunities for biologists and medical researchers to address both fundamental issues and practical problems. on the other hand, it poses many computational challenges for theoretical scientists to create efficient and reliable methods or algorithms for sequence analyses and knowledge mining. sequence comparison, an essential operation for gene finding and protein function annotation, is one such challenge. the methods for sequence comparison are classified into two categories, alignment-based and alignment-free. the alignment-based sequence analysis methods have both fundamental and computational limitations. for example, these methods cannot deal with changes like chromosome reversal or gene translocation. they also encounter difficulties in aligning dissimilar sequences. another drawback with sequence alignment is its computational complexity, where no optimal solution can be achieved when a large number of sequences are compared. consequently, considerable efforts have been made to seek for alternative, i.e., alignment-free, methods for sequence comparison. the alignment-free methods seen in the past few decades can be divided into three categories: gene contents, data compression, and string composition. of these methods, the string-composition-based methods, especially the composition vector method and the complete composition vector method, have received substantial attention. the cv method uses strings of a fixed length whereas the ccv method uses strings of multiple lengths. the ccv method was found to provide finer evolutionary information than the cv method; however, it has disadvantages regarding computing time and memory usage. both of the above mentioned methods apply a markov model assumption to estimate the random background of observed frequencies, which has been found to be problematic, as detailed in section in this paper, we will provide an improved ccv method and demonstrate that this new method is more robust and efficient in performing sequence comparison compared with the existing ccv method. the issue of how to build a more informative ccv, i.e., how to select the maximum vector string length for better evolutionary information representation, will be addressed as well. the contents of this paper are arranged as follows. in the methods section, we point out the two aforementioned problems in the existing cv or ccv methods and describe our new iccv method. in the results section, we compare the ccv and iccv methods through simulations and experimental data analysis. in the discussion section, we discuss the potential impact of the simple assumption of a uniform and independent model and issues related to selecting the maximum string length for ccv construction. methods existing cv and ccv methods define s as a dna sequence consisting of n nucleotides. let f be the observed frequency of the k-mer string α..αk, where αi is one of the four nucleotides a, c, t, or g and k is the string length. we define sk= as a vector of observed frequencies for a given k, where 4k is the number of k-mer strings, and let γk = as a combined vector for some constant k, where k is the maximum string length considered. from the perspective of molecular evolution, sk or γk reflects both random mutation and selection, and the random background needs to be normalized in order to represent genetic information contributed by natural selection. after the normalization of observed frequencies, sk is converted into a composition vector, and γk is transformed into a complete composition vector. the method to normalize the observed frequencies of different k-mer strings in s was originally proposed by brendel et al. and has been used with minor modifications for phylogenetic studies of prokaryotes and viruses. we have found two problems associated with string frequency normalization in existing methods. to explicate these problems, we reiterate the normalization equation of the observed frequency of α..αk, i.e., f, described in as below: a=f−f0f where f0=fff. for k ≥ first, there is a positive correlation between the observed frequency f and the estimated expected frequency f we computed both quantities for k = using a randomly chosen virus sequence. the correlation coefficients between f and f are, and, respectively, for k = with p <. define e as the true expected frequency of k-mer string α..αk in s. since there exists a highly positive correlation between f and f, the difference between them tends to be smaller than the difference between f and e indicating the information contributed by selective evolution is underestimated. another problem associated with eq. is the denominator. as originally proposed in, a square root needs to be applied to the denominator. without such an operation, the normalized frequency tends to be over-standardized. improved ccv method we assume that the four bases a, c, t, and g occur randomly with equal chance and derive the expected frequency of a k-mer string and the frequency variance in a given sequence s based upon this simple assumption. define xi as follows: xi={ if the k-mer string begins at position i otherwise, where i =..., n - k + and n - k + is the maximum frequency one can observe for string α..αk in dna sequence s of length n. therefore, it can be shown that f=∑i=1n−k+1xi. the expectation and variance of f are given as e=∑i=1n−k+1e=n−k+14k, and var=4k−242k+24k∑t=1k−1jt4t, where jt={   if = f−evar, for k ≥ we construct an improved ccv with the normalized frequencies of all k-mer strings computed using eq.. since e is a theoretical value based on n and k, it is independent of f for a fixed k. therefore, the iccv method we proposed does not experience the underestimation problem of the existing ccv methods. another advantage of iccv over ccv is that iccv is constructed for any k but ccv is constructed for k > the latter neglects the evolutionary information contained in 1-mer and 2-mer strings. distance measurement let α = and β = be the ccv or the iccv of two dna sequences a and b, respectively. to calculate d, the distance between a and b, we adopt a distance measurement in this paper as detailed below: d=1−c where c=∑i=1tai×bi1/ c is the cosine of the angle between α and β. data sets to generate simulation data sets to compare the performance of the iccv and the ccv methods, we adopted a similar approach as in. in brief, an ancestor sequence was randomly picked from our influenza virus database; and the progeny sequences were derived through simulation using different types of mutations and following a pre-defined tree topology. six types of mutations at the rate of 9–15% were applied to generate a and a from a, and b and b from b. three types of mutations at the rate of 2–5% were used to generate a from a and b from b. a total of data sets were generated for phylogenetic analysis. besides the simulated data sets, we used a real dataset to compare the iccv and the ccv methods. fifty-four influenza a viral ha sequences were used. each has approximately base pairs. based upon alignment-based phylogenetic analyses, each sequence was assigned a clade number by the international h5n evolution working group. data analysis and visualization statistical package r version. was used for programming and implementation of the ccv and iccv methods. the trees were generated using the neighbor-joining program in the phylip. package. the resulting phylogenetic trees were displayed with mega  analysis of simulation data sets both ccv and iccv trees for k = show the same topology of six sequences, as shown in fig. however, the iccv tree provides much higher bootstrapping values in support of two major clades. this indicates the iccv method is more robust in resolving phylogenetic relationships of remotely related clades than the existing ccv method. application on influenza a virus lineage analysis as shown in fig. iccv and ccv trees for k = agree with each other in the clade designation, but at the sub-clade level it appears that the designation based on the iccv method is more convincing. for example, it is logical to assign the viral strain dk/guangxi/13/ to sub-clade as shown in the iccv tree. however, this is not the case when examining the ccv tree. in addition, the positions of clade clade and sub-clade. on the iccv tree are not the same as on the ccv tree. when comparing trees generated from different methods, both the iccv tree and the tree constructed by the h5n working group have exactly the same topology, which suggests that the iccv method is more dependable than the existing ccv method. discussion does the uniform and independent assumption matter? as we can envision, the only potential weakness associated with the iccv method is the assumption of a uniform and independent model. it has been shown that the null hypothesis of equiprobable occurrence of different nucleotides is reasonable in the context of the dna structures that have evolved from a "primordial soup' or'base pool' containing equal quantities of each base. sege and saxberg have discussed this issue thoroughly. the hypothesis of independent occurrence of different nucleotides has also been accepted in numerous situations, particularly in the analysis of relatively short strings. arritia et al. showed that the approximation of actual dependence in a dna sequence to the theory of independence of bases is quite good. we used our influenza h5n virus sequence database to examine the assumptions of uniformity and independence. chi-square tests reject that the four nucleotides a, c, t, and g occur in equal probabilites or occur independently of one another. although the assumption does not generally hold, both results from the analyses of simulated data and experimental data showed that our improved method is more robust than the existing ccv method, indicating that the violation of the assumption on base composition has no significant impact on the accuracy of the iccv method. is increasing the maximum string length necessary? wu et al. suggested that increasing the maximum string length results in a vector containing finer evolutionary information. to investigate this issue, we used the same simulated sequences data as in section, and constructed the iccv trees for k =. for the purpose of comparison, we also show the iccv tree for k = from fig. in fig. it is clearly shown that as k increases from to the supporting values significantly improve. however, this trend declines as k increases from to obviously, in this case, k = or is a cutoff point, which means increasing k after a certain number may not necessarily improve the result. therefore, it might not be the case that increasing the maximum string length would result in a vector containing finer evolutionary information. the reason for this is that the overlapping nature of strings with multiple lengths causes the overlap of evolutionary information carried by each individual cv. as multiple cvs are combined into a complete cv, the complete cv collects the exclusive evolutionary information that each cv contains, but at the same time the overlapping information that individual cvs contain is also summed up. therefore, increasing the string length k to a certain point will certainly improve the result, but the trend of improvement reaches its peak and afterwards declines. the question is how to choose an optimal string length for construction of the ccv, which will be discussed next. how to choose an optimal string length for the ccv firstly, all the dna sequences in the dataset are concatenated into a single sequence w of length m, which provides an empirical nucleotide distribution for the class of sequences in the dataset. then sk for w is computed. since sk is the vector of observed frequencies of all the k-mer strings in w, skm−k+1=,q,...,qk) is the observed probability for all the k-mer strings. as for a random sequence, the probability for all the k-mer strings is p=, where pi=14k for i =...., 4k. therefore, we can determine the difference between these two probability distributions by their kullback-leibler distance: dk=∑i=14kqklog⁡2pi). dk would be small if the two distributions are close to each other, which indicates that sk does not contain rich evolutionary information and should be excluded from calculating the iccvs. to apply the above method to the experimental dataset in section, we concatenated all sequences in the experimental dataset into sequence a and calculated dk for k =..., similarly, we calculated dk for k =..., where b is a randomly generated sequence with the same length as sequence a. then we computed q=dkdk for k =....,. in fig. we can see that the magnitude of q is fairly large when k is small. as k increases, q starts to decrease, and then it reaches a steady state at q = when k is larger than the reason for this is that the effect of selective evolution is more significant on shorter strings than it is on longer strings. therefore, dk is much larger than dk when k is small. however, as k increases, the effect of selective evolution on k-mer strings starts to decline. thus, the behavior of k-mer strings in sequence a becomes more similar to that of a random sequence and dk becomes closer to dk, which indicates that less evolutionary information is carried by sk. for the experimental dataset, since q is fairly close to when k is larger than an appropriate choice for the maximum string length k would be  in this paper, we show that the existing cv and ccv methods underestimate the evolutionary information contained in a dna sequence due to the markov model assumption and the denominator used for the normalization of observed string frequencies. experiments using simulated and experimental data sets demonstrated that our iccv method generates more accurate and robust results compared with the currently used ccv method. the consistency between the iccv tree and the alignment-based tree recommended by the international h5n evolution working group indicates that the iccv method is a valuable alternative to the alignment-based methods. it is also shown that the violation of the assumption about base composition has no significant impact on the accuracy of the iccv method. as to the issue related to maximum string length, we believe that it is not necessary to use relatively long strings to construct the ccv due to the overlapping nature of strings with variable length. we suggest a practical approach for choosing the optimal string length for the ccv. competing interests the authors declare that they have no competing interests. authors' contributions gl conceived of the study, participated in the experimental design and implementation, and revised the manuscript. sz conceived of the study, supervised the theoretical design of the improved method, and revised the manuscript. xf participated in the experimental design and theoretical development of the method, carried out the implementation, and drafted the manuscript. all authors read and approved the final manuscript. 
historically, two categories of computational algorithms have been applied to sequence comparison–one of the most fundamental issues in bioinformatics. phylogenetic analyses using both simulated and experimental data sets demonstrate that our new method is more robust compared with existing counterparts and comparable in robustness with alignment-based methods. consequently, alignment-free methods have been explored as important alternatives in estimating sequence similarity. of the alignment-free methods, the string composition vector methods, which use the frequencies of nucleotide or amino acid strings to represent sequence information, show promising results in genome sequence comparison of prokaryotes. in addition, we discussed that it might not be necessary to use relatively long strings to build a complete composition vector, due to the overlapping nature of vector strings with a variable length. we suggested a practical approach for the choice of an optimal string length to construct the ccv. the existing cv-based methods, however, suffer certain statistical problems, thereby underestimating the amount of evolutionary information in genetic sequences. we observed two problems existing in the currently used string composition methods and proposed a new robust method for the estimation of evolutionary information of genetic sequences. we propose an improved complete composition vector method under the assumption of a uniform and independent model to estimate sequence information contributing to selection for sequence comparison. we show that the existing string composition based methods have two problems, one related to the markov model assumption and the other associated with the denominator of the frequency normalization equation.
 historically, two categories of computational algorithms have been applied to sequence comparison–one of the most fundamental issues in bioinformatics. multiple sequence alignment, although dominantly used by biologists, possesses both fundamental as well as computational limitations. consequently, alignment-free methods have been explored as important alternatives in estimating sequence similarity. of the alignment-free methods, the string composition vector methods, which use the frequencies of nucleotide or amino acid strings to represent sequence information, show promising results in genome sequence comparison of prokaryotes. the existing cv-based methods, however, suffer certain statistical problems, thereby underestimating the amount of evolutionary information in genetic sequences.  we show that the existing string composition based methods have two problems, one related to the markov model assumption and the other associated with the denominator of the frequency normalization equation. we propose an improved complete composition vector method under the assumption of a uniform and independent model to estimate sequence information contributing to selection for sequence comparison. phylogenetic analyses using both simulated and experimental data sets demonstrate that our new method is more robust compared with existing counterparts and comparable in robustness with alignment-based methods.  we observed two problems existing in the currently used string composition methods and proposed a new robust method for the estimation of evolutionary information of genetic sequences. in addition, we discussed that it might not be necessary to use relatively long strings to build a complete composition vector, due to the overlapping nature of vector strings with a variable length. we suggested a practical approach for the choice of an optimal string length to construct the ccv. 13– august symposium of computations in bioinformatics and bioscience iowa city, iowa, usa 