the prediction of protein interactions from sequence and genomic features is helping in the functional interpretation of the massive amounts of genomic information .
the context of a protein in the  interactome of a given organism provides important information on its biological role .
computational techniques for the prediction of protein interactions based on sequence and genomic features ( context - based methods ) provide information which is orthogonal and complementary to the traditional methods based on sequence similarity ( similarity - based methods ) ( 1 ) .
one of these computational methods is based on the fact that interacting families of proteins ( i.e. a family of ligands and their corresponding receptors ) tend to have similar phylogenetic trees .
this was first observed qualitatively ( 2 ) and later quantitatively evaluated in large sets of interacting proteins ( 3,4 ) . a hypothesis for explaining this relationship between interaction and tree similarity states that interacting partners are forced to adapt to each other .
this process of co - adaptation should lead to correlated evolutionary histories , which in turn should be reflected in a tree similarity higher than the expected background similarity due to the underlying speciation process ( 5 ) .
one practical way of quantifying this similarity is to calculate the correlation between the two sets of distances extracted from the two trees ( 3,4 ) .
this methodology has been followed by many authors who developed different implementations and variations of it ( 511 ) .
it can be applied to evaluate whether or not two sets of proteins , for which the mapping ( links between the leaves of both trees ) is known , interact .
for example , the eventual interaction between two sets of orthologues for which the mapping is provided by the organisms themselves , can be investigated .
this allows , among other things , to predict pairs of interacting proteins on a genomic scale by evaluating the similarity of trees for all pairs of proteins within a genome ( pairs of groups of orthologues , actually ) ( 4 ) . on the other hand
, we can start from two families known to interact and predict the mapping based on the idea that the real mapping would be the one maximizing the similarity between the trees ( 7 ) .
predicting the mapping between the members of two interacting protein families ( i.e. which receptor within one family interacts with which ligand within the other ) is very important especially in eukaryotic organisms . in these organisms , large families of interacting paralogues exist for which only one or a small number of pairs of interacting proteins have been experimentally determined ( i.e. ras / ras effectors , chemokines / chemokine receptors ) .
most biologists working with eukaryotic proteins face the problem that there is more than one paralogue for their protein and for its interactors and that , in many cases , the unknown network of interactions between the members of these families is crucial for explaining their biological role .
the exhaustive exploration of all possible mappings between two sets of proteins ( in the search for the one maximizing the tree similarity ) is unfeasible due to the combinatorial nature of the problem : the number of possible mappings between two sets of n elements is n!. for this reason , current approaches for finding these mappings use heuristic techniques to avoid the exhaustive exploration of all the possibilities .
ramani and marcotte ( 7 ) developed a method which uses a monte carlo approach to perform a 
the search space can be reduced even more by avoiding mappings incompatible with certain characteristics of phylogenetic trees , like automorphism ( 11 ) .
because of their intrinsic heuristic nature , these methods do not ensure that the best solution is found but they may find a sub - optimal solution ( trapped within a local minimum ) . for a user interested in the interactions between the members of two families of proteins , it is worth further exploring the ( eventually sub - optimal ) solution proposed by these heuristic approaches .
this exploration can be driven by expert knowledge ( forcing pairs of proteins suspected or known to interact ) and/or by performance figures indicative of the reliability of the proposed links . in this work we present tsema , 
the server for efficient mapping assessment. this system is intended not only to provide the user with a predicted mapping based on an heuristic search , but to allow her / him to interactively explore and modify it through a web interface .
this interactive process can be used to find better solutions not explored by the heuristic approach due to intrinsic limitations .
the initial input for the system are the two families of homologous proteins for which the user wants to predict the mapping ( which protein within one family interacts with which one within the other ) .
the user can submit this information through a plain web interface ( figure 1 ) .
the only compulsory fields ( apart from the information on the families ) are a name for the job and an email address where to send forthcoming messages and results .
there is a set of advanced options to control the monte carlo algorithm ( see below ) which are intentionally blurred unless the user decides to enable them ( figure 1 ) .
for the two families of proteins , the user can either submit two phylogenetic trees ( in newick format ) or two multiple sequence alignments in a format compatible with clustalw ( 12 ) . in the second case , the system generates the phylogenetic trees from the alignments using the neighbour joining algorithm implemented in clustalw .
it is highly recommended that the user submits her / his own tree generated with more sophisticated techniques ( parsimony or bayesian trees ) . in the next step ,
distances for all pairs of proteins within both families are extracted from the phylogenetic trees by summing the length of the branches separating each pair of proteins in the trees .
these two sets of distances are used to run a modified implementation of ramani and marcotte 's monte carlo metropolis method ( 7 ) for finding the mapping between the two sets of proteins which maximizes the matching between these two sets of distances .
this implementation , written in c , includes the possibility of running two sets with different number of proteins , which is the situation for most real interacting families , owing to promiscuity , pseudogenes and the like . in this implementation
it is also possible to use different scores for evaluating the matching between the distance matrices , including linear correlation and root mean square deviation . owing to its stochastic nature
, the monte carlo step is repeated many times ( 500 by default ) to obtain an estimation of the consistency of the results .
for each one of the 500 runs , the system explores up to 1 000 000 solutions .
the complexity of both trees is also calculated as the entropy of the distribution of distances .
trees with low complexity are expected to produce worse results since there is not enough information to distinguish between mappings ( 7 ) .
the results of this first step include the overall best mapping obtained through all the monte carlo runs , the best mapping obtained in each one of the runs , and a contingency table which shows in how many of these runs a given pair of proteins is linked .
this raw file can be further processed by the user to implement her / his own analysis , or it can be submitted to the interactive analysis part of the server (  new analysis button ) . the single raw file with the results produced in the first step is the only input required for the analysis , although the user can additionally provide an email address and a job identifier to facilitate tracking of the jobs .
the interactive analysis interface ( figure 1 ) shows the list of predicted interacting pairs of proteins corresponding to the best mapping found ( the one with the best score through all the runs ) . for each pair
segregation which gives an idea of the difference between the reliability of that pair and the second best reliability value . the reliability for pair ab could be different from pair ba , since a and b might be confronted with a different number of proteins .
the entropies of the two trees ( see above ) are also shown at the top of the lists .
the interface also displays a graphical representation of the two trees showing the predicted interacting pairs of proteins corresponding to the current mapping ( figure 1 ) .
the colour of the links correspond to the ab reliability score of the list above .
if there is bootstrap information in the trees provided by the user it is included in the representation .
many wrong pairings are associated to internal nodes with low bootstrap support ( data not shown ) .
the last section of the interface shows the distance correlation plots corresponding to the current and other mappings .
the figure on the left shows the correlation plot of the current mapping superposed with that of the previous mapping , while the one on the right shows the correlation plot of the current mapping compared with that of the original mapping .
these plots can be used to asses whether a given change in the mapping affects many distances , or whether a given mapping produces an overall good score but there are some outliers .
the user can start changing links in the list of predicted pairs and asses how these changes affect the scores ( reliability and segregation ) .
anytime the user changes a link , the new mapping incorporating that change is generated and shown in the tree representation and in the correlation plots .
the user can undo the changes to the previous mapping or load the original ( first ) mapping .
the links the user is more confident about can be  fixed to avoid changing them .
this interface allows the user to interactively explore alternative mappings by applying some changes and assessing the quality of the new mappings graphically and by the scores .
the coincidence matrix ( figure 1 ) is a good starting point for guessing possible changes in the mappings .
a given pair which is found in most of the mappings generated by the different runs ( high reliability in the coincidence matrix ) might not be present in the overall highest scoring tree . in this case
the user can also incorporate expert information in this process , e.g. by forcing some pairs suspected to interact .
the system also has a help page and a guided tutorial for the user to get familiar with the interface and its functioning .
the initial input for the system are the two families of homologous proteins for which the user wants to predict the mapping ( which protein within one family interacts with which one within the other ) .
the user can submit this information through a plain web interface ( figure 1 ) .
the only compulsory fields ( apart from the information on the families ) are a name for the job and an email address where to send forthcoming messages and results .
there is a set of advanced options to control the monte carlo algorithm ( see below ) which are intentionally blurred unless the user decides to enable them ( figure 1 ) .
for the two families of proteins , the user can either submit two phylogenetic trees ( in newick format ) or two multiple sequence alignments in a format compatible with clustalw ( 12 ) . in the second case , the system generates the phylogenetic trees from the alignments using the neighbour joining algorithm implemented in clustalw .
it is highly recommended that the user submits her / his own tree generated with more sophisticated techniques ( parsimony or bayesian trees ) . in the next step ,
distances for all pairs of proteins within both families are extracted from the phylogenetic trees by summing the length of the branches separating each pair of proteins in the trees .
these two sets of distances are used to run a modified implementation of ramani and marcotte 's monte carlo metropolis method ( 7 ) for finding the mapping between the two sets of proteins which maximizes the matching between these two sets of distances .
this implementation , written in c , includes the possibility of running two sets with different number of proteins , which is the situation for most real interacting families , owing to promiscuity , pseudogenes and the like . in this implementation
it is also possible to use different scores for evaluating the matching between the distance matrices , including linear correlation and root mean square deviation . owing to its stochastic nature
, the monte carlo step is repeated many times ( 500 by default ) to obtain an estimation of the consistency of the results .
for each one of the 500 runs , the system explores up to 1 000 000 solutions .
the complexity of both trees is also calculated as the entropy of the distribution of distances .
trees with low complexity are expected to produce worse results since there is not enough information to distinguish between mappings ( 7 ) .
the results of this first step include the overall best mapping obtained through all the monte carlo runs , the best mapping obtained in each one of the runs , and a contingency table which shows in how many of these runs a given pair of proteins is linked .
this raw file can be further processed by the user to implement her / his own analysis , or it can be submitted to the interactive analysis part of the server (  new analysis button ) .
the single raw file with the results produced in the first step is the only input required for the analysis , although the user can additionally provide an email address and a job identifier to facilitate tracking of the jobs .
the interactive analysis interface ( figure 1 ) shows the list of predicted interacting pairs of proteins corresponding to the best mapping found ( the one with the best score through all the runs ) . for each pair
segregation which gives an idea of the difference between the reliability of that pair and the second best reliability value .
the reliability for pair ab could be different from pair ba , since a and b might be confronted with a different number of proteins . hence , there are two values of reliability and segregation for each pair
the entropies of the two trees ( see above ) are also shown at the top of the lists .
the interface also displays a graphical representation of the two trees showing the predicted interacting pairs of proteins corresponding to the current mapping ( figure 1 ) .
the colour of the links correspond to the ab reliability score of the list above . if there is bootstrap information in the trees provided by the user it is included in the representation .
many wrong pairings are associated to internal nodes with low bootstrap support ( data not shown ) .
the last section of the interface shows the distance correlation plots corresponding to the current and other mappings .
the figure on the left shows the correlation plot of the current mapping superposed with that of the previous mapping , while the one on the right shows the correlation plot of the current mapping compared with that of the original mapping .
these plots can be used to asses whether a given change in the mapping affects many distances , or whether a given mapping produces an overall good score but there are some outliers .
the user can start changing links in the list of predicted pairs and asses how these changes affect the scores ( reliability and segregation ) .
anytime the user changes a link , the new mapping incorporating that change is generated and shown in the tree representation and in the correlation plots .
the user can undo the changes to the previous mapping or load the original ( first ) mapping .
this interface allows the user to interactively explore alternative mappings by applying some changes and assessing the quality of the new mappings graphically and by the scores .
the coincidence matrix ( figure 1 ) is a good starting point for guessing possible changes in the mappings .
a given pair which is found in most of the mappings generated by the different runs ( high reliability in the coincidence matrix ) might not be present in the overall highest scoring tree . in this case
the user can also incorporate expert information in this process , e.g. by forcing some pairs suspected to interact .
the system also has a help page and a guided tutorial for the user to get familiar with the interface and its functioning .
the relationship between protein interactions and similarity of phylogenetic trees has been extensively used for assessing the possible interaction between two proteins , and to predict the mapping between the members of two families known to interact . the server presented here
it allows the user to predict a mapping between two sets of proteins using an heuristic approach and to interactively refine and improve it .
the accuracy of monte carlo - based methods like the one implemented here has been quantified for some cases ( 7,11 ) .
it is very difficult to obtain a large enough set of examples for testing these methods : interacting families for which the mapping is known , with enough members and so on .
this is something that remains to be done and that will allow to obtain performance figures for our modified method ( obviously without the interactive part ) and , more importantly , to relate that performance with parameters like tree complexity , number of sequences , tree similarity of the right mapping , bootstrap values and the like . while that quantification is not available , the user has to qualitatively assess these parameters .
for example , if the complexity ( entropy ) of one or the two trees is low , it means that there is not enough topological information in the trees to distinguish the right mapping .
even if the overall entropy of the trees is not bad , there could be 
for instance , for two proteins which are exactly at the same distance from their ancestral node , the mappings involving one or the other would have exactly the same score and hence they would be indistinguishable .
special instances of this would be pairs of identical proteins ( distance = 0 ) .
similarly , we have observed many wrong predictions involving clades in the tree for which the bootstrap support is low . in summary ,
this is why it is desirable for the user to provide a manually - curated tree , obtained with state - of - the - art methodologies ( like bayesian trees ) instead of relying on the neighbour - joining tree automatically generated by the server .
the generation of bayesian trees is very cpu - demanding and , to some extend , a manual process .
we are working on incorporating this methodology in future versions of the server . as more genomes continue to be sequenced in a high - throughput way , the number of interacting families for which the mapping is unknown will grow too , specially for eukaryotic genomes .
for many families of paralogues with biomedical interest , the differential interaction between their members is a crucial aspect for explaining their functioning ( ras , chemokines , g - proteins and so on ) .
the server presented here can help in elucidating these complex networks of interactions by interactively assessing the landmarks the evolution left on them .
screenshots of tsema 's web interface . ( 1 ) initial screen for submitting a new job .
( 2 ) list of predicted links ( mapping ) . ( 3 ) coincidence matrix . ( 4 ) examples of representations of the phylogenetic trees together with the predicted mappings .
 an entire family of methodologies for predicting protein interactions is based on the observed fact that families of interacting proteins tend to have similar phylogenetic trees due to co - evolution . 
 one application of this concept is the prediction of the mapping between the members of two interacting protein families ( which protein within one family interacts with which protein within the other ) . 
 the idea is that the real mapping would be the one maximizing the similarity between the trees . 
 since the exhaustive exploration of all possible mappings is not feasible for large families , current approaches use heuristic techniques which do not ensure the best solution to be found . 
 this is why it is important to check the results proposed by heuristic techniques and to manually explore other solutions . 
 here we present tsema , the server for efficient mapping assessment . 
 this system calculates an initial mapping between two families of proteins based on a monte carlo approach and allows the user to interactively modify it based on performance figures and/or specific biological knowledge . 
 all the explored mappings are graphically shown over a representation of the phylogenetic trees . 
 the system is freely available at . 
 standalone versions of the software behind the interface are available upon request from the authors . 
INTRODUCTION
METHODS AND WEB INTERFACE
First step: generating the initial mapping
Second step: interactive analysis and modification of the proposed mapping
DISCUSSION
Figures and Tables