Similarity/Dissimilarity Analysis of Protein Sequences Based on a New Spectrum-Like Graphical Representation

Sequence comparison is one of the foundations in bioinformatics, which can be used to study evolutionary relations among the sequences. In this study, a 2D spectrum-like graphical representation of protein sequences is presented based on the hydrophobicity scale of amino acids. The frequencies of amplitudes of 4-subsequences are adopted to characterize a spectrum-like graph, and a 17D vector is used as the descriptor of protein sequence. The χ2 value of compatibility test is performed. New similarity analysis approach is illustrated on the all protein sequences, which are encoded by the mitochondrion genome of 20 different species. Finally, comparison with the ClustalW method shows the utility of our method.


Introduction
Comparison of bio-sequences, such as DNA, RNA, and protein, is the origin of bioinformatics. Through the comparison, we can identify the similarity/dissimilarity of different species' sequences. Many methods of technologies have been introduced like graphical representation of DNA/RNA and so on. Based on graphical representations, numerical characterization techniques offer a route toward quantitatively estimating the similarities/dissimilarities of sequences. [1][2][3][4][5][6][7][8][9][10][11][12][13] The reason for the delay in the emergence of graphical representations of proteins is the increased complexity of biological strings built on a 20-letter alphabet (representing the 20 natural amino acids) in comparison with strings built from only four letters (representing DNA or RNA). According to the genetic code, Randić et al. and Bai and Wang [14][15][16][17] gave some graphical representations and the sequence descriptors of proteins. Similar to existing graphical representation of DNA, in order to better compare the similarities/dissimilarities of proteins, we modified some graphical representations of proteins. [18][19][20][21] With some physicochemical properties of 20 amino acids, the graphical representations of protein sequence have been introduced. [22][23][24][25][26] Measuring the similarity between categorical sequences is a fundamental process in many data mining applications.
A key issue is extracting and making use of significant features hidden behind the chronological and structural dependencies found in these sequences. This measure can lead to a better understanding of the nature of these sequences. The most important known challenges presented by these data, which are only partially addressed by existing methods, are the following: (1) it is difficult to extract the information underlying the chronological dependencies of structural features which may have significant meaning; (2) the high computational cost involved is also an important problem; (3) this creates ambiguities and complications for the similarity measurement task, especially for sequences of significantly different lengths.
In this study, we outline a novel spectrum-like graphical representation, which is based on the hydrophobicity property of amino acids, and introduce a novel strategy for sequence comparison according to the method of calculating the frequencies of all amplitudes of different species' spectral graphs. We will make a comparison for all protein sequences in the mitochondria of 20 species.

Methods
Here we consider a physicochemical property which has important relations with the structure of proteins: hydrophobicity of amino acids. The distribution of hydrophobic amino acids in the primary sequences can be used as an indicator to predict the secondary structure of protein elements. 27 In the following contents, we will construct the spectrum-like graphical representation of protein sequences.
First, each amino acid is characterized by its own physicochemical properties. Twenty amino acids are simplified into two types 28  Thus, giving a protein sequence S = s 1 s 2 …s N with N amino acids, we inspect it by stepping one amino acid at a time. For example, at the step i(i = 1, 2, …, N), S i is transformed into d i which may be 2, 1, −1, and −2. Then the digit sequence D = d 1 d 2 …d N is obtained. In order to more clearly display the differences between hydrophobic amino acids and hydrophilic amino acids, during the construction of the digit sequence, we preset the value of properties: It is sometimes instructive to represent a random walk as a polygonal line, or path, in the plane, where the horizontal axis represents time and the vertical axis represents the value of {S n }. Giving a sequence {S n } of partial sums, we first plot the points (n, S n ), and then for each k , n, we connect (k, S k ) and (k+1, S k+1 ) with a straight line segment. The length of a path is just the difference in the time values of the beginning and ending points on the path. So, d j , d j+1 , d j+2 , d j+3 , four consecutive numbers are summed as the partial sums and the summations are the values of vertical axis and are considered as the amplitudes. When i is the value of horizontal axis and runs from 1 to N−3, we have the points P 1 (x 1 , y 1 ), P 2 (x 2 , y 2 ),…, P N−3 (x N−3 , y N−3 ). Among them, x i and y i are calculated by the following formula: .  Connecting adjacent points, we obtain a spectrum-like graph of protein sequence.
We will illustrate the current approach on two shorter segments of yeast protein Saccharomyces cerevisiae. Figure 1 shows the two spectral graphs, and the corresponding proteins are Protein I: WTFESRNDPAKDPVILWLNGGPGC-SSLTGL; Protein II: WFFESRNDPANDPIILWLNGGPGC-SSFTGL.
The digit sequence (d i ) and 4-subsequence (y i ) of the protein I are showed in Table 1.
Observing Figure 1, we know that the two curves are similar on the whole and have several same local sequences' segments. In this method, the reason why we emphasize the same hydrophilic-hydrophobic amino acids is that they are more likely to form a similar or identical structure.
In Figure 2, we apply the new spectral representation to the ND6 (NADH dehydrogenase subunit 6) proteins of nine species, human, gorilla, common chimpanzee, pigmy chimpanzee, blue whale, fin whale, rat, mouse, and opossum. Taking a closer look at Figure 2 and comparing the curves, we find that the curves of the ND6 proteins of human, gorilla, P. chimpanzee, and C. chimpanzee are more similar. Also, the Evolutionary Bioinformatics 2014:10 ND6 protein graphs are more similar for F. whale, B. whale and rat, mouse too. In addition, we find ND6 protein of opossum is obviously different from the other species. Also their similarities/dissimilarities are consistent with the known fact of evolution.
Unexpectedly, we find that most amplitudes of amino acid are greater than 0, which may mean that amino acids' preferences are hydrophobic in the protein sequence according to the four classifications of amino acids. It is probably because hydrophobic amino acids have an important influence on protein structures.

results/discussion
Once we have a matrix to represent a sequence, numerous matrix invariants 25,26,[30][31][32][33] are used as descriptor of sequences. However, the computational complexity of these matrix invariants techniques is at least O(N 2 ), which results in the main difficulty in computation. In this section, we overcome the difficulty and introduce a novel way to numerically characterize protein sequence and it is easy to implement. Their computational complexities are reduced to O(N), so it is easy to implement. In addition, the new sequence descriptor is linearly relative to the length of the sequences, so it is appropriate for sequences of significantly different lengths.
When we construct the spectrum-like graph, we calculate the summation of four consecutive numbers of a digit sequence. The summations are considered as the amplitudes, which can be −8, −7, −6, −5, −4, −3, −2, −1, 0, 1, 2, 3, 4, 5, 6, 7, and 8. In order to obtain the numerical representation of protein sequences, we calculate the frequency of amplitude. Therefore, a protein sequence can be characterized by a 17D vector.
The data set consists of 13 proteins (cytochrome oxidase subunits I, II, and III; cytochrome b apoenzyme; NADH dehydrogenase subunits 1-6 and 4L; ATP synthase subunits 6 and 8) encoded by the typical mitochondrial genome from mammalian species.
The information of the 13 proteins is listed in Table 2. The 13 proteins are concatenated into one long amino acid sequence and analyzed as one protein sequence. Their frequencies of amplitudes are obtained and listed in Table 3. According to the results obtained in Table 3, we construct 17-component vectors of the spectral graphs corresponding to 9 species proteins, and then the 17-component vectors are first normalized. For a vector X, normalization means: Z = (X−Mean(X))/Std(X), Mean(X), means the mean of X and Std(X) is the standard deviation of X. In Table 4, the similarity/dissimilarity matrices for the nine species protein sequences are given, which are based on the   assumption: the smaller the distance between two proteins is, the more the two proteins will be similar. We know that the smaller the index of similarity/dissimilarity is, the more similar the two proteins will be. The indexes of similarity/ dissimilarity between the nine species are listed in Table 4.
Observing Table 4, we can find that the smaller entries are associated with the pairs in group human, gorilla, P. chimpanzee, and C. chimpanzee; F. whale, B. whale; and rat, mouse. On the other hand, the larger entries in the similarity/ dissimilarity matrix appear in the rows belonging to opossum. These results are consistent with the known conclusion of evolution. 12,25 We calculate the theory values of frequency for the amplitudes which are listed in Table 5. As the theory values are symmetrical, we only show one half. We intend to know whether the frequencies of amplitudes for the 13 proteins in the 9 species are consistent with the ratios of theory values. In Figure 6, we show the comparison charts of 13 proteins of human and the theory values. Then, we calculate the χ 2 values: The χ 2 values of 13 proteins for 9 species are listed in Table 6.

=
in Table 6, so they are not consistent with the ratios of theory values. The amino acid sequences of proteins determine the protein structure and function. So their patterns are not expected to be random.
Firstly, we will make a comparison for helicase protein sequences of 12 baculoviruses, including 3 group I alphabaculovirus: AcMNPV, BmNPV, RoMNPV; 6 group II alphabaculovirus: HearNPV, HzSNPV, MacoNPVA, MacoNPVB, HaSNPV, AgseNPV; 3 betabaculovirus: AdorGV, CpGV, CrleGV. Length and group information of these protein sequences are shown in Table 7. The phylogenetic tree of 12 helicase protein sequences is given in Figure 3. Their  Euclidean distances between the 17-component vectors normalized. We give two arbitrary sequences S 1 and S 2 . In our approach, the Euclidian distance D(S 1 , S 2 ) between the two vectors is The analysis of similarities/dissimilarities represented by the index of similarity/dissimilarity is based on the following similarities/dissimilarities are consistent with classification of these baculovirus proteins. [34][35][36] To further verify the validity of our approach, we have done an experiment on a dataset of the 13 proteins encoded by the same strand of the mitochondrial genome from 20 eutherian species: human (Homo sapiens), C. chimpanzee (Pan troglodytes), P. chimpanzee (Pan paniscus), gorilla (Gorilla gorilla), orangutan (Pongo pygmaeus), gibbon (Hylobates lar), baboon (Papio hamadryas), horse (Equus caballus), white rhinoceros (Ceratotherium simum), harbor seal (Phoca vitulina), gray seal (Halichoerus grypus), cat (Felis catus), F. whale (Balaenoptera physalus), B. whale (Balaenoptera musculus), cow (Bos taurus), rat (Rattus norvegicus), mouse (Mus musculus), opossum (Didelphis virginiana), wallaroo (Macropus robustus), and platypus (Ornithorhynchus anatinus). Note that we have kept rodent species to murids only and marsupials and monotremes are being used as out-group. The phylogenetic tree of 20 species is given in Figure 4. We also construct a phylogenetic tree by the Clust-alW method. 37 The result is shown in Figure 5.
Comparing Figures 4 and 5, we can find that: (1) they all distinguish the marsupials and monotremes, rodents, ferungulates, and primates; (2) it has been debated which two of the three main groups of placental mammals are closely related: primates, ferungulates, and rodents. Figure 4 supports the suggestion that primates and ferungulates are more closely related, whereas Figure 5 shows that primates and rodents are more closely related; (3) in Figure 5, opossum, wallaroo, and platypus as the out-group, was nearly clustered to rodents. The result of Figure 4 is consistent with the known conclusion of evolution and others' partial results 38,39 except for the opossum, so our method is more advantageous in this regard.
To show the efficiency of the proposed approach, based on different protein families, we further make a comparison with the widely used methods, EMBOSS water -pairwise sequence alignment. Then, we test some families by the two methods, including 13 protein families encoded by the same strand of the mitochondrial genome, UDP glucuronosyltransferase family proteins (including the same genus but different species), and so on. The test results show that the similarity distances or scores by different methods are almost in an agreement with each other. Furthermore, for longer protein sequences the test results by the two methods are more consistent.  . the phylogenetic tree of 20 eutherian species based on our method. Phylogeny was based on analysis of the combined sequences of 13 proteins encoded by the same strand of the mitochondrial genome. sequences include those for human, common chimpanzee, pigmy chimpanzee, gorilla, orangutan, gibbon, baboon, horse, white rhinoceros, harbor seal, gray seal, cat, fin whale, blue whale, cow, rat, mouse, opossum, wallaroo, and platypus. the sequences of opossum, wallaroo, and platypus were used as out-group.  5. the phylogenetic tree of 20 eutherian species based on clustalW. Phylogeny was based on analysis of the combined sequences of 13 proteins encoded by the same strand of the mitochondrial genome. sequences include those for human, common chimpanzee, pigmy chimpanzee, gorilla, orangutan, gibbon, baboon, horse, white rhinoceros, harbor seal, gray seal, cat, fin whale, blue whale, cow, rat, mouse, opossum, wallaroo, and platypus. the sequences of opossum, wallaroo, and platypus were used as out-group.

conclusions
The graphical techniques of biological sequences have been used as a very powerful tool for the visualization and analysis of protein sequences. Based on the hydrophobicity of amino acids, a new spectral representation of proteins is introduced, in this study.
1. We present a spectrum-like graphical representation of protein sequences, which are based on a significant physicochemical property. The chemical or physical property of amino acids will also be useful to study and solve some bioinformatics problems. The advantage of our approach is that it allows visual inspection of data, which helps recognize major similarities among different proteins, and even protein structures. 2. For long protein sequences, the frequencies are easily computed and can be used to numerically characterize protein sequences, and the examination of similarity/ dissimilarity illustrates the utility of the approach. The computational complexity of alignment method and matrix invariant technique is at least O(N 2 ). Our method does not require multiple sequence alignments and greatly reduces the computational complexity at the same time. 3. Our approach also gives novel numerical characterization of proteins. One is based on the frequencies of amplitudes of spectral graphs and the other is based on the χ 2 , which are used to analyze the similarity of protein sequences. Also, both computational scientists and molecular biologists can use them to analyze protein sequences efficiently. 4. Theory values of frequencies of amplitudes are calculated.
The results of the compatibility test show that the distribution of hydrophilic-hydrophobic amino acids may have special biological significance. To a certain degree, our method can extract the information underlying the chronological dependencies of structural features and is successfully applied to sequences comprising similar structural features in chronologically different positions. Also, the other physicochemical properties of amino acids will also be useful to study and solve some bioinformatics problems.