BACKGROUND
understanding historical relationships between genes, proteins and species is a core aspect of evolutionary biology, with the phylogenetic tree playing a fundamental role in analysis and visualization.
however, major challenges still exist in the representation and analysis of the information encoded within phylogenetic trees.
for instance, inferring the "true" tree is fundamentally a difficult problem, leading to continuous refinement of reconstruction methods  <cit> .
similarly, methodologies for tree comparison are also undergoing significant development  <cit> .
in this instance, the typical goal is to compare trees in order to determine their degree of similarity, providing one mechanism to test a variety of hypotheses regarding evolutionary associations.
for example, comparison of gene trees with organismal trees allows the detection of non-standard events such as horizontal gene transfer  <cit> .
comparison of species trees can be used to give a picture of host-parasite symbiosis as is seen, for example, in the case of attine ants, their fungal cultivars, and the escovopsis parasite  <cit> .
another example is the prediction of protein-protein interactions, as it has been shown that interacting proteins often appear to coevolve with one another  <cit> .
such instances of coevolution are largely based on the premise that in order to maintain their interaction , changes in one gene/protein will be coordinated with changes in the other, and this process of coevolution or correlated evolution can be observed through the similarity of their phylogenetic trees  <cit> .
while there are a variety of methods available for the comparison of trees, two general categories of approaches are clearly distinguishable.
the first class of approaches focuses on comparing trees through topological features, for example quantifying the number of shared/non-shared substructures  between a pair of trees  <cit>  or finding the minimum number of operations  to transform one tree into another  <cit> .
the second class of approaches compares the distance or path length information directly.
specifically, in these approaches assessing the similarity between two trees is reduced to a problem of finding the degree of correlation  between the elements within the respective distance matrices.
the "mirrortree" method is based on such an approach and was developed for the prediction of protein-protein interactions  <cit> .
continued work in this area has led to multiple modifications of the basic mirrortree approach including the use of patristic distances obtained from the corresponding neighbor-joining tree instead of the observed inter-protein distances  <cit> , the correction of patristic distance matrices for their inherent similarity due to background "tree of life" evolution  <cit> , and the incorporation of ancestor node information into the distance matrices  <cit> .
while methods based on distance matrix similarities have proven to be of particular value, several substantial disadvantages exist.
for instance, these methods assume that each value in a distance matrix is independent of the other distance values.
this is generally not the case as, if a distance  between two leaf nodes changes, lengths of all other paths involving the modified edge also change.
therefore, any method in which the distance matrices are directly manipulated without considering this dependency may bias the reported correlations.
it is also difficult to extend these existing approaches, for example, to incorporate robust estimation into the identification of outlying lineages between compared trees.
furthermore, by definition, it is not possible to handle trees of different size or to align multiple trees simultaneously.
finally, prior knowledge cannot be readily incorporated so as to help guide comparisons.
here, we report a novel method for the comparison of evolutionary distance matrices  based on the superimposition of euclidean embeddings that best realize the given distance relationships.
specifically, we start from a set of aligned sequences and generate distance matrices based on either distance information calculated directly from the alignment, or distances derived from a corresponding neighbor joining tree.
from these distance matrices we then map each sequence to a euclidean space via metric multidimensional scaling .
this operation produces a multidimensional structure or point pattern, where each point represents a taxon, and the distance relationships between all points is maintained from the original distance matrix.
for the purpose of comparing two trees, the same operation is applied to the second distance matrix, generating the second euclidean embedding.
finally, we superimpose one embedded point pattern onto the other with the degree of fit being determined by the least squares sum of deviations between corresponding point pairs or by some other measure as described below.
in this paper, we refer to the general comparative approach of euclidean embedding creation and alignment as "xceed", the comparison of embedded evolutionary distances.
however, this general approach actually contains three different superimposition methods, differing with regard to the question being asked or the data available .
briefly, the first approach is an indirect superimposition of target structures  that is guided by a low-noise reference structure, 16s ribosomal rna phylogenies.
while similar to the tol-mirrortree and vector-projection methods  <cit> , this approach, rceed, provides a new way to remove background correlation caused by tree-of-life evolution and thus helps in providing an accurate measure of coevolution .
like the tol-mirrortree and vector-projection methods, rceed requires both a reference structure as well as correspondence information for proper alignment .
we describe the application of rceed to the prediction of coevolving protein interactions and demonstrate its improved performance over the mirrortree, tol-mirrortree  <cit> , phylogenetic vector projection  <cit> , and partial correlation methods  <cit> .
in cases where the identification of incongruent region between trees is desired, robust structure alignment  can be performed using "verboonian" procrustes  <cit> , which penalizes less for the existence of outliers when compared to rceed.
as a result, one can detect local regions of similarity even in the presence of outliers and/or identify outliers relative to a common shared structure.
the identification of horizontal gene transfer  events is an area where outlier detection within a phylogenetic tree is needed and we provide an example of the applicability of vceed to this problem.
as with rceed, we can also use vceed to detect coevolving protein interactions, especially in cases where a reference structure is not available and/or target structures  contain outlying taxa and show its in this.
we also compare the performance of vceed with that of rceed and other existing methods.
finally, alignment without either a reference structure or mapping information can be performed with a gaussian mixture model superimposition approach .
as a proof-of-concept for the potential broader utility of this approach, we describe its application to the prediction of protein interaction specificity between multigene families.
as a whole, the xceed methodology provides a novel approach to the tree comparison problem and the study of related evolutionary processes.
RESULTS
prediction of protein interactions
we first applied both rceed and vceed to the prediction of protein interactions through the detection of a coevolutionary signal between orthologous protein families.
while analogous to the approaches of  <cit> , rceed attempts to address some of their weaknesses.
specifically, in the tol-mirrortree approach, pazos and colleagues subtracted the distance matrix of 16s rrna from that of each protein, and then measured the correlation between these "difference of distance" matrices  <cit> .
however, direct subtraction of rrna from protein distances is problematic, as their evolutionary rates are different and it is not clear as to how to properly scale such differencing procedures.
in phylogenetic vector projection, sato and colleagues formed a vector from the lower triangular region of each distance matrix  <cit>  and computed a difference vector between a gene vector and the same gene vector projected onto that of 16s rrna.
again the correlation between distance matrices is measured with these difference  vectors.
while avoiding direct subtraction of amino acid and rrna distances, this approach  still assumes that all pairwise distances are independent.
not accounting for non-independence between distances can potentially cause bias in evaluation of correlation between two distance matrices  <cit> .
the rceed approach addresses these issues by viewing the leaf nodes in an embedded structure as independent variables.
to measure the degree of coevolution, we estimate how similar the deviations from the reference structure are for each embedded structure.
doing this makes it possible to remove the background tree-of-life correlation without direct subtraction of rrna distances from amino acid distances or assuming independence between distances.
specifically, we fit the reference structure onto the first embedded structure and then onto the second structure separately .
afterwords, we superimpose these two reference structures onto each other while carrying along their associated structures, which are the actual targets of interest.
after this superimposition we can remove the reference structures, and then measure the degree of similarity between the remaining two target structures.
as a single outlier can make the estimation of correlation coefficients unreliable  <cit>  we also evaluated the use of vceed in this application as it is specifically tailored for dealing with outliers .
we compared the predictions of rceed and vceed to those of the mirrortree, tol-mirrortree, phylogenetic vector projection, and partial correlation methods using the data of pazos and colleagues  <cit> .
this data consisted of  <dig> protein interactions  out of a total of  <dig>  possible between  <dig> e. coli proteins.
results are shown in table  <dig> where we benchmarked the performance of all methods by computing the area under receiver operating characteristic curve  and estimated the significance by using the method of delong et al.
<cit> .
we also provide the area under precision-recall curve, with the full precision-recall curves provided in additional file  <dig>  as shown in table  <dig>  the auc for the precision-recall curve was the greatest for vceed with a value of  <dig> , followed by rceed using either patristic  or observed  distances.
the worst performer was the mirrortree method with an pr-auc of  <dig> .
similar trends are observed when using the roc score with rceed having a score of  <dig> , with that of mirrortree and tol-mirrortree being  <dig>  and  <dig>  respectively.
the phylogenetic vector projection and partial correlation approach had roc scores of  <dig>  and  <dig>  respectively.
in all cases, the difference in auc between rceed and other methods was statistically significant .
we also found that the auc of vceed was  <dig>  - nearly that of rceed using patristic distances.
1area under precision-recall curve
2area under receiver operating characteristic curve
3the significance was computed using rceed  as reference according to  <cit> .
4based on observed distances
5based on patristic distances after the reconstruction of neighbor joining trees
6august  <dig> version of dip.
detection of horizontal gene transfer
with the basic xceed approach, we are able to estimate how well two trees match in a global sense through a least squares model.
specifically, if there exists an incongruent region between two trees, the least squares approach will tend to smooth away large local errors by allowing greater errors in other, otherwise well-aligning regions.
however, in some cases we would prefer to maintain the best alignment of a substructure and/or be able to identify outliers that are not consistent with a comparison structure.
to address this need, we adapted a robust procrustes method previously proposed by verboon and heiser  <cit> , with the difference between this and globally optimal superimposition diagrammed in figure  <dig>
in figure  <dig> it can be seen that errors are distributed across all pairs, as would be done using the basic xceed method using least squares .
however, in this example there is a substructure that is in fact identical between the two that is lost as a result of the spreading of errors throughout the alignment.
in contrast, figure  <dig> shows the case where we have used verboonian robust procrustes  for the alignment.
in this case we have found and aligned the identical substructures; allowing identification of both this region of high-similarity as well as the outliers which deviate significantly between the two distance matrices.
this ability to detect local similarity and/or outliers is of particular utility in the identification of horizontal gene transfer  events.
in hgt, a gene or group of genes is transferred laterally from another species, rather than inherited vertically from the parent.
there are a variety of approaches to predict the occurrence of hgt based on, for example, codon usage, patterns of sequence homology, and patterns of gene distribution  <cit> .
however, the most robust method for detecting hgt is through the comparison of phylogenetic trees of different genes.
when a species accepts a gene laterally from another species, the location of the recipient species in the phylogenetic tree will be unusually close to the location of the donor species, which can be detected through manual analysis of the tree.
using vceed, we can detect possible hgt by comparing a tree that potentially harbors one or more hgt events with a reference tree that does not, and then identifying the associated outliers as likely hgt candidates.
as a proof-of-concept, we applied vceed to the case of the ruvb  gene family described in  <cit> .
in e. coli, the ruva and ruvb proteins catalyze branch migration of holliday junctions during genetic recombination and form an operon conserved in the majority of sequenced bacterial genomes.
in contrast with the ruva family, the ruvb gene is believed to have undergone hgt  <cit> .
we compared the trees  of ruvb orthologous proteins collected from  <dig> bacterial species  to that of 16s rrna, with errors in the superimposition plotted in figure  <dig>  in this example, we expect that the lineages that underwent hgt will show up as outliers in the superimposition of the reference structure  onto that of ruvb.
as can be observed, genes with errors larger than the threshold of  <dig>  for c , see methods), in the superimposition are those from ureaplasma and mycoplasma and include m. pulmonis , u. urealyticum , m. pneumoniae , and m. genitalium  .
these four were the same species identified by omelchenko and colleagues as being related to the hgt of the ruvb gene.
in addition, vceed was also able to identify sll <dig>  a cyanobacterial gene from synechocystis which, as can be observed in the phylogentic tree of ruvb, is closer to the firmicutes rather than the proteobacteria or actinobacteria as opposed to ruva.
we also tested our approach with the more complicated case of the upps gene family  which, as also described in  <cit> , is believed to harbor multiple hgt events.
figure  <dig> shows the outlying genes according to vceed using 16s rrna as the reference and using the same threshold value of  <dig>  for c as in the previous example.
as can be observed, we found that ape <dig> from a. pernix, an archaeal gene, has the greatest divergence in the comparison to the 16s rrna tree.
we also see in the phylogenetic tree that it has atypical affinity to bacterial genes from c. jejuni  and b. burgdorferi , both of which are also identified as weak outliers with errors just above threshold.
both cj <dig> and bb <dig> would generally be expected to appear in the tree under the proper phyla, proteobacteria  and spirochaetes , respectively.
further examination of the identified outlier genes within the phylogenetic tree shows a bacterial branch  of d. radioduran , c. glutamicum , m. tuberculosis h37rv  and m. leprae , embedded within an archaeal phylum, the euryarchaeota.
we also see in the archaeal branch that a crenarchaeota gene, sso <dig>  stands out in its grouping with other genes from the euryarchaeota phylum.
the rickettsiales  identified by omelchenko and colleagues were also included in our outlier list, although they were not the most deviating.
note that being an outlier does not certify that the gene was horizontally transferred.
other mechanisms for this deviation can also occur including large differences in evolutionary rate or poor quality of the sequence alignment.
therefore, while this approach can potentially aid in the automatic prediction of potential hgt events, manual inspection of the phylogenetic tree may still be required.
for example, the firmicutes genes, l <dig> and sa <dig>  while being slight outliers, are in a monophyletic subtree of firmicutes  and can thus be excluded from further consideration.
interaction specificity between multigene families
as demonstrated earlier, we can use either rceed or vceed to compare trees so as to predict the potential interaction of a pair of protein families.
again, these approaches require the use of mapping information to link the leaves of the two trees.
there are applications, however, where one would like to compare trees that lack mapping information or where the recovery of mapping information is the primary goal.
an important example of this type is in trying to determine likely interaction specificity between a pair of protein or domain families   <cit> .
two primary methods for specificity prediction, matrix  <cit>  and morph  <cit> , currently exist, and like all methods, have their own inherent strengths and weaknesses.
with matrix, a significant weakness is that the tree structure is completely ignored throughout the specificity search.
matrix also requires multiple simulated annealing runs  to determine which pairings are most frequent.
perhaps most important, both matrix and morph assume that there is a one-to-one correspondence between members of the two protein families; i.e.
protein a from family  <dig> interacts solely with protein b from family  <dig>  thus it is not possible to generalize to the more realistic situation where we are looking at specificities between protein families of different size.
in addition it precludes the possibility of many-to-many or multiple interaction partners for a given protein.
here we adapt the use of a registration algorithm based upon gaussian mixture models with our basic embedding and alignment approach  <cit> .
in this case, we regard each vertex in the embedded structure  as the mean of a gaussian component such that the entire embedding is represented as a mixture model .
the central idea is that if we have two structures that are highly similar, as we align one structure closer to the other, their corresponding mixture models become accordingly similar.
by trying to minimize the divergence between the two mixture models, we can eventually find the best superimposition.
we refer to this method of alignment as gaussian ceed or gceed for short.
using gceed, we attempted to determine the specificity information between protein families provided in ramani et al.
<cit> .
the first example is the case of the interacting protein family of gyra and gyrb.
each protein family is known to have a single paralog, parc and pare respectively, and these paralogs are also known to interact.
figure  <dig> shows the trees and interaction specificity  between these two multigene families.
results of the initial superimposition are shown in figure 6-step <dig>  the probability matrix is shown after having converted probabilities to grayscale values such that darker elements at  denote a higher probability of correspondence between i-th protein of family  <dig> and j-th protein of family  <dig>  proteins are arranged such that correct individual binding partners lie along the diagonal.
in this first step we see that the initial alignment appears to have found the correct broader interaction specificity of gyra with gyrb  and parc with pare  as observed by the distinct segmentation of the probability matrix into two distinct regions.
for parc/pare, correct correspondence for three individual interactions was also found in the initial alignment .
both regions a and b, being indeterminate, are separately superimposed in an iterative manner with results after each superimposition shown in the submatrices of figure  <dig>
the final result after complete alignment is shown in figure  <dig>  here we can see that gceed successfully predicted the interaction specificity for  <dig> out of  <dig> individual interactions.
the other misassigned  <dig> pairs were degenerate cases and their interaction specificity could not be further defined due to a lack of structural information.
the reason for this can in part be observed within figure  <dig>  where the four proteins from each family  can be observed to be very close to each other .
in such instances it is difficult for the algorithm to find a correct high-probability mapping as multiple alignments are equally viable.
nevertheless, the interaction specificity at the protein-family level was correctly predicted.
in addition, over half of the specific interactions could be recovered solely from the alignment of these structures.
we performed the same specificity analysis using gceed to a total of  <dig> protein family pairs used in previous studies and compared results to that of matrix and morph in terms of stringent accuracy .
as can be observed, there is no significantly superior approach , as all methods show instances where they have the greatest accuracy of specificity prediction.
however, we emphasize the extra functionality of gceed that is suited to realistic situations where  the size of the protein families at hand are unlikely to be identical, and/or  there exist some a priori knowledge of validated interacting protein interactions.
as a demonstration of this functionality within gceed, we again used the case of gyra and gyrb interactions.
we first made the gyra tree progressively smaller by sampling from nineteen down to ten sequences from the total of twenty gyra orthologs, with  <dig> different combinations for each size.
we then performed specificity prediction by aligning each sampled gyra tree with the complete 20-node gyrb tree.
to evaluate our performance, we introduce the vicinity hit rate as a means to estimate how close each node's true interacting partner is in relation to others within the aligned structures.
specifically, we define the vicinity hit rate as the ratio of nodes that have their true interacting parter within top three highest predicted probability partners.
thus the vicinity hit rate allows for situations where the true interacting partner is very close  to the predicted interaction partner as determined through the alignment.
results of this analysis is shown in figure  <dig>  again, each histogram along the x-axis was generated from  <dig> samples of the gyra tree of corresponding size and the dark line shows how the average hit rate changes as the size of this tree decreases.
in this instance, the ability for gceed to determine binding specificities with a vicinity hit rate of approximately 65%  is relatively well maintained out to approximately  <dig> leaves or a 25% difference in tree sizes.
as the difference between tree sizes decreases, we also begin to observe greater numbers of very poor predictions along with lesser numbers of very good predictions.
these arise in situations where the the smaller tree fits very well, but in the wrong position within the larger tree, resulting in a very poor vicinity hit rate ).
the situation is analogous, but far less common for the high vicinity rate predictions .
we would expect that additional information in the form of prior knowledge of an existing protein interaction pair would help to improve predictive performance.
such knowledge can be readily introduced into the gceed alignment scheme and results of knowing just a single pair a priori are shown in figure  <dig>  here we picked a random, but correct pair of interacting proteins between the two trees to serve as the a priori known information.
as these proteins interact, we assume that they must be near each other in the final superimposition.
we thus impose a constraint in the optimization of equation , where the two proteins are kept within a pre-specified distance range .
results show that use of prior knowledge provides a significant improvement in the stability of the vicinity hit rate, with a mean hit rate of approximately 60% even when reducing tree size to nearly half of its original value.
in addition, using the structural information provided by the known interaction pair, we were able to avoid degenerate cases ).
in the comparisons between trees with greatest difference in size, the average vicinity hit rate of ten-node sample trees was  <dig> % without prior knowledge versus  <dig> % when using a single known protein pair.
together, these results suggest the potential for using gceed in realistic situations where differences in tree sizes exist and/or prior information is available.
CONCLUSIONS
in this work, we have described a novel approach for the comparison of phylogenetic trees, represented as embedded structures, and shown several examples of its application.
first, when applied to the prediction of protein interactions, we see an improvement in prediction accuracy using the rceed/vceed approach when compared to other available approaches.
we note, that high similarity between two embedded structures does not require that there is a physical interaction between members, but is only suggestive of the possibility.
similarly, the physical interaction between two proteins does not necessitate coevolution.
thus coevolutionary approaches such as those presented here can only identify a portion of the complete interactome within a given species.
for the enhanced prediction of protein interactions, approaches such as rceed/vceed may show their greatest efficacy when combined with other computational approaches .
with vceed, we were also able to perform a local alignment between structures, providing the opportunity to detect outliers that often indicate unusual evolutionary events including the horizontal gene transfer described here.
while phylogenetic methods which detect incongruity between trees are generally considered the gold-standard for hgt detection, these methods are not readily automatable and require extensive manual analysis.
our results suggests that vceed has significant potential in aiding such identifications.
by using the information inherent in the representation of a tree as an embedded structure, we were able to demonstrate the ability to align and measure the similarity between trees even when correspondence information is not available or when their sizes are different.
while a basic example, the need to establish interaction specificity between interacting protein families supports the development of new approaches, and in this regard, gceed shows significant promise.
while the embedding and superimposition of taxa within a euclidean space in no way supersedes the use of a phylogenetic tree, it does provide several useful capabilities.
for instance, embedding generates a deterministic structure that bypasses ambiguities associated in direct tree comparisons by transforming a specific distance matrix into a single specific shape enabling consistent comparison between trees.
similarly, use of a representative embedding also makes it possible to take into account the entire point-pattern structure all at once when determining correlation, rather than examining pair-by-pair correlation as in the mirrortree or related approaches.
finally, the representation of trees as embedded structures provides the capability to compare trees of different size, which is a built-in limitation of correlation-based methods.
in this case, it becomes a matter of comparing two structures using procedures based on registration approaches such as the gceed approach proposed in this work.
as a whole, the xceed approach provides an additional set of tools for the study of phylogenetic trees and associated evolutionary processes.

 understanding historical relationships between genes, proteins and species is a core aspect of evolutionary biology, with the phylogenetic tree playing a fundamental role in analysis and visualization. however, major challenges still exist in the representation and analysis of the information encoded within phylogenetic trees. for instance, inferring the "true" tree is fundamentally a difficult problem, leading to continuous refinement of reconstruction methods. similarly, methodologies for tree comparison are also undergoing significant development. in this instance, the typical goal is to compare trees in order to determine their degree of similarity, providing one mechanism to test a variety of hypotheses regarding evolutionary associations. for example, comparison of gene trees with organismal trees allows the detection of non-standard events such as horizontal gene transfer. comparison of species trees can be used to give a picture of host-parasite symbiosis as is seen, for example, in the case of attine ants, their fungal cultivars, and the escovopsis parasite. another example is the prediction of protein-protein interactions, as it has been shown that interacting proteins often appear to coevolve with one another. such instances of coevolution are largely based on the premise that in order to maintain their interaction, changes in one gene/protein will be coordinated with changes in the other, and this process of coevolution or correlated evolution can be observed through the similarity of their phylogenetic trees. while there are a variety of methods available for the comparison of trees, two general categories of approaches are clearly distinguishable. the first class of approaches focuses on comparing trees through topological features, for example quantifying the number of shared/non-shared substructures between a pair of trees or finding the minimum number of operations to transform one tree into another. the second class of approaches compares the distance or path length information directly. specifically, in these approaches assessing the similarity between two trees is reduced to a problem of finding the degree of correlation between the elements within the respective distance matrices. the "mirrortree" method is based on such an approach and was developed for the prediction of protein-protein interactions. continued work in this area has led to multiple modifications of the basic mirrortree approach including the use of patristic distances obtained from the corresponding neighbor-joining tree instead of the observed inter-protein distances, the correction of patristic distance matrices for their inherent similarity due to background "tree of life" evolution, and the incorporation of ancestor node information into the distance matrices. while methods based on distance matrix similarities have proven to be of particular value, several substantial disadvantages exist. for instance, these methods assume that each value in a distance matrix is independent of the other distance values. this is generally not the case as, if a distance between two leaf nodes changes, lengths of all other paths involving the modified edge also change. therefore, any method in which the distance matrices are directly manipulated without considering this dependency may bias the reported correlations. it is also difficult to extend these existing approaches, for example, to incorporate robust estimation into the identification of outlying lineages between compared trees. furthermore, by definition, it is not possible to handle trees of different size or to align multiple trees simultaneously. finally, prior knowledge cannot be readily incorporated so as to help guide comparisons. here, we report a novel method for the comparison of evolutionary distance matrices based on the superimposition of euclidean embeddings that best realize the given distance relationships. specifically, we start from a set of aligned sequences and generate distance matrices based on either distance information calculated directly from the alignment, or distances derived from a corresponding neighbor joining tree. from these distance matrices we then map each sequence to a euclidean space via metric multidimensional scaling. this operation produces a multidimensional structure or point pattern, where each point represents a taxon, and the distance relationships between all points is maintained from the original distance matrix. for the purpose of comparing two trees, the same operation is applied to the second distance matrix, generating the second euclidean embedding. finally, we superimpose one embedded point pattern onto the other with the degree of fit being determined by the least squares sum of deviations between corresponding point pairs or by some other measure as described below. in this paper, we refer to the general comparative approach of euclidean embedding creation and alignment as "xceed", the comparison of embedded evolutionary distances. however, this general approach actually contains three different superimposition methods, differing with regard to the question being asked or the data available. briefly, the first approach is an indirect superimposition of target structures that is guided by a low-noise reference structure, 16s ribosomal rna phylogenies. while similar to the tol-mirrortree and vector-projection methods, this approach, rceed, provides a new way to remove background correlation caused by tree-of-life evolution and thus helps in providing an accurate measure of coevolution. like the tol-mirrortree and vector-projection methods, rceed requires both a reference structure as well as correspondence information for proper alignment. we describe the application of rceed to the prediction of coevolving protein interactions and demonstrate its improved performance over the mirrortree, tol-mirrortree, phylogenetic vector projection, and partial correlation methods. in cases where the identification of incongruent region between trees is desired, robust structure alignment can be performed using "verboonian" procrustes, which penalizes less for the existence of outliers when compared to rceed. as a result, one can detect local regions of similarity even in the presence of outliers and/or identify outliers relative to a common shared structure. the identification of horizontal gene transfer events is an area where outlier detection within a phylogenetic tree is needed and we provide an example of the applicability of vceed to this problem. as with rceed, we can also use vceed to detect coevolving protein interactions, especially in cases where a reference structure is not available and/or target structures contain outlying taxa and show its in this. we also compare the performance of vceed with that of rceed and other existing methods. finally, alignment without either a reference structure or mapping information can be performed with a gaussian mixture model superimposition approach. as a proof-of-concept for the potential broader utility of this approach, we describe its application to the prediction of protein interaction specificity between multigene families. as a whole, the xceed methodology provides a novel approach to the tree comparison problem and the study of related evolutionary processes.  prediction of protein interactions we first applied both rceed and vceed to the prediction of protein interactions through the detection of a coevolutionary signal between orthologous protein families. while analogous to the approaches of, rceed attempts to address some of their weaknesses. specifically, in the tol-mirrortree approach, pazos and colleagues subtracted the distance matrix of 16s rrna from that of each protein, and then measured the correlation between these "difference of distance" matrices. however, direct subtraction of rrna from protein distances is problematic, as their evolutionary rates are different and it is not clear as to how to properly scale such differencing procedures. in phylogenetic vector projection, sato and colleagues formed a vector from the lower triangular region of each distance matrix and computed a difference vector between a gene vector and the same gene vector projected onto that of 16s rrna. again the correlation between distance matrices is measured with these difference vectors. while avoiding direct subtraction of amino acid and rrna distances, this approach still assumes that all pairwise distances are independent. not accounting for non-independence between distances can potentially cause bias in evaluation of correlation between two distance matrices. the rceed approach addresses these issues by viewing the leaf nodes in an embedded structure as independent variables. to measure the degree of coevolution, we estimate how similar the deviations from the reference structure are for each embedded structure. doing this makes it possible to remove the background tree-of-life correlation without direct subtraction of rrna distances from amino acid distances or assuming independence between distances. specifically, we fit the reference structure onto the first embedded structure and then onto the second structure separately. afterwords, we superimpose these two reference structures onto each other while carrying along their associated structures, which are the actual targets of interest. after this superimposition we can remove the reference structures, and then measure the degree of similarity between the remaining two target structures. as a single outlier can make the estimation of correlation coefficients unreliable we also evaluated the use of vceed in this application as it is specifically tailored for dealing with outliers. we compared the predictions of rceed and vceed to those of the mirrortree, tol-mirrortree, phylogenetic vector projection, and partial correlation methods using the data of pazos and colleagues. this data consisted of protein interactions out of a total of possible between e. coli proteins. results are shown in table where we benchmarked the performance of all methods by computing the area under receiver operating characteristic curve and estimated the significance by using the method of delong et al.. we also provide the area under precision-recall curve, with the full precision-recall curves provided in additional file as shown in table the auc for the precision-recall curve was the greatest for vceed with a value of, followed by rceed using either patristic or observed distances. the worst performer was the mirrortree method with an pr-auc of. similar trends are observed when using the roc score with rceed having a score of, with that of mirrortree and tol-mirrortree being and respectively. the phylogenetic vector projection and partial correlation approach had roc scores of and respectively. in all cases, the difference in auc between rceed and other methods was statistically significant. we also found that the auc of vceed was - nearly that of rceed using patristic distances. 1area under precision-recall curve 2area under receiver operating characteristic curve 3the significance was computed using rceed as reference according to. 4based on observed distances 5based on patristic distances after the reconstruction of neighbor joining trees 6august version of dip. detection of horizontal gene transfer with the basic xceed approach, we are able to estimate how well two trees match in a global sense through a least squares model. specifically, if there exists an incongruent region between two trees, the least squares approach will tend to smooth away large local errors by allowing greater errors in other, otherwise well-aligning regions. however, in some cases we would prefer to maintain the best alignment of a substructure and/or be able to identify outliers that are not consistent with a comparison structure. to address this need, we adapted a robust procrustes method previously proposed by verboon and heiser, with the difference between this and globally optimal superimposition diagrammed in figure in figure it can be seen that errors are distributed across all pairs, as would be done using the basic xceed method using least squares. however, in this example there is a substructure that is in fact identical between the two that is lost as a result of the spreading of errors throughout the alignment. in contrast, figure shows the case where we have used verboonian robust procrustes for the alignment. in this case we have found and aligned the identical substructures; allowing identification of both this region of high-similarity as well as the outliers which deviate significantly between the two distance matrices. this ability to detect local similarity and/or outliers is of particular utility in the identification of horizontal gene transfer events. in hgt, a gene or group of genes is transferred laterally from another species, rather than inherited vertically from the parent. there are a variety of approaches to predict the occurrence of hgt based on, for example, codon usage, patterns of sequence homology, and patterns of gene distribution. however, the most robust method for detecting hgt is through the comparison of phylogenetic trees of different genes. when a species accepts a gene laterally from another species, the location of the recipient species in the phylogenetic tree will be unusually close to the location of the donor species, which can be detected through manual analysis of the tree. using vceed, we can detect possible hgt by comparing a tree that potentially harbors one or more hgt events with a reference tree that does not, and then identifying the associated outliers as likely hgt candidates. as a proof-of-concept, we applied vceed to the case of the ruvb gene family described in. in e. coli, the ruva and ruvb proteins catalyze branch migration of holliday junctions during genetic recombination and form an operon conserved in the majority of sequenced bacterial genomes. in contrast with the ruva family, the ruvb gene is believed to have undergone hgt. we compared the trees of ruvb orthologous proteins collected from bacterial species to that of 16s rrna, with errors in the superimposition plotted in figure in this example, we expect that the lineages that underwent hgt will show up as outliers in the superimposition of the reference structure onto that of ruvb. as can be observed, genes with errors larger than the threshold of for c, see methods), in the superimposition are those from ureaplasma and mycoplasma and include m. pulmonis, u. urealyticum, m. pneumoniae, and m. genitalium. these four were the same species identified by omelchenko and colleagues as being related to the hgt of the ruvb gene. in addition, vceed was also able to identify sll a cyanobacterial gene from synechocystis which, as can be observed in the phylogentic tree of ruvb, is closer to the firmicutes rather than the proteobacteria or actinobacteria as opposed to ruva. we also tested our approach with the more complicated case of the upps gene family which, as also described in, is believed to harbor multiple hgt events. figure shows the outlying genes according to vceed using 16s rrna as the reference and using the same threshold value of for c as in the previous example. as can be observed, we found that ape from a. pernix, an archaeal gene, has the greatest divergence in the comparison to the 16s rrna tree. we also see in the phylogenetic tree that it has atypical affinity to bacterial genes from c. jejuni and b. burgdorferi, both of which are also identified as weak outliers with errors just above threshold. both cj and bb would generally be expected to appear in the tree under the proper phyla, proteobacteria and spirochaetes, respectively. further examination of the identified outlier genes within the phylogenetic tree shows a bacterial branch of d. radioduran, c. glutamicum, m. tuberculosis h37rv and m. leprae, embedded within an archaeal phylum, the euryarchaeota. we also see in the archaeal branch that a crenarchaeota gene, sso stands out in its grouping with other genes from the euryarchaeota phylum. the rickettsiales identified by omelchenko and colleagues were also included in our outlier list, although they were not the most deviating. note that being an outlier does not certify that the gene was horizontally transferred. other mechanisms for this deviation can also occur including large differences in evolutionary rate or poor quality of the sequence alignment. therefore, while this approach can potentially aid in the automatic prediction of potential hgt events, manual inspection of the phylogenetic tree may still be required. for example, the firmicutes genes, l and sa while being slight outliers, are in a monophyletic subtree of firmicutes and can thus be excluded from further consideration. interaction specificity between multigene families as demonstrated earlier, we can use either rceed or vceed to compare trees so as to predict the potential interaction of a pair of protein families. again, these approaches require the use of mapping information to link the leaves of the two trees. there are applications, however, where one would like to compare trees that lack mapping information or where the recovery of mapping information is the primary goal. an important example of this type is in trying to determine likely interaction specificity between a pair of protein or domain families. two primary methods for specificity prediction, matrix and morph, currently exist, and like all methods, have their own inherent strengths and weaknesses. with matrix, a significant weakness is that the tree structure is completely ignored throughout the specificity search. matrix also requires multiple simulated annealing runs to determine which pairings are most frequent. perhaps most important, both matrix and morph assume that there is a one-to-one correspondence between members of the two protein families; i.e. protein a from family interacts solely with protein b from family thus it is not possible to generalize to the more realistic situation where we are looking at specificities between protein families of different size. in addition it precludes the possibility of many-to-many or multiple interaction partners for a given protein. here we adapt the use of a registration algorithm based upon gaussian mixture models with our basic embedding and alignment approach. in this case, we regard each vertex in the embedded structure as the mean of a gaussian component such that the entire embedding is represented as a mixture model. the central idea is that if we have two structures that are highly similar, as we align one structure closer to the other, their corresponding mixture models become accordingly similar. by trying to minimize the divergence between the two mixture models, we can eventually find the best superimposition. we refer to this method of alignment as gaussian ceed or gceed for short. using gceed, we attempted to determine the specificity information between protein families provided in ramani et al.. the first example is the case of the interacting protein family of gyra and gyrb. each protein family is known to have a single paralog, parc and pare respectively, and these paralogs are also known to interact. figure shows the trees and interaction specificity between these two multigene families. results of the initial superimposition are shown in figure 6-step the probability matrix is shown after having converted probabilities to grayscale values such that darker elements at denote a higher probability of correspondence between i-th protein of family and j-th protein of family proteins are arranged such that correct individual binding partners lie along the diagonal. in this first step we see that the initial alignment appears to have found the correct broader interaction specificity of gyra with gyrb and parc with pare as observed by the distinct segmentation of the probability matrix into two distinct regions. for parc/pare, correct correspondence for three individual interactions was also found in the initial alignment. both regions a and b, being indeterminate, are separately superimposed in an iterative manner with results after each superimposition shown in the submatrices of figure the final result after complete alignment is shown in figure here we can see that gceed successfully predicted the interaction specificity for out of individual interactions. the other misassigned pairs were degenerate cases and their interaction specificity could not be further defined due to a lack of structural information. the reason for this can in part be observed within figure where the four proteins from each family can be observed to be very close to each other. in such instances it is difficult for the algorithm to find a correct high-probability mapping as multiple alignments are equally viable. nevertheless, the interaction specificity at the protein-family level was correctly predicted. in addition, over half of the specific interactions could be recovered solely from the alignment of these structures. we performed the same specificity analysis using gceed to a total of protein family pairs used in previous studies and compared results to that of matrix and morph in terms of stringent accuracy. as can be observed, there is no significantly superior approach, as all methods show instances where they have the greatest accuracy of specificity prediction. however, we emphasize the extra functionality of gceed that is suited to realistic situations where the size of the protein families at hand are unlikely to be identical, and/or there exist some a priori knowledge of validated interacting protein interactions. as a demonstration of this functionality within gceed, we again used the case of gyra and gyrb interactions. we first made the gyra tree progressively smaller by sampling from nineteen down to ten sequences from the total of twenty gyra orthologs, with different combinations for each size. we then performed specificity prediction by aligning each sampled gyra tree with the complete 20-node gyrb tree. to evaluate our performance, we introduce the vicinity hit rate as a means to estimate how close each node's true interacting partner is in relation to others within the aligned structures. specifically, we define the vicinity hit rate as the ratio of nodes that have their true interacting parter within top three highest predicted probability partners. thus the vicinity hit rate allows for situations where the true interacting partner is very close to the predicted interaction partner as determined through the alignment. results of this analysis is shown in figure again, each histogram along the x-axis was generated from samples of the gyra tree of corresponding size and the dark line shows how the average hit rate changes as the size of this tree decreases. in this instance, the ability for gceed to determine binding specificities with a vicinity hit rate of approximately 65% is relatively well maintained out to approximately leaves or a 25% difference in tree sizes. as the difference between tree sizes decreases, we also begin to observe greater numbers of very poor predictions along with lesser numbers of very good predictions. these arise in situations where the the smaller tree fits very well, but in the wrong position within the larger tree, resulting in a very poor vicinity hit rate ). the situation is analogous, but far less common for the high vicinity rate predictions. we would expect that additional information in the form of prior knowledge of an existing protein interaction pair would help to improve predictive performance. such knowledge can be readily introduced into the gceed alignment scheme and results of knowing just a single pair a priori are shown in figure here we picked a random, but correct pair of interacting proteins between the two trees to serve as the a priori known information. as these proteins interact, we assume that they must be near each other in the final superimposition. we thus impose a constraint in the optimization of equation, where the two proteins are kept within a pre-specified distance range. results show that use of prior knowledge provides a significant improvement in the stability of the vicinity hit rate, with a mean hit rate of approximately 60% even when reducing tree size to nearly half of its original value. in addition, using the structural information provided by the known interaction pair, we were able to avoid degenerate cases ). in the comparisons between trees with greatest difference in size, the average vicinity hit rate of ten-node sample trees was % without prior knowledge versus % when using a single known protein pair. together, these results suggest the potential for using gceed in realistic situations where differences in tree sizes exist and/or prior information is available.  in this work, we have described a novel approach for the comparison of phylogenetic trees, represented as embedded structures, and shown several examples of its application. first, when applied to the prediction of protein interactions, we see an improvement in prediction accuracy using the rceed/vceed approach when compared to other available approaches. we note, that high similarity between two embedded structures does not require that there is a physical interaction between members, but is only suggestive of the possibility. similarly, the physical interaction between two proteins does not necessitate coevolution. thus coevolutionary approaches such as those presented here can only identify a portion of the complete interactome within a given species. for the enhanced prediction of protein interactions, approaches such as rceed/vceed may show their greatest efficacy when combined with other computational approaches. with vceed, we were also able to perform a local alignment between structures, providing the opportunity to detect outliers that often indicate unusual evolutionary events including the horizontal gene transfer described here. while phylogenetic methods which detect incongruity between trees are generally considered the gold-standard for hgt detection, these methods are not readily automatable and require extensive manual analysis. our results suggests that vceed has significant potential in aiding such identifications. by using the information inherent in the representation of a tree as an embedded structure, we were able to demonstrate the ability to align and measure the similarity between trees even when correspondence information is not available or when their sizes are different. while a basic example, the need to establish interaction specificity between interacting protein families supports the development of new approaches, and in this regard, gceed shows significant promise. while the embedding and superimposition of taxa within a euclidean space in no way supersedes the use of a phylogenetic tree, it does provide several useful capabilities. for instance, embedding generates a deterministic structure that bypasses ambiguities associated in direct tree comparisons by transforming a specific distance matrix into a single specific shape enabling consistent comparison between trees. similarly, use of a representative embedding also makes it possible to take into account the entire point-pattern structure all at once when determining correlation, rather than examining pair-by-pair correlation as in the mirrortree or related approaches. finally, the representation of trees as embedded structures provides the capability to compare trees of different size, which is a built-in limitation of correlation-based methods. in this case, it becomes a matter of comparing two structures using procedures based on registration approaches such as the gceed approach proposed in this work. as a whole, the xceed approach provides an additional set of tools for the study of phylogenetic trees and associated evolutionary processes. 
the understanding of evolutionary relationships is a fundamental aspect of modern biology, with the phylogenetic tree being a primary tool for describing these associations. these approaches provide additional tools for the study of phylogenetic trees and associated evolutionary processes. furthermore, we show its applicability to both the detection of horizontal gene transfer events as well as its potential use in the prediction of interaction specificity between a pair of multigene families. we demonstrate the application of this approach to the prediction of coevolving protein interactions and demonstrate its improved performance over the mirrortree, tol-mirrortree, phylogenetic vector projection, and partial correlation approaches. we describe a novel approach for the comparison of phylogenetic distance information based on the alignment of representative high-dimensional embeddings.
 the understanding of evolutionary relationships is a fundamental aspect of modern biology, with the phylogenetic tree being a primary tool for describing these associations. however, comparison of trees for the purpose of assessing similarity and the quantification of various biological processes remains a significant challenge.  we describe a novel approach for the comparison of phylogenetic distance information based on the alignment of representative high-dimensional embeddings. the xceed methodology, which utilizes multidimensional scaling and procrustes-related superimposition approaches, provides the ability to measure the global similarity between trees as well as incongruities between them. we demonstrate the application of this approach to the prediction of coevolving protein interactions and demonstrate its improved performance over the mirrortree, tol-mirrortree, phylogenetic vector projection, and partial correlation approaches. furthermore, we show its applicability to both the detection of horizontal gene transfer events as well as its potential use in the prediction of interaction specificity between a pair of multigene families.  these approaches provide additional tools for the study of phylogenetic trees and associated evolutionary processes. source code is available at http://gomezlab.bme.unc.edu/tools. 