BACKGROUND
protein-protein interactions play a key role in cellular functions, and thus, to complement the experimental approaches  <cit> , many computational methods have recently been developed in systems biology for predicting whether two proteins interact, based on what is already known about these proteins.
one type of data used for prediction is the phylogenetic profile of a protein – a string of ones and zeros encoding respectively the presence and absence of the protein in a group of genomes, conserved operons, gene fusions, etc.
<cit> .
the rationale is that interacting proteins tend to co-evolve, and therefore should have similar phylogenetic profiles.
recently, to enhance the prediction accuracy, the focus has been given to using the similarity of phylogenetic trees to infer interactions between receptors and ligands  <cit> .
of particular interest is the so-called mirror tree method by pazos and valencia  <cit> .
the mirror tree method predicts protein-protein interactions under the assumption that the interacting proteins show similarity in the molecular phylogenetic protein trees because of the co-evolution caused by the interaction.
however, it is difficult to directly evaluate the similarity between a pair of molecular phylogenetic trees.
instead, the mirror tree method compares a pair of distance matrices by calculating the pearson correlation coefficient for the corresponding elements in the two matrices, and uses the correlation coefficient as a measure to evaluate the extent of co-evolutionary behavior between two proteins.
to address the issue of high rate of false positives with the mirror tree method, recently, sato et al  <cit>  suggested that the information about the phylogenetic relationships of the host genomes be excluded by a projection operation, and only the residual information in the distance matrices be used for the calculation of the correlation coefficient between proteins.
as a result, significant improvement in prediction specificity was achieved, though at a cost of losing some sensitivity.
a similar yet more sophisticated approach is proposed in pazos et al  <cit>  to correct the distance matrices based on the phylogenetic tree, which incorporates information on the overall evolutionary histories of the species .
in addition to adjusting the distance matrices by excluding the expected background similarity due to the underlying speciation events, this tree of life mirror tree  method can also detect non-canonical evolutionary events, in particular horizontal gene transfers.
while both pazos et al's tol-mirrortree method and sato et al's projection approach are concerned with – and quite successful at – removing some background from the inter-matrix correlation, like the original mirror tree method they do not directly address the intra-matrix correlations, which can be informative and critical in revealing co-evolution.
for example, in some recent related studies, the columns and rows of the distance matrices are reshuffled in an attempt to discover maximal similarity between two matrices in order to predict interaction specificity when paralogs are involved  <cit> .
in this work, we propose a novel, simple method to extract the intra-matrix correlational information with reference to the species tree of the host genomes and to represent said information in a way that is conducive to a supervised learning paradigm.
we tested our method on the same dataset used in  <cit> , which consists of interacting proteins from e. coli, where these interactions are experimentally verified.
the results from a series of leave-one-out cross validation experiments showed that the prediction accuracy was greatly increased with our data representation method.
methods
dataset
we selected the same data set as used in  <cit> , so that the performance of the different methods can be compared.
the  <dig> pairs of interacting proteins are from e. coli, and the interaction within each pair has been experimentally verified, as documented in the database of interacting proteins   <cit> , and no interaction outside the pairing is known.
so, these  <dig> proteins make up  <dig> × 25/ <dig> =  <dig> distinct pairs but only  <dig> of them contain truly interacting partners.
for each of these  <dig> proteins, its putative orthologs from  <dig> bacterial genomes are selected from kegg/ko database  <cit> , and a  <dig> ×  <dig> distance matrix is constructed, giving the genetic distance between any pair of these  <dig> orthologs.
the genetic distances were calculated using the protdist module in the phylip package  <cit>  and the score table by jones, taylor, and thornton  <cit> , from a multiple alignment of these  <dig> orthologous proteins, constructed using mafft  <cit>  software.
the  <dig> pairs of proteins and the  <dig> source organisms are listed in tables  <dig> and  <dig> respectively.
the phylogenetic tree for these  <dig> reference bacterial genomes was built from the 16s rrna sequences using the neighbor-joining module in phylip package.
the 16s rrna sequences were downloaded from the kegg/genes database  <cit>  and the ribosomal database project-ii release  <dig>  <cit> .
phylogenetic vectors and correlations
the original mirror tree method is proposed by pazos and valencia  <cit>  to infer protein-protein interaction from correlated evolutions.
the hypothesis is that two proteins should have a higher chance to share correlated evolutionary history if they interact with each other than if they do not.
as the evolutionary history for a protein can be represented as a phylogenetic tree , it makes sense to compare the two protein trees to reveal any correlation between their evolutionary history.
instead of comparing two trees directly, which is a highly nontrivial task in terms of both algorithmic implementation and biological interpretation, the mirror tree method uses as a surrogate the distance matrices that store the genetic distance between the protein and its orthologs in a group of genomes.
it is from these distance matrices that the proteins trees are typically reconstructed using well known algorithms such as neighbor-joining  <cit> .
for two proteins a and b, the mirror tree method compares their distance matrices da and db, by examining how the corresponding elements are correlated.
because the distance matrices are symmetric, only the elements in the upper  triangle of the matrices are needed to calculate the correlation, which is measured as the pearson correlation coefficient ρ as defined below:
ρab=∑i=1n−1∑j=i+1n−ave)−ave)varvar
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaaiigacqwfbpgcdawgaawcbagaeeyqaekaeeoqaieabeaakiabg2da9maalaaabawaaabmaeaadaaewaqaaiabcicaoiabdseaenaabaaaleaacqqgbbqqaeqaaogaeiikagiaemyaakmaeiilawiaemoaaomaeiykakiaeyoei0iaeeyqaekaeeodaynaeeyzaumaeiikagiaemiraq0aasbaasqaaiabbgeabbqabagccqggpaqkcqggpaqkcqggoaakcqwgebardawgaawcbagaeeoqaieabeaakiabcicaoiabdmgapjabcycasiabdqgaqjabcmcapiabgkhitiabbgeabjabbaha2jabbwgaljabcicaoiabdseaenaabaaaleaacqqgcbgqaeqaaogaeiykakiaeiykakcaleaacqwgqbgacqgh9aqpcqwgpbqacqghrawkcqaixaqmaeaacqwgubgba0gaeyyeiuoaasqaaiabdmgapjabg2da9iabigdaxaqaaiabd6gaujabgkhitiabigdaxaqdcqghris5aagcbawaaoaaaeaacqqgwbgvcqqghbqycqqgybgccqggoaakcqwgebardawgaawcbagaeeyqaeeabeaakiabcmcapiabbafawjabbggahjabbkhayjabcicaoiabdseaenaabaaaleaacqqgcbgqaeqaaogaeiykakcaleqaaaaakiaaxmaacawljawaaewaaeaacqaixaqmaiaawicacaglpaaaaaa@7b33@
where ave and var represent the average and the variance of the elements in the upper triangle of a distance matrix, respectively.
to apply this method for prediction, the pearson correlation coefficient ρ is calculated for all distinct pairs of proteins, and these pairs are then ranked in a non decreasing order of ρ. with a threshold preset on ρ, the pairs with a higher correlation coefficient are predicted to be interacting pairs.
in two recent works  <cit> , the measurement of correlations is refined by excluding the information about the phylogenetic relationships in order to overcome the problem of high rate of false positives reportedly present in the predictions using the mirror tree method.
the high rate of false positives is believed to be caused by a high correlation between non-interacting proteins, which can be attributed to some common background shared by the two corresponding distance matrices, because they all are derived from orthologous proteins in the same set of n source organisms.
that is to say, these protein trees bear some resemblance to the species tree.
sato et al therefore propose to exclude the species tree resemblance from the distance matrices before comparing them.
specifically, a distance matrix r is computed for the 16s rrna sequences of these  <dig> genomes, from which the species tree can be reconstructed.
for convenience, all the rows in the upper triangle of this  <dig> ×  <dig> distance matrix are concatenated, producing a vector of dimension  <dig>  which we refer to as |u16s>.
similarly, all the distance matrices for the protein trees can be transformed into a vector form, of the same dimension  <dig>  which is termed the phylogenetic vector.
let |vi>  be a phylogenetic vector for one of the  <dig> proteins in the dataset, then the resemblance of |vi> to |u16s> is measured by the projection < u16s|vi > , which is then subtracted from |vi>, giving a residue vector |εi> defined as follow:
|εi> = |vi> - |u16s>
then, the pearson correlation coefficient ]}/√,
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqahbpgcdawgaawcbagaeeyaakmaeeoaaogabeaakiabg2da9iabfo6atnaabaaaleaacqqgrbwacqgh9aqpcqaixaqmcqqggaaicqqg0badcqqgvbwbcqqggaaicqai4aaocqaiyagmcqaiwaamaeqaaogaei4easnaei4waslaeiifawnaeqytdu2aa0baasqaaiabbmgapbqaaiabbugarbaakiabg6da+iabb2catiabbccagiabbgeabjabbaha2jabbwgaljabcicaoiabcyha8jabew7alnaabaaaleaacqqgpbqaaeqaaogaeyopa4jaeiykakiaeiyxa0laei4waslaeiifawnaeqytdu2aa0baasqaaiabbqgaqbqaaiabbugarbaakiabg6da+iabb2catiabbccagiabbgeabjabbaha2jabbwgaljabcicaoiabcyha8jabew7alnaabaaaleaacqqgqbgaaeqaaogaeyopa4jaeiykakiaeiyxa0laeiyfa0naei4la8cccagae8ngiytaei4waslaeeovaylaeeyyaemaeeocainaeiikagiaeiifawnaeqytdu2aasbaasqaaiabbmgapbqabagccqgh+agpcqggpaqkcqqgwbgvcqqghbqycqqgybgccqggoaakcqgg8bafcqah1oqzdawgaawcbagaeeoaaogabeaakiabg6da+iabcmcapiabc2fadjabcycasiaaxmaacawljawaaewaaeaacqaizawmaiaawicacaglpaaaaaa@8f07@
where |εik>
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqgg8bafcqah1oqzdaqhaawcbagaeeyaakgabagaee4aasgaaogaeyopa4daaa@33c8@ stands for the k-th component of vector |εi>, ave and var represent the average and variance of elements in a vector.
it is shown in  <cit>  that the specificity of predictions using the subtracted vectors is significantly improved, though at a cost of losing sensitivity.
in  <cit> , phylogenetic trees  are first reconstructed from the multiple sequence alignments of orthologous proteins using the neighbor-joining algorithm implemented in clustalw.
the protein distance matrices are then derived from these trees by summing the length of the branches connecting each pair of orthologous proteins, which are represented as tree leaves.
new distance matrices for the proteins are obtained by subtracting from each value the distance between the corresponding species in the 16s rrna distance matrix, termed as r. if we transform the matrices into vectors in the same way as used in  <cit> , then the element-wise subtraction of 16s rrna distance matrix r from a distance matrix p for a protein is equivalent to subtraction of two corresponding vectors,
|p'> = |p> - |r>
where |p> is the phylogenetic vector derived from the upper triangle of matrix p, and |r> is the vector from the upper triangle of matrix r. the difference between eq and eq can be seen more clearly as depicted geometrically in figure  <dig>  it is noted that the resulting vector |ε> derived from eq is guaranteed to be orthogonal to the phylogenetic tree orientation, whereas the resulting vector from eq may still have non-zero projection along the phylogenetic tree orientation, which can become minimal when the two vectors are properly rescaled using a "molecular clock" to about the same length  <cit> .
it is also worth noting that although having phylogenetic vectors totally orthogonal to the phylogenetic tree orientation may be mathematically sound and attractive, it by no means necessarily leads to better learning and classification, as many other factors may affect the similarity between a pair of phylogenetic vectors, e.g., when there are horizontal gene transfers as pointed out and dealt with in  <cit> .
super-phylogenetic vectors via treesec method
we propose a novel method to utilize the distance matrices and the species tree for predicting protein interactions.
there are two major changes to the mirror tree method.
first, we augment the phylogenetic vectors with extra bits that encode the topological information of the protein tree with reference to the species tree.
second, in contrast to the unsupervised learning scheme of the mirror tree method, we adopt a supervised learning paradigm, specifically the support vector machines,  <cit>  to further tap into the prior knowledge about interacting and non interacting protein pairs.
as all proteins are already represented as the phylogenetic vectors of the same dimension, it is convenient to concatenate the two vectors for any pair of proteins and use the concatenated vector to represent the pair.
all pairs thus represented are then split into to two subsets – one subset is used for training and the other for testing.
the key contribution of our method comes with the data representation, in which we augment the phylogenetic vector, used in both the original and sato et al's modified version of mirror tree, with some organizational information about the elements in the distance matrix; such information reflects in a somewhat explicit way how the protein tree is reconstructed from the distance matrix, with reference to the species tree.
in the mirror tree method, all the elements in the distance matrix are treated equally, as indicated by the un-weighted summation of the product   over all  in calculating the pearson correlation coefficient as defined in eq.
the very rich intra-matrix correlational information is almost entirely neglected and is condensed to just a single number – the average ave, to which the deviation  is measured for each element  and correlated with its counterpart from the other matrix b and then factored into the inter-matrix correlation ρab.
for example, if element da is above the average in the matrix da and db is above the average in matrix db, then the product   is positively contributing to the correlation ρab, and thus to the similarity.
in another case, if da is above the average in the matrix da but db is below the average in matrix db, then the product   is negatively contributing to the correlation ρab, and thus to the similarity.
and each element in the distance matrix is treated independently and equally.
however, to a very large degree, it is the intra-matrix correlations among the elements that determine the protein tree, as manifested in the distance based phylogenetic tree reconstruction algorithms such as upgma and neighbor-joining  <cit> .
for example, as shown in figure  <dig>  if  corresponds to two host genomes i and j closely positioned in the tree and  to a pair of distantly related genomes i' and j', then it makes sense to weight   and   differently when contributing to the correlation ρab in eq.
when measuring matrix similarity, not only may elements in a matrix contribute differently, but the very fact that a tree can be reconstructed out a distance matrix imparts a clear indication of some embedded "intra-matrix" correlations among matrix elements.
therefore it is reasonable to hypothesize that the matrix elements need to be regrouped in a certain way such that the hierarchical relationships among matrix elements can be unraveled and flattened to achieve the effect of "weighted" pearson correlation between two matrices.
this is somehow similar to the ideas in  <cit>  where, to predict interaction specificity among paralogous proteins, the rows and columns of the distance matrices are reshuffled in order to find maximal similarity measured as inter-matrix correlation.
as the species tree bestows a hierarchy of relationships among the host genomes, weighting the matrix elements in order to reflect the intra-matrix correlations can become very complicated.
here we propose a simple, novel way to account for the intra-matrix correlations.
specifically, we use the species tree  to generate a hierarchical clustering of the genomes, which correspondingly gives a hierarchical clustering of the indices of the protein distance matrices.
given a tree with the root at the top, a "section" cut across the tree will give rise to clusters of leaves, i.e., leaves within the same branch at the section will belong to the same cluster.
the number of clusters is equal to the number of branches at the section, and is determined by the tree and the height where the section is cut – the higher the cut is, the fewer the number of clusters is.
for example, in figure  <dig>  section <dig> generates  <dig> clusters: α, β, γ and δ. given a protein distance matrix d, for each section, an intermediate distance matrix between all pairs of clusters is derived from the original distance matrix as follows.
d = ∑i∈cα;j∈cβ/|cα| |cβ|
where |cα| and |cβ| are the size for the clusters cα and cβ respectively.
that is, the distance between two clusters cα and cβ is equal to the average distance between pairs of orthologous proteins from each cluster.
this definition of distance between two clusters is the same as defined in upgma during the tree reconstruction  <cit> .
the intermediate distance matrix gives a "snapshot" of the evolutionary history about these orthologous proteins at the time, marked as the tree height, where the section is cut.
the snapshot – rather the intermediate matrix derived from it – carries the information about how the hypothetical ancient ancestors at that time are related to one another in terms of evolutionary distance, from the perspective of the protein being studied.
since the matrix is symmetric, only the upper  triangle is needed, which can be transformed into a vector form and concatenated to the original phylogenetic vector in the mirror tree method.
the final representation of a protein is the original phylogenetic vector concatenated with all "snapshot" vectors, which is called super-phylogenetic vector.
figure  <dig> gives a schematic illustration of the procedure for generating the super-phylogenetic vectors.
the number of "snapshots" is a free parameter in our method.
one simple way to remove this parameter is to use the full spectrum of sections, i.e., having a section made at each branching point in the tree.
the difficulty with this full spectrum approach is that the number of sections is large, and many of the neighboring sections are very similar to one another, and therefore not adding much useful information to the phylogenetic vectors; rather it may inflate the dimension of the resulting super-phylogenetic vectors up to  <dig>  or higher, which is beyond the capacity of the classifier used in the study.
instead, a value of  <dig> is used as the number of snapshots taken in the experiments, which yields a dimension of  <dig> for super-phylogenetic vector pairs versus the  <dig> for the original phylogenetic vector pairs.
one refinement made while generating the super-phylogenetic vector is to first adjust the distances, as defined in neighbor-joining algorithm to remove the molecular clock constraint assumed by the upgma:
d = d -
and
ri = ∑k d/
where |l| is the dimension of the matrix d. another refinement is to use the same projection procedure introduced in sato et al's modified mirror tree method eq, only now that |vi> and |u16s> are substituted with the super-phylogenetic vectors.
it should be noted that since the background subtraction in tol-mirrortree method and sato et al's method also utilizes the phylogenetic tree, combining the treesec procedure and background subtraction may introduce some redundancy.
the use of the species tree instead of individual protein trees for hierarchical clustering has a twofold effect.
one effect is more theoretical; it is to reveal how individual protein trees  would differ from the underlying species tree of the host genomes, in the same spirit of subtracting the common background as in  <cit> .
the other effect is more pragmatic; it ensures that the super-phylogenetic vectors thus obtained have the same dimension for all proteins, and therefore can be readily used as input to the support vector machine.
svm
the classifier used here is a support vector machine.
as a powerful statistical learning method, support vector machines , originally proposed by vapnik  <cit> , have recently been applied with remarkable success in bioinformatics problems, including remote protein homology detection, microarray gene expression analysis, and protein secondary structure prediction  <cit> .
there are a couple of reasons to use svms.
first, the data are already in the vector form, particularly suitable as inputs for svms.
second, svms have been used to predict protein-protein interaction in previous works  <cit> , though there the different properties of proteins are used.
we plan to have a comprehensive study of using svm on data from different sources, and more importantly, how to combine them for better prediction.
third, svms have some inherent advantages over other classifiers, including:  <dig>  quadratic programming to avoid local minima,  <dig>  geometric intuition,  <dig>  lower vapnik-chervonenkis dimension leading to better generalization, and  <dig>  amicability with small training samples, which all contribute to its popularity as a classifier adopted in many applications.
the basic idea of svms is simple; it is to find a hyperplane that separates two classes of objects, as represented as points in a vector space, with the maximum margin to the boundary lines.
such a hyperplane ensures good generalization and unseen data are then classified according to their location with respect to the hyperplane.
the power of svms comes partly from the data representation, where an entity, e.g., a pair of proteins, is represented by a set of attributes.
however, how those attributes contribute to distinguishing a true positive from a true negative may be quite complex.
in other words, the boundary line between the two classes, if depicted in a vector space, can be highly nonlinear.
the svms method will find a nonlinear mapping that transform the data from the original space, called input space, into a higher dimensional space, called feature space, where the data can be linearly separable.
in general, the mapping can be quite complex and the dimension can be very  high in order for the mapped data to be linearly separable.
the trick of svms is the use of kernel functions, which define how the dot product between two points in the feature space, which is the only quantity needed to solve the quadratic programming problem for finding the maximum margin hyperplane in the feature space.
the use of kernel functions avoids explicit mapping to high dimensional feature space; high dimensionality often poses difficult problems for learning such as over-fitting, thus termed the curse of dimensionality.
polynomial kernel and gaussian kernel are the two most commonly used generic kernels – linear kernel is not really useful in most cases except when the data are linearly separable.
for vectors x and y, gaussian rbf is defined as
k = exp,
and the polynomial kernel is defined as
k = d,
where c, s and d are parameters adjustable in the software package svmlight  <cit> .
both kernels are experimented with the default values for c, s and d, and the gaussian kernel yielded the best results reported in this paper.
because the polynomial kernel performs significantly worse with the default setting, we also tested with changing the polynomial degree d from the default value .
we found that the performance is quite sensitive to the degree.
details are given in the next section.
besides using the separation of training and testing as a mechanism to alert us to overfitting, another mechanism built into svmlight for avoiding overfitting is the use of "soft" margin, i.e., to allow for misclassification for some outlier training data points, and a cap on the number of iterations to stop the optimization process during the training even if the preset error rate is not reached.
and we have used svmlight's default setting for our experiments.
it is worth noting that, overall our method can be viewed as a hybrid that employs in tandem both an explicit mapping, from phylogenetic vectors to super-phylogenetic vectors, and the use of a generic kernel.
RESULTS
we test our treesec method in a series of leave-one-out cross-validation experiments on the data set described above.
to prepare an experiment, one of the  <dig> interacting pairs is selected and reserved as the positive testing example, and  <dig> non interacting pairs that contain one protein from the positive testing example are reserved as negative testing examples.
the rest  <dig> -  <dig> =  <dig> pairs are used as training examples, among which there are  <dig> interacting pairs as positive training examples.
by rotating the positive testing example among the  <dig> interacting pairs, we can design  <dig> such leave-one-out cross validation experiments, and the average performance is reported.
for each experiment, the training examples are taken as input to train a support vector machine.
the implementation of the support vector machine is adopted from the svmlight package  <cit> .
the two commonly used kernel functions – polynomial, and rbf – are experimented with the default parameter settings, and the gaussian rbf kernel function scored the best performance, which is reported in table  <dig>  with the svm trained, the  <dig> testing examples are then input to it for prediction.
a score with real value between - <dig> and + <dig> is assigned by the svm to each testing example.
ideally, a positive score indicates a predicted positive, whereas a negative score indicates a predicted negative.
this implies a perfect cutoff score at zero.
in practice, the cutoff score may be set at a different value, other than zero.
indeed, its actual value does not matter, as long as the predicted positives  are true positive, and the predicted negative  are true negative.
to evaluate the performance, we use the receiver optical characteristic  score, which is the normalized area under a curve that plots the number of true positives as the number of false positives when a moving cutoff score scans from + <dig> to - <dig>  <cit> .
the roc score is  <dig> for a perfect performance, whereas a random predictor, which will uniformly mix up positives and negatives, is expected to get a roc score  <dig> .
some roc curves for our experiments are shown in figure  <dig>
the roc scores of the mirror tree method and our treesec method, with a few variations, are reported in table  <dig>  since the mirrortree is an unsupervised learning method, to be fair, we first use treesec in an unsupervised learning manner, and compare the two.
in this case, since there is no training necessary, for each leave-one-out experiment, only the testing examples are ranked by their pearson correlation coefficients as if they were scores output from a classifier.
the mirror tree method using the phylogenetic vectors prepared via sato et al's procedure receives a roc score  <dig> .
a slightly higher roc score  is obtained when everything is kept the same except for substituting the phylogenetic vectors with the super-phylogenetic vectors prepared via treesec method.
the advantage of treesec method becomes more obvious when used in supervised learning.
in this case, treesec and mirrortree are compared for their capability of representing proteins in a way which is more conducive for classification.
once proteins are represented as super-phylogenetic vectors via treesec or as phylogenetic vectors via mirrortree, they are fed into the same classifier, in this case, a svm.
as we see in table  <dig>  while the performance of the phylogenetic vectors  also improves , the super-phylogenetic vectors prepared by treesec obtain a significantly better roc score .
because of the significantly worse performance for polynomial kernel with a default degree d =  <dig>  we tested with changing the degree to different values and found that the performance is significantly better for even values than odd values of d. this phenomenon may be an indication of the parity of the hyperplane in the feature space: symmetric with respect to changing the sign of the coordinates.
overall in table  <dig> better performance has been noted for "treesec × 10" when the "snapshots" are taken at a more spacious interval by multiplying the tree height with a factor of  <dig>  because the distances obtained from the phylip software are typically small fraction numbers, dividing the distances at the "cutting" points tend to yield rounding errors, and a re-scaling of the distances in the tree to bigger values proved to be helpful with avoiding such a problem.
in table  <dig>  the effect of the re-scaling factor of the learning performance is given, showing that gaussian kernel is more affected by the rescaling than is the polynomial kernel.
the dimension of the super-phylogenetic vectors from treesec is obviously higher than that of the phylogenetic vectors in mirrortree, since the former is derived by concatenating extra bits of information to the latter.
although this may raise concerns with a judicious reader about the fairness for comparing the two approaches if they have different sizes of data, it should not be a problem in our case, because we use the same amount of input data as the sato et al's approach – the same distance matrices with the same size for proteins and the same distance matrix for species .
the extra bits of information are not really extra; they are the result of how we unravel the information embedded in the input data.
in a sense, our method is a hybrid of combining the explicit mapping  and the use of kernels, which may explain why our method bodes well with the learning task.
nonetheless, care should be taken to not let the increase of dimension go unchecked, as redundancy may arise and lead to overfitting and bad generalization.
that is part of the reason that only "snapshots" of evolutionary history are incorporated.
it is not surprising that the neighbor-joining distance adjustment is essential; without it as shown in table  <dig> the performance decreases significantly .
to verify that the better performance indeed arises from incorporating the intra-matrix correlations, we run the same experiments on the data prepared using a random species tree, we can see in table  <dig> that the roc scores are consistently low at around  <dig>  for cases when a random tree is used.
to further examine the performance, in figure  <dig>  roc curves are shown for those roc scores reported in table  <dig> for the unsupervised learning based on pearson correlation coefficient and for the supervised learning with a gaussian kernel svm.
given the y-axis as the true positives and x-axis as the false positives, the higher a curve means more true positives are identified at cost of a given number of false positives.
it is consistent to note that "treesec × 10" corresponds to the top curve overall.
also remarkable is the steep slope for the two roc curves corresponding to the unsupervised learning  at small false positive rates .
this explains the high specificity for these unsupervised learning based on correlation coefficient, and is consistent with what is reported in  <cit> .
as moving to the right , these two curves quickly lose the upward momentum , an indication of low sensitivity.
therefore, the supervised learning using the svms in these experiments offers a better balance between sensitivity and specificity.
it is worth noting that, the highly skewed learning problem is likely a reflection of situations in the real world, i.e., there are far more negatives than positives.
in our case, given n proteins that uniquely interact with only one other member, there are only n/ <dig> positive pairings among the / <dig> possible pairings of these n proteins.
that is, the interacting network, with nodes representing the proteins and edges representing the interactions, is quite sparse, but our method is still applicable when there are more edges.
because every possible pair of nodes is assigned a score in our method, predictions can be made by going down a list of all pairs that are ranked by their scores in decreasing order.
so, regardless the number of the actual edges in the network , the method works, and perfectly so as long as the true interacting pairs are ranked higher than non interacting pairs in the prediction.
indeed, this scheme is also widely used in predicting protein interaction networks in general, both in an unsupervised paradigm such as the original mirror tree method, and in a supervised learning paradigm.
CONCLUSIONS
to summarize, in this work we developed a novel, simple method to explore the intra-matrix correlational information embedded in the distance matrices and incorporate such information into a data representation which is conducive to supervised learning.
three methods recognize the importance of the phylogenetic tree, both sato et al's projection method  <cit>  and pazos et al's tol-mirrortree  <cit>  try to "subtract" from the similarity  the effect due to speciation rather than the interaction pressures, whereas our method seeks to "unravel" the intrinsic structure of the distance matrices using the species tree as a guide and then "concatenate" these snapshots of the evolutionary history to the current view  of the proteins.
that is, the main difference between subtracting and adding is that the former is more appropriate for removing background noise so as to reduce false positive and the latter is more appropriate for disentangling intra-matrix correlations so as to aid a supervised learner.
as future work, we will study how the reconciliation between protein trees and species tree can be more explicitly represented and how to associate selection pressure imposed by the interaction to specific evolutionary events, e.g., horizontal gene transfers.
competing interests
the author declare that they have no competing interests.
authors' contributions
ll conceived the ideas and prototyped some of the implementation, and rac collected the data and implemented the methods.
both authors participated in writing the manuscript.

 protein-protein interactions play a key role in cellular functions, and thus, to complement the experimental approaches, many computational methods have recently been developed in systems biology for predicting whether two proteins interact, based on what is already known about these proteins. one type of data used for prediction is the phylogenetic profile of a protein – a string of ones and zeros encoding respectively the presence and absence of the protein in a group of genomes, conserved operons, gene fusions, etc.. the rationale is that interacting proteins tend to co-evolve, and therefore should have similar phylogenetic profiles. recently, to enhance the prediction accuracy, the focus has been given to using the similarity of phylogenetic trees to infer interactions between receptors and ligands. of particular interest is the so-called mirror tree method by pazos and valencia. the mirror tree method predicts protein-protein interactions under the assumption that the interacting proteins show similarity in the molecular phylogenetic protein trees because of the co-evolution caused by the interaction. however, it is difficult to directly evaluate the similarity between a pair of molecular phylogenetic trees. instead, the mirror tree method compares a pair of distance matrices by calculating the pearson correlation coefficient for the corresponding elements in the two matrices, and uses the correlation coefficient as a measure to evaluate the extent of co-evolutionary behavior between two proteins. to address the issue of high rate of false positives with the mirror tree method, recently, sato et al suggested that the information about the phylogenetic relationships of the host genomes be excluded by a projection operation, and only the residual information in the distance matrices be used for the calculation of the correlation coefficient between proteins. as a result, significant improvement in prediction specificity was achieved, though at a cost of losing some sensitivity. a similar yet more sophisticated approach is proposed in pazos et al to correct the distance matrices based on the phylogenetic tree, which incorporates information on the overall evolutionary histories of the species. in addition to adjusting the distance matrices by excluding the expected background similarity due to the underlying speciation events, this tree of life mirror tree method can also detect non-canonical evolutionary events, in particular horizontal gene transfers. while both pazos et al's tol-mirrortree method and sato et al's projection approach are concerned with – and quite successful at – removing some background from the inter-matrix correlation, like the original mirror tree method they do not directly address the intra-matrix correlations, which can be informative and critical in revealing co-evolution. for example, in some recent related studies, the columns and rows of the distance matrices are reshuffled in an attempt to discover maximal similarity between two matrices in order to predict interaction specificity when paralogs are involved. in this work, we propose a novel, simple method to extract the intra-matrix correlational information with reference to the species tree of the host genomes and to represent said information in a way that is conducive to a supervised learning paradigm. we tested our method on the same dataset used in, which consists of interacting proteins from e. coli, where these interactions are experimentally verified. the results from a series of leave-one-out cross validation experiments showed that the prediction accuracy was greatly increased with our data representation method. methods dataset we selected the same data set as used in, so that the performance of the different methods can be compared. the pairs of interacting proteins are from e. coli, and the interaction within each pair has been experimentally verified, as documented in the database of interacting proteins, and no interaction outside the pairing is known. so, these proteins make up × 25/ = distinct pairs but only of them contain truly interacting partners. for each of these proteins, its putative orthologs from bacterial genomes are selected from kegg/ko database, and a × distance matrix is constructed, giving the genetic distance between any pair of these orthologs. the genetic distances were calculated using the protdist module in the phylip package and the score table by jones, taylor, and thornton, from a multiple alignment of these orthologous proteins, constructed using mafft software. the pairs of proteins and the source organisms are listed in tables and respectively. the phylogenetic tree for these reference bacterial genomes was built from the 16s rrna sequences using the neighbor-joining module in phylip package. the 16s rrna sequences were downloaded from the kegg/genes database and the ribosomal database project-ii release. phylogenetic vectors and correlations the original mirror tree method is proposed by pazos and valencia to infer protein-protein interaction from correlated evolutions. the hypothesis is that two proteins should have a higher chance to share correlated evolutionary history if they interact with each other than if they do not. as the evolutionary history for a protein can be represented as a phylogenetic tree, it makes sense to compare the two protein trees to reveal any correlation between their evolutionary history. instead of comparing two trees directly, which is a highly nontrivial task in terms of both algorithmic implementation and biological interpretation, the mirror tree method uses as a surrogate the distance matrices that store the genetic distance between the protein and its orthologs in a group of genomes. it is from these distance matrices that the proteins trees are typically reconstructed using well known algorithms such as neighbor-joining. for two proteins a and b, the mirror tree method compares their distance matrices da and db, by examining how the corresponding elements are correlated. because the distance matrices are symmetric, only the elements in the upper triangle of the matrices are needed to calculate the correlation, which is measured as the pearson correlation coefficient ρ as defined below: ρab=∑i=1n−1∑j=i+1n−ave)−ave)varvar      mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaaiigacqwfbpgcdawgaawcbagaeeyqaekaeeoqaieabeaakiabg2da9maalaaabawaaabmaeaadaaewaqaaiabcicaoiabdseaenaabaaaleaacqqgbbqqaeqaaogaeiikagiaemyaakmaeiilawiaemoaaomaeiykakiaeyoei0iaeeyqaekaeeodaynaeeyzaumaeiikagiaemiraq0aasbaasqaaiabbgeabbqabagccqggpaqkcqggpaqkcqggoaakcqwgebardawgaawcbagaeeoqaieabeaakiabcicaoiabdmgapjabcycasiabdqgaqjabcmcapiabgkhitiabbgeabjabbaha2jabbwgaljabcicaoiabdseaenaabaaaleaacqqgcbgqaeqaaogaeiykakiaeiykakcaleaacqwgqbgacqgh9aqpcqwgpbqacqghrawkcqaixaqmaeaacqwgubgba0gaeyyeiuoaasqaaiabdmgapjabg2da9iabigdaxaqaaiabd6gaujabgkhitiabigdaxaqdcqghris5aagcbawaaoaaaeaacqqgwbgvcqqghbqycqqgybgccqggoaakcqwgebardawgaawcbagaeeyqaeeabeaakiabcmcapiabbafawjabbggahjabbkhayjabcicaoiabdseaenaabaaaleaacqqgcbgqaeqaaogaeiykakcaleqaaaaakiaaxmaacawljawaaewaaeaacqaixaqmaiaawicacaglpaaaaaa@7b33@ where ave and var represent the average and the variance of the elements in the upper triangle of a distance matrix, respectively. to apply this method for prediction, the pearson correlation coefficient ρ is calculated for all distinct pairs of proteins, and these pairs are then ranked in a non decreasing order of ρ. with a threshold preset on ρ, the pairs with a higher correlation coefficient are predicted to be interacting pairs. in two recent works, the measurement of correlations is refined by excluding the information about the phylogenetic relationships in order to overcome the problem of high rate of false positives reportedly present in the predictions using the mirror tree method. the high rate of false positives is believed to be caused by a high correlation between non-interacting proteins, which can be attributed to some common background shared by the two corresponding distance matrices, because they all are derived from orthologous proteins in the same set of n source organisms. that is to say, these protein trees bear some resemblance to the species tree. sato et al therefore propose to exclude the species tree resemblance from the distance matrices before comparing them. specifically, a distance matrix r is computed for the 16s rrna sequences of these genomes, from which the species tree can be reconstructed. for convenience, all the rows in the upper triangle of this × distance matrix are concatenated, producing a vector of dimension which we refer to as |u16s>. similarly, all the distance matrices for the protein trees can be transformed into a vector form, of the same dimension which is termed the phylogenetic vector. let |vi> be a phylogenetic vector for one of the proteins in the dataset, then the resemblance of |vi> to |u16s> is measured by the projection < u16s|vi >, which is then subtracted from |vi>, giving a residue vector |εi> defined as follow: |εi> = |vi> - |u16s>     then, the pearson correlation coefficient ]}/√,      mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqahbpgcdawgaawcbagaeeyaakmaeeoaaogabeaakiabg2da9iabfo6atnaabaaaleaacqqgrbwacqgh9aqpcqaixaqmcqqggaaicqqg0badcqqgvbwbcqqggaaicqai4aaocqaiyagmcqaiwaamaeqaaogaei4easnaei4waslaeiifawnaeqytdu2aa0baasqaaiabbmgapbqaaiabbugarbaakiabg6da+iabb2catiabbccagiabbgeabjabbaha2jabbwgaljabcicaoiabcyha8jabew7alnaabaaaleaacqqgpbqaaeqaaogaeyopa4jaeiykakiaeiyxa0laei4waslaeiifawnaeqytdu2aa0baasqaaiabbqgaqbqaaiabbugarbaakiabg6da+iabb2catiabbccagiabbgeabjabbaha2jabbwgaljabcicaoiabcyha8jabew7alnaabaaaleaacqqgqbgaaeqaaogaeyopa4jaeiykakiaeiyxa0laeiyfa0naei4la8cccagae8ngiytaei4waslaeeovaylaeeyyaemaeeocainaeiikagiaeiifawnaeqytdu2aasbaasqaaiabbmgapbqabagccqgh+agpcqggpaqkcqqgwbgvcqqghbqycqqgybgccqggoaakcqgg8bafcqah1oqzdawgaawcbagaeeoaaogabeaakiabg6da+iabcmcapiabc2fadjabcycasiaaxmaacawljawaaewaaeaacqaizawmaiaawicacaglpaaaaaa@8f07@ where |εik> mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqgg8bafcqah1oqzdaqhaawcbagaeeyaakgabagaee4aasgaaogaeyopa4daaa@33c8@ stands for the k-th component of vector |εi>, ave and var represent the average and variance of elements in a vector. it is shown in that the specificity of predictions using the subtracted vectors is significantly improved, though at a cost of losing sensitivity. in, phylogenetic trees are first reconstructed from the multiple sequence alignments of orthologous proteins using the neighbor-joining algorithm implemented in clustalw. the protein distance matrices are then derived from these trees by summing the length of the branches connecting each pair of orthologous proteins, which are represented as tree leaves. new distance matrices for the proteins are obtained by subtracting from each value the distance between the corresponding species in the 16s rrna distance matrix, termed as r. if we transform the matrices into vectors in the same way as used in, then the element-wise subtraction of 16s rrna distance matrix r from a distance matrix p for a protein is equivalent to subtraction of two corresponding vectors, |p'> = |p> - |r>     where |p> is the phylogenetic vector derived from the upper triangle of matrix p, and |r> is the vector from the upper triangle of matrix r. the difference between eq and eq can be seen more clearly as depicted geometrically in figure it is noted that the resulting vector |ε> derived from eq is guaranteed to be orthogonal to the phylogenetic tree orientation, whereas the resulting vector from eq may still have non-zero projection along the phylogenetic tree orientation, which can become minimal when the two vectors are properly rescaled using a "molecular clock" to about the same length. it is also worth noting that although having phylogenetic vectors totally orthogonal to the phylogenetic tree orientation may be mathematically sound and attractive, it by no means necessarily leads to better learning and classification, as many other factors may affect the similarity between a pair of phylogenetic vectors, e.g., when there are horizontal gene transfers as pointed out and dealt with in. super-phylogenetic vectors via treesec method we propose a novel method to utilize the distance matrices and the species tree for predicting protein interactions. there are two major changes to the mirror tree method. first, we augment the phylogenetic vectors with extra bits that encode the topological information of the protein tree with reference to the species tree. second, in contrast to the unsupervised learning scheme of the mirror tree method, we adopt a supervised learning paradigm, specifically the support vector machines, to further tap into the prior knowledge about interacting and non interacting protein pairs. as all proteins are already represented as the phylogenetic vectors of the same dimension, it is convenient to concatenate the two vectors for any pair of proteins and use the concatenated vector to represent the pair. all pairs thus represented are then split into to two subsets – one subset is used for training and the other for testing. the key contribution of our method comes with the data representation, in which we augment the phylogenetic vector, used in both the original and sato et al's modified version of mirror tree, with some organizational information about the elements in the distance matrix; such information reflects in a somewhat explicit way how the protein tree is reconstructed from the distance matrix, with reference to the species tree. in the mirror tree method, all the elements in the distance matrix are treated equally, as indicated by the un-weighted summation of the product over all in calculating the pearson correlation coefficient as defined in eq. the very rich intra-matrix correlational information is almost entirely neglected and is condensed to just a single number – the average ave, to which the deviation is measured for each element and correlated with its counterpart from the other matrix b and then factored into the inter-matrix correlation ρab. for example, if element da is above the average in the matrix da and db is above the average in matrix db, then the product is positively contributing to the correlation ρab, and thus to the similarity. in another case, if da is above the average in the matrix da but db is below the average in matrix db, then the product is negatively contributing to the correlation ρab, and thus to the similarity. and each element in the distance matrix is treated independently and equally. however, to a very large degree, it is the intra-matrix correlations among the elements that determine the protein tree, as manifested in the distance based phylogenetic tree reconstruction algorithms such as upgma and neighbor-joining. for example, as shown in figure if corresponds to two host genomes i and j closely positioned in the tree and to a pair of distantly related genomes i' and j', then it makes sense to weight and differently when contributing to the correlation ρab in eq. when measuring matrix similarity, not only may elements in a matrix contribute differently, but the very fact that a tree can be reconstructed out a distance matrix imparts a clear indication of some embedded "intra-matrix" correlations among matrix elements. therefore it is reasonable to hypothesize that the matrix elements need to be regrouped in a certain way such that the hierarchical relationships among matrix elements can be unraveled and flattened to achieve the effect of "weighted" pearson correlation between two matrices. this is somehow similar to the ideas in where, to predict interaction specificity among paralogous proteins, the rows and columns of the distance matrices are reshuffled in order to find maximal similarity measured as inter-matrix correlation. as the species tree bestows a hierarchy of relationships among the host genomes, weighting the matrix elements in order to reflect the intra-matrix correlations can become very complicated. here we propose a simple, novel way to account for the intra-matrix correlations. specifically, we use the species tree to generate a hierarchical clustering of the genomes, which correspondingly gives a hierarchical clustering of the indices of the protein distance matrices. given a tree with the root at the top, a "section" cut across the tree will give rise to clusters of leaves, i.e., leaves within the same branch at the section will belong to the same cluster. the number of clusters is equal to the number of branches at the section, and is determined by the tree and the height where the section is cut – the higher the cut is, the fewer the number of clusters is. for example, in figure section generates clusters: α, β, γ and δ. given a protein distance matrix d, for each section, an intermediate distance matrix between all pairs of clusters is derived from the original distance matrix as follows. d = ∑i∈cα;j∈cβ/|cα| |cβ|     where |cα| and |cβ| are the size for the clusters cα and cβ respectively. that is, the distance between two clusters cα and cβ is equal to the average distance between pairs of orthologous proteins from each cluster. this definition of distance between two clusters is the same as defined in upgma during the tree reconstruction. the intermediate distance matrix gives a "snapshot" of the evolutionary history about these orthologous proteins at the time, marked as the tree height, where the section is cut. the snapshot – rather the intermediate matrix derived from it – carries the information about how the hypothetical ancient ancestors at that time are related to one another in terms of evolutionary distance, from the perspective of the protein being studied. since the matrix is symmetric, only the upper triangle is needed, which can be transformed into a vector form and concatenated to the original phylogenetic vector in the mirror tree method. the final representation of a protein is the original phylogenetic vector concatenated with all "snapshot" vectors, which is called super-phylogenetic vector. figure gives a schematic illustration of the procedure for generating the super-phylogenetic vectors. the number of "snapshots" is a free parameter in our method. one simple way to remove this parameter is to use the full spectrum of sections, i.e., having a section made at each branching point in the tree. the difficulty with this full spectrum approach is that the number of sections is large, and many of the neighboring sections are very similar to one another, and therefore not adding much useful information to the phylogenetic vectors; rather it may inflate the dimension of the resulting super-phylogenetic vectors up to or higher, which is beyond the capacity of the classifier used in the study. instead, a value of is used as the number of snapshots taken in the experiments, which yields a dimension of for super-phylogenetic vector pairs versus the for the original phylogenetic vector pairs. one refinement made while generating the super-phylogenetic vector is to first adjust the distances, as defined in neighbor-joining algorithm to remove the molecular clock constraint assumed by the upgma: d = d -     and ri = ∑k d/     where |l| is the dimension of the matrix d. another refinement is to use the same projection procedure introduced in sato et al's modified mirror tree method eq, only now that |vi> and |u16s> are substituted with the super-phylogenetic vectors. it should be noted that since the background subtraction in tol-mirrortree method and sato et al's method also utilizes the phylogenetic tree, combining the treesec procedure and background subtraction may introduce some redundancy. the use of the species tree instead of individual protein trees for hierarchical clustering has a twofold effect. one effect is more theoretical; it is to reveal how individual protein trees would differ from the underlying species tree of the host genomes, in the same spirit of subtracting the common background as in. the other effect is more pragmatic; it ensures that the super-phylogenetic vectors thus obtained have the same dimension for all proteins, and therefore can be readily used as input to the support vector machine. svm the classifier used here is a support vector machine. as a powerful statistical learning method, support vector machines, originally proposed by vapnik, have recently been applied with remarkable success in bioinformatics problems, including remote protein homology detection, microarray gene expression analysis, and protein secondary structure prediction. there are a couple of reasons to use svms. first, the data are already in the vector form, particularly suitable as inputs for svms. second, svms have been used to predict protein-protein interaction in previous works, though there the different properties of proteins are used. we plan to have a comprehensive study of using svm on data from different sources, and more importantly, how to combine them for better prediction. third, svms have some inherent advantages over other classifiers, including: quadratic programming to avoid local minima, geometric intuition, lower vapnik-chervonenkis dimension leading to better generalization, and amicability with small training samples, which all contribute to its popularity as a classifier adopted in many applications. the basic idea of svms is simple; it is to find a hyperplane that separates two classes of objects, as represented as points in a vector space, with the maximum margin to the boundary lines. such a hyperplane ensures good generalization and unseen data are then classified according to their location with respect to the hyperplane. the power of svms comes partly from the data representation, where an entity, e.g., a pair of proteins, is represented by a set of attributes. however, how those attributes contribute to distinguishing a true positive from a true negative may be quite complex. in other words, the boundary line between the two classes, if depicted in a vector space, can be highly nonlinear. the svms method will find a nonlinear mapping that transform the data from the original space, called input space, into a higher dimensional space, called feature space, where the data can be linearly separable. in general, the mapping can be quite complex and the dimension can be very high in order for the mapped data to be linearly separable. the trick of svms is the use of kernel functions, which define how the dot product between two points in the feature space, which is the only quantity needed to solve the quadratic programming problem for finding the maximum margin hyperplane in the feature space. the use of kernel functions avoids explicit mapping to high dimensional feature space; high dimensionality often poses difficult problems for learning such as over-fitting, thus termed the curse of dimensionality. polynomial kernel and gaussian kernel are the two most commonly used generic kernels – linear kernel is not really useful in most cases except when the data are linearly separable. for vectors x and y, gaussian rbf is defined as k = exp,     and the polynomial kernel is defined as k = d,     where c, s and d are parameters adjustable in the software package svmlight. both kernels are experimented with the default values for c, s and d, and the gaussian kernel yielded the best results reported in this paper. because the polynomial kernel performs significantly worse with the default setting, we also tested with changing the polynomial degree d from the default value. we found that the performance is quite sensitive to the degree. details are given in the next section. besides using the separation of training and testing as a mechanism to alert us to overfitting, another mechanism built into svmlight for avoiding overfitting is the use of "soft" margin, i.e., to allow for misclassification for some outlier training data points, and a cap on the number of iterations to stop the optimization process during the training even if the preset error rate is not reached. and we have used svmlight's default setting for our experiments. it is worth noting that, overall our method can be viewed as a hybrid that employs in tandem both an explicit mapping, from phylogenetic vectors to super-phylogenetic vectors, and the use of a generic kernel.  we test our treesec method in a series of leave-one-out cross-validation experiments on the data set described above. to prepare an experiment, one of the interacting pairs is selected and reserved as the positive testing example, and non interacting pairs that contain one protein from the positive testing example are reserved as negative testing examples. the rest - = pairs are used as training examples, among which there are interacting pairs as positive training examples. by rotating the positive testing example among the interacting pairs, we can design such leave-one-out cross validation experiments, and the average performance is reported. for each experiment, the training examples are taken as input to train a support vector machine. the implementation of the support vector machine is adopted from the svmlight package. the two commonly used kernel functions – polynomial, and rbf – are experimented with the default parameter settings, and the gaussian rbf kernel function scored the best performance, which is reported in table with the svm trained, the testing examples are then input to it for prediction. a score with real value between - and + is assigned by the svm to each testing example. ideally, a positive score indicates a predicted positive, whereas a negative score indicates a predicted negative. this implies a perfect cutoff score at zero. in practice, the cutoff score may be set at a different value, other than zero. indeed, its actual value does not matter, as long as the predicted positives are true positive, and the predicted negative are true negative. to evaluate the performance, we use the receiver optical characteristic score, which is the normalized area under a curve that plots the number of true positives as the number of false positives when a moving cutoff score scans from + to -. the roc score is for a perfect performance, whereas a random predictor, which will uniformly mix up positives and negatives, is expected to get a roc score. some roc curves for our experiments are shown in figure the roc scores of the mirror tree method and our treesec method, with a few variations, are reported in table since the mirrortree is an unsupervised learning method, to be fair, we first use treesec in an unsupervised learning manner, and compare the two. in this case, since there is no training necessary, for each leave-one-out experiment, only the testing examples are ranked by their pearson correlation coefficients as if they were scores output from a classifier. the mirror tree method using the phylogenetic vectors prepared via sato et al's procedure receives a roc score. a slightly higher roc score is obtained when everything is kept the same except for substituting the phylogenetic vectors with the super-phylogenetic vectors prepared via treesec method. the advantage of treesec method becomes more obvious when used in supervised learning. in this case, treesec and mirrortree are compared for their capability of representing proteins in a way which is more conducive for classification. once proteins are represented as super-phylogenetic vectors via treesec or as phylogenetic vectors via mirrortree, they are fed into the same classifier, in this case, a svm. as we see in table while the performance of the phylogenetic vectors also improves, the super-phylogenetic vectors prepared by treesec obtain a significantly better roc score. because of the significantly worse performance for polynomial kernel with a default degree d = we tested with changing the degree to different values and found that the performance is significantly better for even values than odd values of d. this phenomenon may be an indication of the parity of the hyperplane in the feature space: symmetric with respect to changing the sign of the coordinates. overall in table better performance has been noted for "treesec × 10" when the "snapshots" are taken at a more spacious interval by multiplying the tree height with a factor of because the distances obtained from the phylip software are typically small fraction numbers, dividing the distances at the "cutting" points tend to yield rounding errors, and a re-scaling of the distances in the tree to bigger values proved to be helpful with avoiding such a problem. in table the effect of the re-scaling factor of the learning performance is given, showing that gaussian kernel is more affected by the rescaling than is the polynomial kernel. the dimension of the super-phylogenetic vectors from treesec is obviously higher than that of the phylogenetic vectors in mirrortree, since the former is derived by concatenating extra bits of information to the latter. although this may raise concerns with a judicious reader about the fairness for comparing the two approaches if they have different sizes of data, it should not be a problem in our case, because we use the same amount of input data as the sato et al's approach – the same distance matrices with the same size for proteins and the same distance matrix for species. the extra bits of information are not really extra; they are the result of how we unravel the information embedded in the input data. in a sense, our method is a hybrid of combining the explicit mapping and the use of kernels, which may explain why our method bodes well with the learning task. nonetheless, care should be taken to not let the increase of dimension go unchecked, as redundancy may arise and lead to overfitting and bad generalization. that is part of the reason that only "snapshots" of evolutionary history are incorporated. it is not surprising that the neighbor-joining distance adjustment is essential; without it as shown in table the performance decreases significantly. to verify that the better performance indeed arises from incorporating the intra-matrix correlations, we run the same experiments on the data prepared using a random species tree, we can see in table that the roc scores are consistently low at around for cases when a random tree is used. to further examine the performance, in figure roc curves are shown for those roc scores reported in table for the unsupervised learning based on pearson correlation coefficient and for the supervised learning with a gaussian kernel svm. given the y-axis as the true positives and x-axis as the false positives, the higher a curve means more true positives are identified at cost of a given number of false positives. it is consistent to note that "treesec × 10" corresponds to the top curve overall. also remarkable is the steep slope for the two roc curves corresponding to the unsupervised learning at small false positive rates. this explains the high specificity for these unsupervised learning based on correlation coefficient, and is consistent with what is reported in. as moving to the right, these two curves quickly lose the upward momentum, an indication of low sensitivity. therefore, the supervised learning using the svms in these experiments offers a better balance between sensitivity and specificity. it is worth noting that, the highly skewed learning problem is likely a reflection of situations in the real world, i.e., there are far more negatives than positives. in our case, given n proteins that uniquely interact with only one other member, there are only n/ positive pairings among the / possible pairings of these n proteins. that is, the interacting network, with nodes representing the proteins and edges representing the interactions, is quite sparse, but our method is still applicable when there are more edges. because every possible pair of nodes is assigned a score in our method, predictions can be made by going down a list of all pairs that are ranked by their scores in decreasing order. so, regardless the number of the actual edges in the network, the method works, and perfectly so as long as the true interacting pairs are ranked higher than non interacting pairs in the prediction. indeed, this scheme is also widely used in predicting protein interaction networks in general, both in an unsupervised paradigm such as the original mirror tree method, and in a supervised learning paradigm.  to summarize, in this work we developed a novel, simple method to explore the intra-matrix correlational information embedded in the distance matrices and incorporate such information into a data representation which is conducive to supervised learning. three methods recognize the importance of the phylogenetic tree, both sato et al's projection method and pazos et al's tol-mirrortree try to "subtract" from the similarity the effect due to speciation rather than the interaction pressures, whereas our method seeks to "unravel" the intrinsic structure of the distance matrices using the species tree as a guide and then "concatenate" these snapshots of the evolutionary history to the current view of the proteins. that is, the main difference between subtracting and adding is that the former is more appropriate for removing background noise so as to reduce false positive and the latter is more appropriate for disentangling intra-matrix correlations so as to aid a supervised learner. as future work, we will study how the reconciliation between protein trees and species tree can be more explicitly represented and how to associate selection pressure imposed by the interaction to specific evolutionary events, e.g., horizontal gene transfers. competing interests the author declare that they have no competing interests. authors' contributions ll conceived the ideas and prototyped some of the implementation, and rac collected the data and implemented the methods. both authors participated in writing the manuscript. 
we have shown that the phylogenetic tree can be used as a guide to extract intra-matrix correlations in the distance matrices of orthologous proteins, where these correlations are represented as intermediate distance matrices of the ancestral orthologous proteins. we proposed a novel, simple method to account for some of the intra-matrix correlations in improving the prediction accuracy. the performance, measured as roc score in cross validation experiments, shows significant improvement of our method over that of using pearson correlations. a support vector machine is trained and tested on pairs of proteins, represented as super phylogenetic vectors, whose interactions are known. specifically, the phylogenetic species tree of the reference genomes is used as a guide tree for hierarchical clustering of the orthologous proteins. protein-protein interactions are critical for cellular functions. recently developed computational approaches for predicting protein-protein interactions utilize co-evolutionary information of the interacting partners, e.g., correlations between distance matrices, where each matrix stores the pairwise distances between a protein and its orthologs from a group of reference genomes. both the unsupervised and supervised learning paradigms benefit from the explicit inclusion of these intermediate distance matrices, and particularly so in the latter case, which offers a better balance between sensitivity and specificity in the prediction of protein-protein interactions. the distances between these clusters, derived from the original pairwise distance matrix using the neighbor joining algorithm, form intermediate distance matrices, which are then transformed and concatenated into a super phylogenetic vector.
 protein-protein interactions are critical for cellular functions. recently developed computational approaches for predicting protein-protein interactions utilize co-evolutionary information of the interacting partners, e.g., correlations between distance matrices, where each matrix stores the pairwise distances between a protein and its orthologs from a group of reference genomes.  we proposed a novel, simple method to account for some of the intra-matrix correlations in improving the prediction accuracy. specifically, the phylogenetic species tree of the reference genomes is used as a guide tree for hierarchical clustering of the orthologous proteins. the distances between these clusters, derived from the original pairwise distance matrix using the neighbor joining algorithm, form intermediate distance matrices, which are then transformed and concatenated into a super phylogenetic vector. a support vector machine is trained and tested on pairs of proteins, represented as super phylogenetic vectors, whose interactions are known. the performance, measured as roc score in cross validation experiments, shows significant improvement of our method over that of using pearson correlations.  we have shown that the phylogenetic tree can be used as a guide to extract intra-matrix correlations in the distance matrices of orthologous proteins, where these correlations are represented as intermediate distance matrices of the ancestral orthologous proteins. both the unsupervised and supervised learning paradigms benefit from the explicit inclusion of these intermediate distance matrices, and particularly so in the latter case, which offers a better balance between sensitivity and specificity in the prediction of protein-protein interactions. 