BACKGROUND
we developed a methodology, based on singular value decomposition , for improved inference of evolutionary relationships between amino acid sequences of different species  <cit> .
svd produces a revised distance matrix for a set of related elements.
our svd-based computations provide results that are close to the internationally accepted scientific gold standard, linnaean taxonomy.
the reason we chose this methodology is the proven capacity that svd has to establish non-obvious, relevant relationships among clustered elements  <cit>  <cit>  <cit>  <cit> , providing a deterministic method for grouping related species.
a distance matrix derived from svd can be used by cladogram software to produce a "phylogenetic tree", yielding a visual overview of the relationships.
we compared species grouping by this method with linnaean taxonomy grouping and found that the species clusters were similar.
the rationale behind svd is that a matrix a can be represented by a set of derived matrices  <cit> , in the same way that a number can be derived into factors.
one can also think of svd as a set of matrices that provide numerically different representations of data without loss in semantic meaning, as for example representation in different base numbers.
to understand the mathematical concept of svd, suppose that 'a' is an array of real numbers or complex numbers composed of m rows by n columns.
a matrix with a singular value decomposition of matrix a can be made:
where u is an orthonormal m x m matrix, and Σ is an m x n matrix, known as the diagonal matrix, with real and non negative numbers.
the matrix vt is known as a conjugate transpose, an n x n unit matrix with real or complex numbers.
as the diagonal values of Σ are ordered in descending order, Σ is a direct function of matrix a and characterizes the singular values of this matrix, ordering them from the most significant to the least significant values.
considering a subset of singular values of size k<n, we can obtain ak an approximate matrix of matrix a:
thus, data approximation depends on how many singular values are used  <cit> .
in this case, the number of singular values k is also known as the rank of matrix ak, indicating how many lines and columns in matrix ak are linearly independent.
the possibility of extracting information based on less data is part of the reason for this technique’s success, as it allows data compression/decompression, with an execution time that does not increase exponentially with increasing matrix size, making analysis viable  <cit> .
a data set represented by a smaller number of singular values than the original, full-size data set has a tendency to group data items that would not be grouped together if we used the original data set  <cit> .
this could explain why clusters derived from svd can expose non-trivial relationships among the original data set items  <cit> .
in this paper we do not use the matrix ak, product's factorization by svd to rank k; with only two arrays of svd, the matrix dk <cit>  is represented in the context of the matrix
the justification for using only dk is that it has k lines instead of m lines from ak, so dk is made up of linear combinations from uk columns, which in turns provides the relationship a ≈ ak ≈ dk.
the main data set that we used was obtained from a previous study involving svd  <cit> , with  <dig> mitochondrial protein sequences from  <dig> families of mitochondrial genes, obtained from  <dig> vertebrate mitochondrial genomes.
we organized these  <dig> sequences into  <dig> single fasta sequences, each representing a single linnaean species, concatenating the sequences of the  <dig> families of mitochondrial genes of each species.
from here on, we will refer to this set of data as dataset <dig>  dataset <dig> consists of  <dig> highly-related species that have at least  <dig> of  <dig> linnaean taxonomy levels in common with each other.
as we also wanted to investigate how svd parameters can influence cluster quality, we added  <dig> additional species to this data set, creating a second set of data, which we named dataset <dig> .
we chose these  <dig> new species based on their high diversity, in order to create a less homogeneous data set; our objective was to determine whether svd would separate non-related and related species into different groups.
the species within dataset <dig> all belong to the same infraphylum , whereas the  <dig> new species that were included to increase diversity were selected from other phyla, also from the animal kingdom.
the  <dig> species included in dataset <dig> were aphrocallistes vastus, asterias amurensis, aurelia aurita, balanoglossus carnosus, branchiostoma belcheri, bugula neritina, callyspongia plicifera, candida albicans, metridium senile, ostreococcus tauri, phallusia fumigata, and unionicola foili.
the quality of the clusters that were generated was measured by the number of linnaean taxonomy levels each species within the cluster bore in common with the other species; this was calculated as a function of an increasing rank value.
when certain rank values are reached, larger values do not improve cluster quality, because there is no increase in taxonomic levels that the species have in common; in some cases a decrease is observed.
the cluster quality obtained from a certain rank value maintains the number of shared common linnaean taxonomy levels constant.
this is evidence that there is an intrinsic relationship between these species that is mirrored in the distance matrix derived from these clusters; this quality helps build relevant cladograms.
RESULTS
singular value decomposition and number of clusters matters
in this study we give support to the hypothesis that choice of an appropriate data representation and a fixed number of clusters, combined with a good algorithm for categorizing this data, is sufficient for the production of biologically significant clusters.
an a matrix has rank n, where n indicates the number of distinct species.
the rank value  defines the degree of resolution of matrix dk compared to the original matrix d, so k must be less than or equal to n. however, a k value close to n is undesirable, because one obtains a strong approximation to the original matrix d, which is useless to uncover relationships.
we need to avoid this so-called ‘noise data’  <cit>  and find a smaller number of singular values that adequately represent the original data and thus achieve a reduction in the amount of data that needs to be processed  <cit>  <cit> .
we found that there is an optimal rank value that can be obtained by systematically testing all possible rank values and distances that define whether two species will form part of the same cluster, based on linnaean taxonomic levels.
a maximum distance value defining whether two species belong to a cluster can be experimentally found by increasing and decreasing an initial, empirically-defined distance, for example, the maximum distance between two species in a data set.
we tried a systematic search for parameters that could confirm or deny this hypothesis.
working with singular value decomposition, one of the main parameters is the number of singular values necessary to create matrix decomposition sufficient to correctly separate all  <dig> species.
this can be done by an algorithm called kdcsearch, which systematically examines possibilities for variation in singular values, euclidean distance separation of clusters and number of clusters, a triad that we call kdc values.
a systematic search to evaluate these three parameters proved to be computationally viable, independent of human intervention; it separates the target species into groups that represent similarity relationships between protein sequences and thus infer homology between species.
the clusters generated through systematic choice of these parameters were biologically significant, demonstrating that we were on the right path in our attempt to determine the smallest number of singular values and the correct euclidean distance that will correctly represent the original data, giving the correct separation of species groups.
based on these experiments we showed that even an “as simple as possible agglomerative clustering algorithm”  can benefit from singular value decomposition to improve the quality of clusters that are generated.
the next step was to use the parameters that were optimal  <cit>  according to our methodology in other algorithms that have been thoroughly tested by the scientific community.
the choice was made by k-means  <cit> , expectation maximization   <cit> , adaptive quality-based clustering algorithm   <cit> , k-medoids  <cit> , and makedensitybasedclusterer   <cit> , since there is a statistically well-founded background, they have been widely used, and they are available as free software packages from r  <cit> , waikato environment for knowledge analysis   <cit> , and the java machine learning library  <cit> .
the k-means requires that an array of numbers be processed to calculate distances for the creation of clusters.
it also opens the possibility of including a parameter that defines a fixed number of clusters to be created with the elements in the distance matrix.
the same number of clusters inferred from the analysis done by asap, our in-house agglomerative clustering algorithm, was used by the k-means algorithm.
the k-means implemented in the r statistical software, from now on called the k-means-r algorithm, was parameterized for the initial number of elements, but not for specific elements.
there is no such parameterizing in the k-means implemented in the weka  software, making it possible that different results will be obtained with these two programs.
we chose as the number of initial elements for calculating the first k-means-r average half of the items or half of the species.
the first run of k-means-r was done with a matrix regarded as adequate because it had been generated with the parameters of the algorithm systematically observed asap, a rank value of nine and eight clusters.
the algorithms em, mbdc, k-means-weka and k-medoids were configured for eight clusters, without altering the other configuration parameters.
the algorithm aqbc does not allow fixing the number of clusters, but we empirically tested parameters till we obtained the same number of clusters .
then we looked for a way to compare the results from the various algorithms.
at first glance it seemed that the result of, for example, k-means-r was as good as the result from asap, but the large number of species and the not less considerable number of clusters made the comparison difficult.
we needed a measure that would allow us to objectively compare the performances of the algorithms.
then we initiated execution of all algorithms with a number of singular values that represented the original array, without any reduction in the rank of the matrix decomposed into singular values.
despite minor variations in quality in some clusters, the overall quality of the clusters did not differ from the performance of all algorithms on a distance matrix generated with a reduction in rank.
table  <dig> shows quality calculations of eight clusters using asap and k-means-r algorithms with different numbers of singular values.
clusters shown in this table are from the second round of trying to create smaller clusters, while maintaining correct separation of the aves group , or the first recursive call of the asap algorithm.
both k-means-r and asap were configured to generate eight clusters.
both algorithms used the matrix of the trigrams representing  <dig>  combinatorial possibilities of  <dig> amino acids , also called n-gram with n= <dig>  with  <dig> singular values  and another matrix derived from the former with only nine singular values; these quantities of singular values and clusters gave good svd results in final clustering.
the first column shows the cluster identification.
the columns that follow are in groups of four, showing the results of k-means and asap, using a trigrams frequency matrix created by svd with  <dig> or nine singular values.
the four columns under the label 'number of species clusters joined by' show the number of species obtained in each cluster.
the four columns under the label 'linnaean taxonomy levels in common by clusters' show the number of linnaean levels in common for each cluster, and the four columns under the label 'common linnaean taxonomy frequency levels  by cluster' show the results of the metrics that we suggested.
these come from multiplication of the column 'number of species clusters joined by' by the column 'linnaean taxonomy levels in common by clusters'.
there were no significant differences  in the quality of clusters generated by the algorithms, based on a comparison of the mean number of linnaean levels in common and cltlf, even though they used different singular values, as shown in the additional file  <dig> .
the chi-square test did not demonstrate any significant relation between these four clustering rounds.
however, there were significant differences between the algorithms and cluster data, based on cltlf, as shown in table  <dig>  this table shows an alternative to measuring algorithm performance with different calibration parameters, using linnaean taxonomy to infer cluster quality.
the sum of the individual qualities of each cluster is measured by cltlf.
when cltlf is weighted by the variation of this quality around the mean or standard deviation, the quality of results can be inferred through linnaean clusters metric quality .
it is worth noting that clusters whose data are shown in table  <dig> possessed a large number of taxonomic levels in common .
it is possible that so many in-common taxonomic levels left little scope for differentiation between the clusters, making the average quality very similar regardless of the method used for clustering.
this result in the comparison between k-means-r and asap was also observed in the results produced by the other algorithms that we tested.
when there was a set of clusters with homogeneous qualities, it was necessary to find a measure that would discriminate the effectiveness of the algorithms with different numbers of singular values.
therefore, we used a measurement that takes into consideration the sum of the qualities of all clusters provided by a given method, weighted by the variation in the quality of clusters.
we analyzed this metric to look for significant differences between the two algorithms and the two numbers of singular values.
the k-means-r algorithm performance was two-fold better than that of asap.
when we used an array of nine decomposed singular values, the number considered optimal for this set of data, in accordance with the methodology suggested here, k-means and asap algorithms had  <dig> and 28% better performances, respectively, when compared to the original results from these methods, without singular value decomposition.
the other algorithms that we tested also gave a significant increase in the quality of clusters in the results of the matrix decomposed into nine singular values and eight clusters, versus the non-decomposed matrix and eight clusters.
in decreasing order, the increases in performance for each method were ~50% , ~49% , ~27% , ~16% , and ~9% .
despite the equal percentage increase for the algorithms k-means-weka, mdbc and k-means-r, the absolute quality values for k-means-r were approximately 50% higher than those from k-means-weka and mdbc, considering the distance matrices with and without decomposition by singular values.
we chose the k-means-r method for more detailed analysis of the results because this is a widely used algorithm and because in terms of absolute quality, it gave results very close to those from algorithm em, which was the best in terms of absolute quality.
these results have some details that are worthy of note.
first, they show that in fact a matrix decomposed into a certain number of singular values, using a certain number of clusters, can create a representation of the original data with better quality than that obtained when we use the original data matrix .
this reinforces the need for decomposition of a matrix into a smaller number of singular values for the removal of so-called 'noise' attributable to a full-rank array  <cit>  <cit>  <cit> .
second, the clustering algorithm was instrumental in generating good-quality clusters.
it can be seen in table  <dig> that the performance of k-means-r and em algorithms was two-fold better than that of the asap algorithm.
third, the method that we suggest here, to systematically explore the parameters needed to obtain the best performance of the k-means proved essential to allow the k-means to generate even better quality clusters.
fourth, the representation of a sequence of amino acids as a vector that stores the trigram frequency of  <dig> amino acids was effective to capture the levels of similarity between the sequences of the protein species that we analyzed, without incurring the problems that classical algorithms have with protein sequence alignments  <cit> .
fifth and finally, the quality metrics using the linnaean classification suggested in this study were effective in measuring the quality of the biological significance of clusters constructed from mitochondrial proteins of dozens of species.
consequently, we conclude that when we use a smaller number of singular values to generate clusters, the quality of the clusters is significantly improved when compared with clusters generated with a matrix with all singular values, independently of algorithm.
these results show that the combination of correct choice of algorithm, the number of singular values, the number of clusters and a quality metric with biological significance allows separation of species groups that are biologically meaningful.
furthermore, the use of trigrams of amino acids provides an effective way to determine similarity between protein sequences without using sequence alignment algorithms.
this table displays the results of k-means and asap on a cluster of  <dig> species obtained in the first asap clustering round, when  <dig> species were separated into clusters.
all evaluated partitioning's algorithms showed improved performance considering the linnaean clusters quality when used the optimized distance matrix created by the better kdc parameters tested.
in the remainder of this paper, we show preliminary findings and methods that helped us reach our final conclusions, including how we arrived at an adequate number of singular values that allowed us to separate a set of species into groups with biological significance.
to this end, we found that using arrays of trigram frequencies of amino acids to determine statistical properties was as good as using 4-gram frequencies  <cit> .
we show that the size of the sequences that are analyzed can affect the separation of elements into clusters.
we also present measures that allow us to infer the biological significance of a cluster and measure the quality of the clustering methods compared to linnaean taxonomic classification of species.
algorithm kdcsearch: parameterizing rank and number of partitions
the objective of the algorithm kdcsearch  is to identify a 'k' rank value and a quantity 'c' of partitions that promote correct separation of species, based on biological significance according to linnaean taxonomy.
this 'k' rank is responsible for the reducing the dimensions of the data that hide evolutionary relations among species, also known as data noise.
a quantity of partitions 'c' should correctly separate the positive control group from the other species and possibly separate the other species into partitions with evolutionarily-significant relationships.
in this algorithm, the number of partitions 'c' is a function of 'd', that is c=f, with 'd' being the euclidian distance between elements in a symmetric matrix of distances between the species.
the value of 'd', on the other hand, varies according to the distance matrix created with rank 'k', establishing the relations d=f and c=f).
in this way, we look for the 'k' value that will eliminate data noise and generate a distance 'd' responsible for creating a number of partitions 'c' with the greatest capacity to infer evolutionary relationships between grouped species.
in this process, we use an in-house algorithm, asap, to partition the species.
considering the random selection of pivotal elements for the creation of partitions by asap, it is not possible to estimate a priori what distance 'd' will create a number 'c' of partitions.
consequently, a systematic search is made with a range of x and y values of euclidean distances in order to determine which distances give what number of partitions.
this algorithm begins with an x value equal to the largest euclidean distance between species represented in a symmetric matrix of distances with a maximum value; that is, it has not undergone decomposition by singular values and for this reason k is equal to the total 'n' of the number of species in this matrix.
considering the maximum distance of the symmetric matrix, only one partition with 'n' species is formed.
the value y is always zero, the point at which the search for partitions of value 'k' terminates and 'n' partitions of the data are always formed, with only one species per partition.
with the values in hand  with their respective values  , c2=f, c3=f, ..., cn=f), in turn with their respective biological significance levels, measured by the function cltlf, we filtered the configuration that gave the correct separation of the control group and the greatest number of partitions of species sharing the highest possible numbers of linnaean classification levels.
this algorithm is recursive because if no group of these variables provides a partitioning of the control group isolated from the other species, then the algorithm did not yet find a solution with the desired level of linnaean taxonomic relationship.
in order to simplify, it is not necessary to analyze all of the possible numbers of partitions; analysis is made only within well-defined intervals.
taking as an example, dataset <dig> with  <dig> species, an alternative is to analyze the number of partitions containing groups of three .
this example can be obtained from the algorithm below through the initialization of a variable that, as it divides the total number of species by  <dig>  permits the creation of an incremental step of three levels between analyses.
the number was determined empirically and the algorithm below is adduced by the variable edrd .
when one of the recursions of the algorithm kdcsearch finds one or more groups of variables k, d and c that give correct separation of the positive control group, the algorithm recursions are finalized.
in this case, there is no reason to continue making recursions, since the desired level of cohesion for the elements of the partitions has reached its limit, measured by the positioning of the positive control.
in the case of the data that we analyzed here, this situation occurs after the end of the first recursion by the algorithm kdcsearch, culminating in the plotting of the final graphs and implementing the function 'finalize'.
the code for the function 'finalize' was left open because at this stage of execution, the algorithm finds various groups of the variables k, d and c  that promote correct separation of the positive control group in a partition separate from the other species.
at this point, the question is which group of values kdc is a good result.
what differentiates one group of variables kdc from another is the quality of the partitioning of the other species compared with linnaean taxonomic classification.
we think that it would not be useful to develop an algorithm that one particular kdc group is better than others because they give different levels of separation of species.
a researcher can be trying to separate a group of species at the level of 'classis' with nine linnaean levels in common , while another researcher may try to separate this same group at the 'ordo' level, with  <dig> linnaean levels in common.
consequently, it would be reasonable to consult the last table generated by the algorithm kdcsearch to adjust the result to the necessities of a specific objective.
however, in case the final objective is not well defined, an option to completely automate this process could be to compare the partitioning medians for each kdc group with which it was possible to separate integrally and isolatedly the positive control species group.
this comparison creates an estimate of the cohesiveness of the partitionings based on comparison with linnaean taxonomic classifications.
values of kdc that give larger medians would be chosen as superior, promoting partitionings with greater biological significance.
the rationale that explains the use of the median as a parameter for the procedure 'finalize' can be better comprehended by analysis of the data in tables  <dig> and  <dig>  these tables show the cltlf results for nine sets of kdc values that by definition are good results because they can separate integrally and isolatedly the positive control group.
in the partitionings produced with these kdc values, there is always a partition of the positive control group with a cltlf equal  <dig> .
values of kdc that cannot optimally separate the positive control group from the other species were also included.
the set of kdc values used as a negative control in this analysis is suffixed with the symbol ''.
in table  <dig>  we can see that the kdc sets that have many partitions with only one isolated element  reduce the median cltlf value for all of the partitions produced in this set by the respective set of kdc values.
the intention of these partitionings is to demonstrate evolutionary relationships among species; the kdc values that give large numbers of partitions with only one element each do not give much information about such relationships.
consequently, it is understood that the best kdc values are those that have the fewest species isolated in partitions with only one element.
table  <dig> also shows the application of the measurement 'linnaean cluster quality' to the partitionings based on these kdc values; however, this measure was not effective in indicating how informative the partitionings for each group of kdc values were in terms of the relationships based on linnaean classification.
it can be seen that the kdc values of the negative control had larger 'linnaean cluster quality' values than the various sets of kdc values that adequately separated the positive control group.
apparently, 'linnaean cluster quality' is not efficient at classifying kdc values at this 'finalize' step of the algorithm search, though it is efficient while the positive control group has not been integrally separated in an isolated partition.
however, based on the median, the sets of kdc values that do not separate the positive control group into isolated clusters were correctly classified as being of low quality based on linnaean classification, as well as other kdc values that had many partitions with the lowest ltlf.
in table  <dig>  the kdc values with the largest medians are in bold, and the kdc values that do not adequately separate the positive control group are in italic.
it is relevant to point out that though some kdc values can adequately separate the positive control group, many partitions have the minimum cltlf; these were responsible for the low kdc values, values even lower than some kdc values that do not adequately separate the positive control group.
in this study, we decided to analyze in more detail the partitions created by the kdc values with eight partitions and rank nine, which produced the third best median result without separating many species into isolated partitions.
this choice is justified by the fact that these kdc parameters make the correct separation of the mammals 'hsap' and 'ppya' in a partition separate from those of the other species.
these two species were used as a second positive control group.
in the set of kdc values with six partitions and rank six, the configuration classified as having the best median, these two species are in a partition with  <dig> other species.
another option would be to use the kdc values with six partitions and rank three, which were classified as the second-best median.
in this kdc configuration, 'hsap' is isolated in a partition, while 'ppya' is in a partition with  <dig> other species.
accordingly, the kdc values that give eight partitions with rank nine promote correct separation of the two positive control groups and were responsible for significantly improving performance in the statistic 'linnaean cluster quality' and in most of the medians of the partitioning algorithms that were tested .
linnaean taxonomy levels used to classify the species in this paper.
the numbers denote an increasing degree of nomenclature specialization.
the statistic cltlf for all of the partitionings of species obtained with nine kdc values that separate the positive control group in the function finalize of the algorithm kdssearch, along with three kdc values as a negative control .
comparison of the lcq values and the Σcltlf medians for partitionings of the species obtained in table  <dig>
from  <dig> to  <dig> species and eight clusters
we decided to use a  <dig> species data set , incorporating  <dig> species that were less related to the original group, in order to develop relationship trees that included clusters with distantly related species.
the  <dig> species data set  from the study by stuart contains closely related species, as all of them share  <dig> of the  <dig> linnaean taxonomy levels used in our study to differentiate species  <cit> .
when a correct fit was made , we were able to separate  <dig> of the  <dig> species and the additional  <dig> species using asap .
these  <dig> added species plus four of the original species from dataset <dig> did not group into a single cluster.
instead, we obtained several different clusters, most of which included only one species.
analyses were then carried out on only the  <dig> species from the data set that were joined as a single cluster; the asap algorithm was run with  <dig> clusters and a rank value of  <dig>  when the asap algorithm was run with the original  <dig> species data set, some elements were separated into isolated clusters despite actually sharing several linnaean taxonomy levels in common with all of the other species.
this could be due to the fact that mitochondrial protein sequences for some species within the data set used in this study were not available.
since our algorithm only uses the frequency of occurrence of amino acid triplets, a lower frequency can affect the quality of the clusters that are generated, as does the presence or absence of a triplet sequence.
presence or absence of amino acid triplets are also responsible for early cluster separation of the  <dig> additional taxonomically distantly related species, incorporated into the original  <dig> species data set.
consequently, we worked with this  <dig> species data subset.
to do so, we included a recurrence step prediction in our algorithm in order to develop a species subset.
we worked with the concept that a good separation of species in clusters distributes the elements in groups of more than one element, whereas a group with only one element gives no information about species ancestry.
when we correctly separated the aves group in an isolated cluster, we assumed that other groups should also be close to divisions that have evolutionary significance.
finally, a good separation involves having aves isolated in a single group, while having the largest possible number of other species together in groups, with a few isolated species in groups of only one element .
this definition of good separation between species is applicable only when it is not possible to isolate the positive control group, the aves group.
but when we split a homogeneous positive control group, the concept of a good separation of species is altered and it changes the way we interpret the graph of rank value versus cltlf in the first recursive call of the algorithm .
in figure  <dig>  a high cltlf value means poor cluster quality, because at this level of recursion it is possible to isolate the positive control group in a single cluster and leave few species in isolated groups.
therefore the optimal value for the separation of the group of aves is  <dig> .
a value larger or smaller than that gave inappropriate separation, because the positive control is the group of birds with  <dig> species sharing  <dig> levels of linnaeus.
using a second positive control group , we concluded that using eight partitions with rank nine is the best configuration, correctly separating the birds group, creating groups with evolutionary significance and decreasing the number of species in groups of only one element.
we used a rank value of nine to create the unrooted tree shown in figure  <dig>  asap was calibrated with a d value that produces eight clusters using the experimented rank value of nine.
this choice was made based on obtaining a good separation result, when grouping all species of the aves class into a single cluster, plus a positive control group.
the results of the first execution of our recurrence algorithm based on the  <dig> species data set can be seen in table  <dig>  clusters  <dig>   <dig> and  <dig> are comprised of species of theclass mammalia.
cluster number  <dig> includes the hominids homo sapiens and pongo pygmaeus, which were together, separated from other mammals due to their mitochondrial protein sequences sharing  <dig> common linnaean taxonomy levels.
clusters  <dig>   <dig> and  <dig> were composed of only mammalian species, sharing  <dig>   <dig> and  <dig> common linnaean taxonomy levels, respectively.
it is evident that the number of clusters and rank value used to create distance matrices enables even asap to provide adequate clustering based on quality discrimination.
all the clusters that were obtained are shown in figure  <dig>  in which four mnemonic letters represent each species.
eight clusters created from the first recurrence algorithm execution calibrated with a rank value of nine.
species were grouped according to their deepest evolutionary relatedness based on linnaean taxonomy levels.
clusters  <dig>   <dig> and  <dig> belong to the mammalian class.
CONCLUSIONS
clusters and cladistic trees drawn from distance matrices, which were generated with svd, showed a good correlation with linnaean taxonomy.
considering the best estimate, when a difference is found, this does not necessarily mean strong divergence from taxonomic methods, but perhaps a more accurate picture of the relationship between the species that clustered together.
this was demonstrated by clusters that were separated from mammalian clusters due to their greater protein sequence relatedness.
it also was reinforced by linnaean taxonomy information.
the similarity between clusters generated by our distance matrix and linnaean taxonomy is indicative that distance matrices generated by svd can demonstrate evolutionary relationships of species and construct better quality clusters and phylogenetic trees.
these clusters and phylogenetic trees would benefit from amino acid trigrams and the euclidean distance property of displaying a distance proportional to the number of necessary edits needed to perform a global alignment sequence within a polynomial execution time.

 we developed a methodology, based on singular value decomposition, for improved inference of evolutionary relationships between amino acid sequences of different species. svd produces a revised distance matrix for a set of related elements. our svd-based computations provide results that are close to the internationally accepted scientific gold standard, linnaean taxonomy. the reason we chose this methodology is the proven capacity that svd has to establish non-obvious, relevant relationships among clustered elements, providing a deterministic method for grouping related species. a distance matrix derived from svd can be used by cladogram software to produce a "phylogenetic tree", yielding a visual overview of the relationships. we compared species grouping by this method with linnaean taxonomy grouping and found that the species clusters were similar. the rationale behind svd is that a matrix a can be represented by a set of derived matrices, in the same way that a number can be derived into factors. one can also think of svd as a set of matrices that provide numerically different representations of data without loss in semantic meaning, as for example representation in different base numbers. to understand the mathematical concept of svd, suppose that'a' is an array of real numbers or complex numbers composed of m rows by n columns. a matrix with a singular value decomposition of matrix a can be made: where u is an orthonormal m x m matrix, and Σ is an m x n matrix, known as the diagonal matrix, with real and non negative numbers. the matrix vt is known as a conjugate transpose, an n x n unit matrix with real or complex numbers. as the diagonal values of Σ are ordered in descending order, Σ is a direct function of matrix a and characterizes the singular values of this matrix, ordering them from the most significant to the least significant values. considering a subset of singular values of size k<n, we can obtain ak an approximate matrix of matrix a: thus, data approximation depends on how many singular values are used. in this case, the number of singular values k is also known as the rank of matrix ak, indicating how many lines and columns in matrix ak are linearly independent. the possibility of extracting information based on less data is part of the reason for this technique’s success, as it allows data compression/decompression, with an execution time that does not increase exponentially with increasing matrix size, making analysis viable. a data set represented by a smaller number of singular values than the original, full-size data set has a tendency to group data items that would not be grouped together if we used the original data set. this could explain why clusters derived from svd can expose non-trivial relationships among the original data set items. in this paper we do not use the matrix ak, product's factorization by svd to rank k; with only two arrays of svd, the matrix dk is represented in the context of the matrix the justification for using only dk is that it has k lines instead of m lines from ak, so dk is made up of linear combinations from uk columns, which in turns provides the relationship a ≈ ak ≈ dk. the main data set that we used was obtained from a previous study involving svd, with mitochondrial protein sequences from families of mitochondrial genes, obtained from vertebrate mitochondrial genomes. we organized these sequences into single fasta sequences, each representing a single linnaean species, concatenating the sequences of the families of mitochondrial genes of each species. from here on, we will refer to this set of data as dataset dataset consists of highly-related species that have at least of linnaean taxonomy levels in common with each other. as we also wanted to investigate how svd parameters can influence cluster quality, we added additional species to this data set, creating a second set of data, which we named dataset. we chose these new species based on their high diversity, in order to create a less homogeneous data set; our objective was to determine whether svd would separate non-related and related species into different groups. the species within dataset all belong to the same infraphylum, whereas the new species that were included to increase diversity were selected from other phyla, also from the animal kingdom. the species included in dataset were aphrocallistes vastus, asterias amurensis, aurelia aurita, balanoglossus carnosus, branchiostoma belcheri, bugula neritina, callyspongia plicifera, candida albicans, metridium senile, ostreococcus tauri, phallusia fumigata, and unionicola foili. the quality of the clusters that were generated was measured by the number of linnaean taxonomy levels each species within the cluster bore in common with the other species; this was calculated as a function of an increasing rank value. when certain rank values are reached, larger values do not improve cluster quality, because there is no increase in taxonomic levels that the species have in common; in some cases a decrease is observed. the cluster quality obtained from a certain rank value maintains the number of shared common linnaean taxonomy levels constant. this is evidence that there is an intrinsic relationship between these species that is mirrored in the distance matrix derived from these clusters; this quality helps build relevant cladograms.  singular value decomposition and number of clusters matters in this study we give support to the hypothesis that choice of an appropriate data representation and a fixed number of clusters, combined with a good algorithm for categorizing this data, is sufficient for the production of biologically significant clusters. an a matrix has rank n, where n indicates the number of distinct species. the rank value defines the degree of resolution of matrix dk compared to the original matrix d, so k must be less than or equal to n. however, a k value close to n is undesirable, because one obtains a strong approximation to the original matrix d, which is useless to uncover relationships. we need to avoid this so-called ‘noise data’ and find a smaller number of singular values that adequately represent the original data and thus achieve a reduction in the amount of data that needs to be processed. we found that there is an optimal rank value that can be obtained by systematically testing all possible rank values and distances that define whether two species will form part of the same cluster, based on linnaean taxonomic levels. a maximum distance value defining whether two species belong to a cluster can be experimentally found by increasing and decreasing an initial, empirically-defined distance, for example, the maximum distance between two species in a data set. we tried a systematic search for parameters that could confirm or deny this hypothesis. working with singular value decomposition, one of the main parameters is the number of singular values necessary to create matrix decomposition sufficient to correctly separate all species. this can be done by an algorithm called kdcsearch, which systematically examines possibilities for variation in singular values, euclidean distance separation of clusters and number of clusters, a triad that we call kdc values. a systematic search to evaluate these three parameters proved to be computationally viable, independent of human intervention; it separates the target species into groups that represent similarity relationships between protein sequences and thus infer homology between species. the clusters generated through systematic choice of these parameters were biologically significant, demonstrating that we were on the right path in our attempt to determine the smallest number of singular values and the correct euclidean distance that will correctly represent the original data, giving the correct separation of species groups. based on these experiments we showed that even an “as simple as possible agglomerative clustering algorithm” can benefit from singular value decomposition to improve the quality of clusters that are generated. the next step was to use the parameters that were optimal according to our methodology in other algorithms that have been thoroughly tested by the scientific community. the choice was made by k-means, expectation maximization, adaptive quality-based clustering algorithm, k-medoids, and makedensitybasedclusterer, since there is a statistically well-founded background, they have been widely used, and they are available as free software packages from r, waikato environment for knowledge analysis, and the java machine learning library. the k-means requires that an array of numbers be processed to calculate distances for the creation of clusters. it also opens the possibility of including a parameter that defines a fixed number of clusters to be created with the elements in the distance matrix. the same number of clusters inferred from the analysis done by asap, our in-house agglomerative clustering algorithm, was used by the k-means algorithm. the k-means implemented in the r statistical software, from now on called the k-means-r algorithm, was parameterized for the initial number of elements, but not for specific elements. there is no such parameterizing in the k-means implemented in the weka software, making it possible that different results will be obtained with these two programs. we chose as the number of initial elements for calculating the first k-means-r average half of the items or half of the species. the first run of k-means-r was done with a matrix regarded as adequate because it had been generated with the parameters of the algorithm systematically observed asap, a rank value of nine and eight clusters. the algorithms em, mbdc, k-means-weka and k-medoids were configured for eight clusters, without altering the other configuration parameters. the algorithm aqbc does not allow fixing the number of clusters, but we empirically tested parameters till we obtained the same number of clusters. then we looked for a way to compare the results from the various algorithms. at first glance it seemed that the result of, for example, k-means-r was as good as the result from asap, but the large number of species and the not less considerable number of clusters made the comparison difficult. we needed a measure that would allow us to objectively compare the performances of the algorithms. then we initiated execution of all algorithms with a number of singular values that represented the original array, without any reduction in the rank of the matrix decomposed into singular values. despite minor variations in quality in some clusters, the overall quality of the clusters did not differ from the performance of all algorithms on a distance matrix generated with a reduction in rank. table shows quality calculations of eight clusters using asap and k-means-r algorithms with different numbers of singular values. clusters shown in this table are from the second round of trying to create smaller clusters, while maintaining correct separation of the aves group, or the first recursive call of the asap algorithm. both k-means-r and asap were configured to generate eight clusters. both algorithms used the matrix of the trigrams representing combinatorial possibilities of amino acids, also called n-gram with n= with singular values and another matrix derived from the former with only nine singular values; these quantities of singular values and clusters gave good svd results in final clustering. the first column shows the cluster identification. the columns that follow are in groups of four, showing the results of k-means and asap, using a trigrams frequency matrix created by svd with or nine singular values. the four columns under the label'number of species clusters joined by' show the number of species obtained in each cluster. the four columns under the label'linnaean taxonomy levels in common by clusters' show the number of linnaean levels in common for each cluster, and the four columns under the label'common linnaean taxonomy frequency levels by cluster' show the results of the metrics that we suggested. these come from multiplication of the column'number of species clusters joined by' by the column'linnaean taxonomy levels in common by clusters'. there were no significant differences in the quality of clusters generated by the algorithms, based on a comparison of the mean number of linnaean levels in common and cltlf, even though they used different singular values, as shown in the additional file. the chi-square test did not demonstrate any significant relation between these four clustering rounds. however, there were significant differences between the algorithms and cluster data, based on cltlf, as shown in table this table shows an alternative to measuring algorithm performance with different calibration parameters, using linnaean taxonomy to infer cluster quality. the sum of the individual qualities of each cluster is measured by cltlf. when cltlf is weighted by the variation of this quality around the mean or standard deviation, the quality of results can be inferred through linnaean clusters metric quality. it is worth noting that clusters whose data are shown in table possessed a large number of taxonomic levels in common. it is possible that so many in-common taxonomic levels left little scope for differentiation between the clusters, making the average quality very similar regardless of the method used for clustering. this result in the comparison between k-means-r and asap was also observed in the results produced by the other algorithms that we tested. when there was a set of clusters with homogeneous qualities, it was necessary to find a measure that would discriminate the effectiveness of the algorithms with different numbers of singular values. therefore, we used a measurement that takes into consideration the sum of the qualities of all clusters provided by a given method, weighted by the variation in the quality of clusters. we analyzed this metric to look for significant differences between the two algorithms and the two numbers of singular values. the k-means-r algorithm performance was two-fold better than that of asap. when we used an array of nine decomposed singular values, the number considered optimal for this set of data, in accordance with the methodology suggested here, k-means and asap algorithms had and 28% better performances, respectively, when compared to the original results from these methods, without singular value decomposition. the other algorithms that we tested also gave a significant increase in the quality of clusters in the results of the matrix decomposed into nine singular values and eight clusters, versus the non-decomposed matrix and eight clusters. in decreasing order, the increases in performance for each method were ~50%, ~49%, ~27%, ~16%, and ~9%. despite the equal percentage increase for the algorithms k-means-weka, mdbc and k-means-r, the absolute quality values for k-means-r were approximately 50% higher than those from k-means-weka and mdbc, considering the distance matrices with and without decomposition by singular values. we chose the k-means-r method for more detailed analysis of the results because this is a widely used algorithm and because in terms of absolute quality, it gave results very close to those from algorithm em, which was the best in terms of absolute quality. these results have some details that are worthy of note. first, they show that in fact a matrix decomposed into a certain number of singular values, using a certain number of clusters, can create a representation of the original data with better quality than that obtained when we use the original data matrix. this reinforces the need for decomposition of a matrix into a smaller number of singular values for the removal of so-called'noise' attributable to a full-rank array. second, the clustering algorithm was instrumental in generating good-quality clusters. it can be seen in table that the performance of k-means-r and em algorithms was two-fold better than that of the asap algorithm. third, the method that we suggest here, to systematically explore the parameters needed to obtain the best performance of the k-means proved essential to allow the k-means to generate even better quality clusters. fourth, the representation of a sequence of amino acids as a vector that stores the trigram frequency of amino acids was effective to capture the levels of similarity between the sequences of the protein species that we analyzed, without incurring the problems that classical algorithms have with protein sequence alignments. fifth and finally, the quality metrics using the linnaean classification suggested in this study were effective in measuring the quality of the biological significance of clusters constructed from mitochondrial proteins of dozens of species. consequently, we conclude that when we use a smaller number of singular values to generate clusters, the quality of the clusters is significantly improved when compared with clusters generated with a matrix with all singular values, independently of algorithm. these results show that the combination of correct choice of algorithm, the number of singular values, the number of clusters and a quality metric with biological significance allows separation of species groups that are biologically meaningful. furthermore, the use of trigrams of amino acids provides an effective way to determine similarity between protein sequences without using sequence alignment algorithms. this table displays the results of k-means and asap on a cluster of species obtained in the first asap clustering round, when species were separated into clusters. all evaluated partitioning's algorithms showed improved performance considering the linnaean clusters quality when used the optimized distance matrix created by the better kdc parameters tested. in the remainder of this paper, we show preliminary findings and methods that helped us reach our final conclusions, including how we arrived at an adequate number of singular values that allowed us to separate a set of species into groups with biological significance. to this end, we found that using arrays of trigram frequencies of amino acids to determine statistical properties was as good as using 4-gram frequencies. we show that the size of the sequences that are analyzed can affect the separation of elements into clusters. we also present measures that allow us to infer the biological significance of a cluster and measure the quality of the clustering methods compared to linnaean taxonomic classification of species. algorithm kdcsearch: parameterizing rank and number of partitions the objective of the algorithm kdcsearch is to identify a'k' rank value and a quantity'c' of partitions that promote correct separation of species, based on biological significance according to linnaean taxonomy. this'k' rank is responsible for the reducing the dimensions of the data that hide evolutionary relations among species, also known as data noise. a quantity of partitions'c' should correctly separate the positive control group from the other species and possibly separate the other species into partitions with evolutionarily-significant relationships. in this algorithm, the number of partitions'c' is a function of'd', that is c=f, with'd' being the euclidian distance between elements in a symmetric matrix of distances between the species. the value of'd', on the other hand, varies according to the distance matrix created with rank'k', establishing the relations d=f and c=f). in this way, we look for the'k' value that will eliminate data noise and generate a distance'd' responsible for creating a number of partitions'c' with the greatest capacity to infer evolutionary relationships between grouped species. in this process, we use an in-house algorithm, asap, to partition the species. considering the random selection of pivotal elements for the creation of partitions by asap, it is not possible to estimate a priori what distance'd' will create a number'c' of partitions. consequently, a systematic search is made with a range of x and y values of euclidean distances in order to determine which distances give what number of partitions. this algorithm begins with an x value equal to the largest euclidean distance between species represented in a symmetric matrix of distances with a maximum value; that is, it has not undergone decomposition by singular values and for this reason k is equal to the total'n' of the number of species in this matrix. considering the maximum distance of the symmetric matrix, only one partition with'n' species is formed. the value y is always zero, the point at which the search for partitions of value'k' terminates and'n' partitions of the data are always formed, with only one species per partition. with the values in hand with their respective values, c2=f, c3=f,..., cn=f), in turn with their respective biological significance levels, measured by the function cltlf, we filtered the configuration that gave the correct separation of the control group and the greatest number of partitions of species sharing the highest possible numbers of linnaean classification levels. this algorithm is recursive because if no group of these variables provides a partitioning of the control group isolated from the other species, then the algorithm did not yet find a solution with the desired level of linnaean taxonomic relationship. in order to simplify, it is not necessary to analyze all of the possible numbers of partitions; analysis is made only within well-defined intervals. taking as an example, dataset with species, an alternative is to analyze the number of partitions containing groups of three. this example can be obtained from the algorithm below through the initialization of a variable that, as it divides the total number of species by permits the creation of an incremental step of three levels between analyses. the number was determined empirically and the algorithm below is adduced by the variable edrd. when one of the recursions of the algorithm kdcsearch finds one or more groups of variables k, d and c that give correct separation of the positive control group, the algorithm recursions are finalized. in this case, there is no reason to continue making recursions, since the desired level of cohesion for the elements of the partitions has reached its limit, measured by the positioning of the positive control. in the case of the data that we analyzed here, this situation occurs after the end of the first recursion by the algorithm kdcsearch, culminating in the plotting of the final graphs and implementing the function'finalize'. the code for the function'finalize' was left open because at this stage of execution, the algorithm finds various groups of the variables k, d and c that promote correct separation of the positive control group in a partition separate from the other species. at this point, the question is which group of values kdc is a good result. what differentiates one group of variables kdc from another is the quality of the partitioning of the other species compared with linnaean taxonomic classification. we think that it would not be useful to develop an algorithm that one particular kdc group is better than others because they give different levels of separation of species. a researcher can be trying to separate a group of species at the level of'classis' with nine linnaean levels in common, while another researcher may try to separate this same group at the'ordo' level, with linnaean levels in common. consequently, it would be reasonable to consult the last table generated by the algorithm kdcsearch to adjust the result to the necessities of a specific objective. however, in case the final objective is not well defined, an option to completely automate this process could be to compare the partitioning medians for each kdc group with which it was possible to separate integrally and isolatedly the positive control species group. this comparison creates an estimate of the cohesiveness of the partitionings based on comparison with linnaean taxonomic classifications. values of kdc that give larger medians would be chosen as superior, promoting partitionings with greater biological significance. the rationale that explains the use of the median as a parameter for the procedure'finalize' can be better comprehended by analysis of the data in tables and these tables show the cltlf results for nine sets of kdc values that by definition are good results because they can separate integrally and isolatedly the positive control group. in the partitionings produced with these kdc values, there is always a partition of the positive control group with a cltlf equal. values of kdc that cannot optimally separate the positive control group from the other species were also included. the set of kdc values used as a negative control in this analysis is suffixed with the symbol''. in table we can see that the kdc sets that have many partitions with only one isolated element reduce the median cltlf value for all of the partitions produced in this set by the respective set of kdc values. the intention of these partitionings is to demonstrate evolutionary relationships among species; the kdc values that give large numbers of partitions with only one element each do not give much information about such relationships. consequently, it is understood that the best kdc values are those that have the fewest species isolated in partitions with only one element. table also shows the application of the measurement'linnaean cluster quality' to the partitionings based on these kdc values; however, this measure was not effective in indicating how informative the partitionings for each group of kdc values were in terms of the relationships based on linnaean classification. it can be seen that the kdc values of the negative control had larger'linnaean cluster quality' values than the various sets of kdc values that adequately separated the positive control group. apparently,'linnaean cluster quality' is not efficient at classifying kdc values at this'finalize' step of the algorithm search, though it is efficient while the positive control group has not been integrally separated in an isolated partition. however, based on the median, the sets of kdc values that do not separate the positive control group into isolated clusters were correctly classified as being of low quality based on linnaean classification, as well as other kdc values that had many partitions with the lowest ltlf. in table the kdc values with the largest medians are in bold, and the kdc values that do not adequately separate the positive control group are in italic. it is relevant to point out that though some kdc values can adequately separate the positive control group, many partitions have the minimum cltlf; these were responsible for the low kdc values, values even lower than some kdc values that do not adequately separate the positive control group. in this study, we decided to analyze in more detail the partitions created by the kdc values with eight partitions and rank nine, which produced the third best median result without separating many species into isolated partitions. this choice is justified by the fact that these kdc parameters make the correct separation of the mammals'hsap' and'ppya' in a partition separate from those of the other species. these two species were used as a second positive control group. in the set of kdc values with six partitions and rank six, the configuration classified as having the best median, these two species are in a partition with other species. another option would be to use the kdc values with six partitions and rank three, which were classified as the second-best median. in this kdc configuration,'hsap' is isolated in a partition, while'ppya' is in a partition with other species. accordingly, the kdc values that give eight partitions with rank nine promote correct separation of the two positive control groups and were responsible for significantly improving performance in the statistic'linnaean cluster quality' and in most of the medians of the partitioning algorithms that were tested. linnaean taxonomy levels used to classify the species in this paper. the numbers denote an increasing degree of nomenclature specialization. the statistic cltlf for all of the partitionings of species obtained with nine kdc values that separate the positive control group in the function finalize of the algorithm kdssearch, along with three kdc values as a negative control. comparison of the lcq values and the Σcltlf medians for partitionings of the species obtained in table from to species and eight clusters we decided to use a species data set, incorporating species that were less related to the original group, in order to develop relationship trees that included clusters with distantly related species. the species data set from the study by stuart contains closely related species, as all of them share of the linnaean taxonomy levels used in our study to differentiate species. when a correct fit was made, we were able to separate of the species and the additional species using asap. these added species plus four of the original species from dataset did not group into a single cluster. instead, we obtained several different clusters, most of which included only one species. analyses were then carried out on only the species from the data set that were joined as a single cluster; the asap algorithm was run with clusters and a rank value of when the asap algorithm was run with the original species data set, some elements were separated into isolated clusters despite actually sharing several linnaean taxonomy levels in common with all of the other species. this could be due to the fact that mitochondrial protein sequences for some species within the data set used in this study were not available. since our algorithm only uses the frequency of occurrence of amino acid triplets, a lower frequency can affect the quality of the clusters that are generated, as does the presence or absence of a triplet sequence. presence or absence of amino acid triplets are also responsible for early cluster separation of the additional taxonomically distantly related species, incorporated into the original species data set. consequently, we worked with this species data subset. to do so, we included a recurrence step prediction in our algorithm in order to develop a species subset. we worked with the concept that a good separation of species in clusters distributes the elements in groups of more than one element, whereas a group with only one element gives no information about species ancestry. when we correctly separated the aves group in an isolated cluster, we assumed that other groups should also be close to divisions that have evolutionary significance. finally, a good separation involves having aves isolated in a single group, while having the largest possible number of other species together in groups, with a few isolated species in groups of only one element. this definition of good separation between species is applicable only when it is not possible to isolate the positive control group, the aves group. but when we split a homogeneous positive control group, the concept of a good separation of species is altered and it changes the way we interpret the graph of rank value versus cltlf in the first recursive call of the algorithm. in figure a high cltlf value means poor cluster quality, because at this level of recursion it is possible to isolate the positive control group in a single cluster and leave few species in isolated groups. therefore the optimal value for the separation of the group of aves is. a value larger or smaller than that gave inappropriate separation, because the positive control is the group of birds with species sharing levels of linnaeus. using a second positive control group, we concluded that using eight partitions with rank nine is the best configuration, correctly separating the birds group, creating groups with evolutionary significance and decreasing the number of species in groups of only one element. we used a rank value of nine to create the unrooted tree shown in figure asap was calibrated with a d value that produces eight clusters using the experimented rank value of nine. this choice was made based on obtaining a good separation result, when grouping all species of the aves class into a single cluster, plus a positive control group. the results of the first execution of our recurrence algorithm based on the species data set can be seen in table clusters and are comprised of species of theclass mammalia. cluster number includes the hominids homo sapiens and pongo pygmaeus, which were together, separated from other mammals due to their mitochondrial protein sequences sharing common linnaean taxonomy levels. clusters and were composed of only mammalian species, sharing and common linnaean taxonomy levels, respectively. it is evident that the number of clusters and rank value used to create distance matrices enables even asap to provide adequate clustering based on quality discrimination. all the clusters that were obtained are shown in figure in which four mnemonic letters represent each species. eight clusters created from the first recurrence algorithm execution calibrated with a rank value of nine. species were grouped according to their deepest evolutionary relatedness based on linnaean taxonomy levels. clusters and belong to the mammalian class.  clusters and cladistic trees drawn from distance matrices, which were generated with svd, showed a good correlation with linnaean taxonomy. considering the best estimate, when a difference is found, this does not necessarily mean strong divergence from taxonomic methods, but perhaps a more accurate picture of the relationship between the species that clustered together. this was demonstrated by clusters that were separated from mammalian clusters due to their greater protein sequence relatedness. it also was reinforced by linnaean taxonomy information. the similarity between clusters generated by our distance matrix and linnaean taxonomy is indicative that distance matrices generated by svd can demonstrate evolutionary relationships of species and construct better quality clusters and phylogenetic trees. these clusters and phylogenetic trees would benefit from amino acid trigrams and the euclidean distance property of displaying a distance proportional to the number of necessary edits needed to perform a global alignment sequence within a polynomial execution time. 
the choice of a reasonable number of singular values is crucial for svd-based studies. we found that fewer singular values are needed to produce biologically significant clusters when svd is employed. subsequently, we developed a method to determine the lowest number of singular values and fewest clusters needed to guarantee biological significance; this system was developed and validated by comparison with linnaean taxonomic classification. singular value decomposition is a powerful technique for information retrieval; it helps uncover relationships between elements that are not prima facie related. we found that svd applied to amino acid sequences demonstrates relationships and provides a basis for producing clusters and cladograms, demonstrating evolutionary relatedness of species that correlates well with linnaean taxonomy. in tests, clusters that we developed with svd perfectly matched what was expected based on linnaean taxonomy.
 singular value decomposition is a powerful technique for information retrieval; it helps uncover relationships between elements that are not prima facie related. svd was initially developed to reduce the time needed for information retrieval and analysis of very large data sets in the complex internet environment. since information retrieval from large-scale genome and proteome data sets has a similar level of complexity, svd-based methods could also facilitate data analysis in this research area.  we found that svd applied to amino acid sequences demonstrates relationships and provides a basis for producing clusters and cladograms, demonstrating evolutionary relatedness of species that correlates well with linnaean taxonomy. the choice of a reasonable number of singular values is crucial for svd-based studies. we found that fewer singular values are needed to produce biologically significant clusters when svd is employed. subsequently, we developed a method to determine the lowest number of singular values and fewest clusters needed to guarantee biological significance; this system was developed and validated by comparison with linnaean taxonomic classification.  by using svd, we can reduce uncertainty concerning the appropriate rank value necessary to perform accurate information retrieval analyses. in tests, clusters that we developed with svd perfectly matched what was expected based on linnaean taxonomy. 15- november 6th international conference of the brazilian association for bioinformatics and computational biology ouro preto, brazil 