systems biology research is like solving a jigsaw puzzle : the goal is to figure out how the various parts ( i.e. genes and proteins within the cell ) interact and work together .
the interactome of an organism is then analogous to the puzzle s key : it describes the network of all the protein  protein interactions ( ppis ) in a cell . as such , identifying all the protein - protein interactions for an organism is of great value , akin to sequencing its genome . despite the use of high - throughput techniques in discovering ppis , however , the coverage of experimentally determined ppi data remains poor ( table 1 ) .
such low coverage is partly because the set of possible ppis to be verified is so large ( 100 million for a species with 10 000 genes ) that any exhaustive experimental verification will take a long time , even with high - throughput techniques .
indeed , the rate of ppi discovery has slowed down in recent years ( figure 1 ) .
for example , tandem affinity purification experiments have historically had difficulty identifying transient interactions , while yeast two - hybrid experiments may produce false positives due to promiscuous proteins ( 1 ) ; recently , statistical methods have been proposed to improve confidence in the output of these experiments ( 2,3 ) 
 table 1.availability of experimental ppi data for major eukaryotic organismsorganismnumber of interactionspercentage of proteins with at least one interactionmouse14866.0human26 64041.8worm455914.5fly22 74052.7yeast48 90193.5the statistics here and in figure 1 have been computed using data from biogrid ( v 2.0.53 ) ( 35 ) .
data based on phenotypic suppression / enhancement and synthetic interaction was excluded as these experiments do not provide evidence of a direct physical interaction between proteins . 

availability of experimental ppi data for major eukaryotic organisms the statistics here and in figure 1 have been computed using data from biogrid ( v 2.0.53 ) ( 35 ) .
data based on phenotypic suppression / enhancement and synthetic interaction was excluded as these experiments do not provide evidence of a direct physical interaction between proteins .
the paucity of interactome coverage has motivated significant research interest in methods for supplementing experimentally determined ppi data with interactions inferred or predicted from other sources . a wide variety of methods have been proposed .
one approach is to use interologs , which are basically ppis mapped from another species to the target species ( 4,5 ) .
another approach is to use functional genomic data and leverage the observation that a pair of interacting proteins is also likely to have similar go annotations , occupy the same cellular sub - compartments , or correspond to genes with similar expression profiles ( 8,9 ) .
consequently , many researchers have described machine learning - based approaches to predict ppi data from functional genomic data such as gene expression , cellular localization and go annotation .
predictions from many of these approaches have been aggregated into a number of databases / web services offering predicted ppis .
the string database ( 10 ) combines experimental datasets ( e.g. kegg , biogrid , hprd ) with computational predictions based on co - expression , interologs and text - mining , etc . the entries in this database correspond to functional interactions , and may not always be directly interpretable as ppis .
another database , intact ( 11 ) , focuses more on inferring interactions from expert curation of data from literature .
other public services include domino ( 12 ) , interdom ( 13 ) and i2d ( 14 ) .
however , all of these databases suffer from a common selection bias : often , the proteins that have been selected for ppi experiments are usually genes / proteins that have received some attention before and , as such , are also more likely to have functional genomic data . in this article , we describe struct2net , a web service for predicting ppis using a structure - based approach .
our method predicts interactions by threading each pair of protein sequences onto potential structures in the protein data bank ( pdb ) ( 15 ) .
struct2net provides ppi predictions that are independent of all the non - structure - based approaches and may thus be combined with any of them .
another key advantage of our web server is that , apart from the pdb data , the prediction algorithm only requires protein sequence data as input .
it can thus be applied to proteins for which no functional data is available provided there is a suitable pdb structural template available . the use of structure - based approaches to predict interaction has been previously proposed .
aloy and russell ( 16 ) suggested the use of structure - based approaches to predicting ppis .
( 17 ) constructed statistical potential functions to evaluate potential ppis and later described multiprospector , a structure - based prediction algorithm ( 18 ) . in a previous paper , we proposed a prediction algorithm ( also used by struct2net ) .
our algorithm builds upon previous work like multiprospector , by combining a threading approach for template alignment with a novel machine learning approach to estimate a confidence score for the interaction . in our previous proof - of - concept paper
, we discussed how struct2net s results compare favorably to related work ( 19 ) .
unfortunately , the progress made in prediction has not yet translated into comprehensive community resources .
aloy and russell ( 20 ) have described interprets , a web - server to predict ppis for a given protein , using a homology modeling approach .
we have already mentioned lu et al.s multiprospector tool which also predicts ppis ( 17 ) .
more recently , fukuhara and kawabata have described homcos ( 21,22 ) a web - server that performs a similar task by homology modeling .
modbase is a database of homology models for protein complexes that have high sequence similarity to known structures ( 23 ) .
adan is a specialized database for prediction of ppis mediated by linear motifs and utilizes position - specific matrices to assess putative interactions ( 24 ) .
successful use of homology modeling requires relatively high sequence similarity between the query and template protein pairs .
in contrast , we use a threading - based approach which widens the range of proteins for which predictions can be made .
( 22 ) have reported that homcos achieves a recall of 80% with a precision of about 10% ; in comparison , struct2net achieves a recall of 80% with a precision of 30% [ here , recall = ( true positives)/(true positives + false negatives ) and precision = ( true positives)/(true positives + false positives ) ] .
the struct2net approach can also be contrasted with methods that model ppis based on domain - domain interactions .
these approaches argue that the structural basis of protein interaction can be traced to the presence of interacting domains .
a domain can be represented simply by its sequence motif or as a structure - fragment .
given a set of known ppis , one can infer the set of domain pairings that are presumably the underlying cause of interaction . in principle , these pairs can then be used to make prediction for unannotated protein pairs .
there has been a significant amount of work on analyzing ppis using such domain interactions .
some researchers focus solely on the sequence signature of the domains , proposing methods to predict ppis using these sequence domains ( 25,26 ) . in previous work ,
we have discussed how such sequence - domain - based prediction can be combined with our approach in a machine - learning framework ( 19 ) .
we also described some results that suggest that struct2net s predictive ability compares well with the sequence - domain approaches .
prieto and las rivas ( 27 ) have reviewed publicly available databases that facilitate analysis of domain - based ppis : 3did ( 28 ) , snappi - db ( 29 ) , ipfam ( 30 ) , pibase ( 31 ) and psibase ( 32 ) .
while our approach has some parallels with these approaches , our goal is significantly different .
the domain interaction databases are essentially repositories of known structural data , analyzed specifically from a ppi perspective . prediction , which is our core goal , is usually out of the scope of these approaches . in the  methods overview section below , we suggest how struct2net could take advantage of some of these databases .
the guiding intuition behind our prediction approach is that if a potential interaction is sufficiently favorable from a thermodynamics perspective , it is likely to be true .
we provide a brief description of the algorithm here . for more details , see singh et al .
( 19 ) , which describes a proof - of - concept implementation of the algorithm .
given a pair of protein sequences , the first stage predicts the most likely structure of the complex formed by the two proteins and produces a vector of scores that quantitatively represent the thermodynamic suitability of this structure . for this task
, we start by analyzing the pdb to construct a database of complex - structure templates ; then we thread the two sequences jointly through the various templates in this database and identify the best fitting template .
our threading algorithm formulates the threading problem as an integer linear program ( ilp ) and uses branch - and - bound techniques to efficiently find the solution .
the ideas in this algorithm , when applied to a single - protein threading context in the raptor program , have performed well at various blind tests and competitions ( 33,34 ) . to speed up prediction
if some templates in our database appear in the list of psi - blast top hits ( e - value < 10 ) , we simply thread the sequence pair to these templates instead of the whole template database .
this speedup procedure does not lose accuracy since psi - blast is very good at close homolog detection .
we begin by using a simple geometric criterion to determine if two protein chains form a complex .
given two protein chains in the same pdb entry , we first calculate the distance between two ( non - hydrogen ) atoms from these two chains .
we assume that there is an interaction between two residues of different chains if there is at least one pair of atoms from these two residues with distance < 3.5  .
if there are at least 10 interacting residue pairs between two chains a and b , we say these two chains form a complex . to avoid redundancy
, we enforce the constraint that any two templates in the database share < 70% sequence identity . following this procedure ,
while our template database ( and the web server s predictions ) are currently built at the chain level , we intend to explore the incorporation of domain  domain interactions ( from databases like snappi , 3did , psibase , pibase , etc . ) into it .
the second stage of our prediction approach evaluates the likelihood of the interaction based on the predicted structure .
we compute various energy scores that evaluate the structure ( e.g. the quality of the interfacial region , the quality of fit for the individual proteins ) . given these
let yi be an indicator variable representing protein interaction , i.e. yi = 1 if the protein pair i interacts and 0 otherwise .
we fit the following model : 

  where  , 1 , 2 , etc .
to train this model , we constructed positive and negative training sets . obviously , the choice of these sets can have a substantial impact on the prediction algorithm s quality .
the exact criteria and a discussion about the rationale behind them are available at the struct2net website .
briefly , we require that the positive examples either come from a small set of trustworthy protocols or from low - throughput experiments ; or roughly correspond to co - clustered protein pairs in the ppi network .
we chose biogrid ( 36 ) as our data - source , but other multi - species genome - wide databases [ e.g. mint ( 37 ) or apid ( 38 ) ] could also be used . for negative examples ,
we require that the two proteins either be disconnected in the ppi network or be at least 3 hops away from each other . using these criteria , we had a training set of 62 519 pairs and a test set of 15 635 pairs ( with a positive : negative ratio of 1:6 approximately , in both sets ) .
our construction of the negative dataset was motivated by similar approaches in literature ( 8) . for positive datasets , we believe that our approach identifies true ppis with better confidence than an alternative approach that would select repeatedly observed ppis ( across multiple experiments ) .
in contrast , many high - throughput protocols ( e.g. yeast two - hybrid ) have systematic biases which may manifest as repeated false positives , even across multiple experiments .
in addition to the energy scores from the first stage , we aimed to enhance the model s predictive power by adding extra terms to it .
these included interaction terms , non - linear functions of the energy scores , as well as normalized scores ( e.g. interfacial energy normalized by the average of the two proteins sequence length ) .
we then used the akaike information criterion ( aic ) to select the model with the best trade - off of higher explanatory power and lower complexity . using this model , we computed the interaction score for the given joint structure .
as seen by the graph in figure 2 , our method has significant predictive power when tested on current data . for further details , including the construction of training / test datasets and evaluation of the algorithm ,
as the threshold for the interaction score is increased , the specificity of the model rises .
higher sensitivity , on the other hand , can be achieved by choosing lower specificity .
also , we note here that we do not make a prediction for a candidate protein pair if the first stage of our algorithm fails to predict a structure for them . 

. the prediction algorithm can achieve 60% sensitivity while maintaining 75% specificity as measured on the test set . here , sensitivity = ( true positives)/(true positives + false negatives ) and specificity = ( true negatives)/(true negatives + false positives )
. we constructed a training set and test set of positive and negative examples from yeast and fly , using criteria we have developed to identify high - confidence positive and negative examples of ppis ( see the website faq for details ) .
after training the logistic regression model on the training set , its performance was measured on the test set .
sensitivity versus specificity . the prediction algorithm can achieve 60% sensitivity while maintaining 75% specificity as measured on the test set . here ,
sensitivity = ( true positives)/(true positives + false negatives ) and specificity = ( true negatives)/(true negatives + false positives ) .
we constructed a training set and test set of positive and negative examples from yeast and fly , using criteria we have developed to identify high - confidence positive and negative examples of ppis ( see the website faq for details ) .
after training the logistic regression model on the training set , its performance was measured on the test set .
( saccharomyces cerevisiae , drosophila melanogaster , homo sapiens ) , ppi predictions have been pre - computed and can be retrieved by gene name or a wide array of gene identifiers , including 
ids from ensembl , embl , entrez , uniprotkb , genbank , flybase and saccharomyces genome database ( sgd ; figure 3a ) . for proteins from other organisms ,
users have the option of getting a quick - but - approximate result , by retrieving predictions from the best - hit ortholog over pre - computed results , or have a full - blown computation performed ( figure 3c ) .
furthermore , with full - blown computations , a batch query option is available for querying multiple sequences at a time .
in addition , with orthology - based approximation , users can specify just one protein identifier or fasta sequence ; in that case , all the interactions involving that protein will be returned . 

( c ) a query option for either a quick - but - approximate approach ( using orthology over pre - computed predictions from yeast , fly and human ) or a full - blown computation using the struct2net algorithm .
( d ) example of an output page when choosing to thread pairs of sequences onto all templates .
( c ) a query option for either a quick - but - approximate approach ( using orthology over pre - computed predictions from yeast , fly and human ) or a full - blown computation using the struct2net algorithm .
( d ) example of an output page when choosing to thread pairs of sequences onto all templates .
when querying by protein sequence and with orthology - based approximation selected , typical run - times are within 20 s. full - blown computations finish within 45 mins , given query and subject sequences . because of the potential for long run - times ( e.g. if the server is overloaded ) , we encourage the user to supply an email address to which a job i d and a link to the progress page are sent upon submission .
alternatively , users can check the progress of a submitted job by entering a job i d in the 
upon completion of a job , an email with a link to the results page will also be sent .
for pre - computed predictions in s. cerevisiae , d. melanogaster and h. sapiens , the output for each query protein sequence consists of a list of all predicted interactions along with their confidence scores ( figure 3d ) .
struct2net interactively links each gene hit to various sequence databases along with associated go annotations and aliases .
results are also cross - referenced with biogrid in the case where experimental data is available for a predicted interaction . for predictions in other organisms using the struct2net algorithm ,
the output for each sequence pair contains details on the best - fit complex templates used during the computation including sequence alignments , alignment scores , their associated z - scores and an interfacial energy calculated between the sequence pair ( figure 3d ) .
the confidence score ranges from 0 to 1 , with 0 indicating minimum confidence and 1 indicating maximum confidence . in the  about page of the website
, we discuss threshold choices that would allow a user to achieve a desired level of specificity in the output or a desired number of interactions above the threshold . for batch queries ,
results are separated by each pair of protein sequences . for users interested in performing large - scale database analysis and classification , bulk download of predictions for s. cerevisiae ,
we have further made available a script on the download page that facilitates the integration of struct2net s predictions with other tools . in the future ,
every 6 months , we will update our pre - computed predictions using the latest template database . in table 2 , we provide an example of our algorithm s results on a set of protein pairs often used as test cases . for comparison
multi - prospector no longer seems to be publicly available , and we could not include its results .
the test cases we have chosen are the same as chosen by fukuhara et al . for evaluating homcos ( 22 ) . as can be seen , for pairs that are thought to
be interacting ( table 2 ) , the final scores from struct2net are , on average , significantly higher than for non - interacting pairs ( table 2 ) .
furthermore , normalizing the difference between the average interacting and non - interacting scores for each method by the standard deviation of the method s scores suggests that the discriminatory ability of struct2net compares favorably with homcos and interprets . 

table 2.struct2net results for set of interacting and non - interacting protein pairsstruct2nethomcosinterpretsjob idtest pairsuniprot idstemplatesconfidencezseqconzconbest z - scoreinteracting protein pairs1olyn2pm1b34abp62314 , p623161d3bab0.62040.93.371.62n9ljtipg1g65jkp22141 , p306561irukl0.59062.71.34no hitsq44otfmd1gl2bco70439 , o883841gl2bc0.95837.94.383.42hz0n1hr91sxjbcp40339 , p386291sxjbc0.25181.33.772.87nqarc82j1finabp24941 , p202481e9hab0.42870.72.963.044ljqhza1ukvgyp39958 , p011231ukvgy0.66267.36.233.904lfmidj1bi7abq00534 , p427711bi7ab0.38551.12.370.849n2phlbi1id3afp61830 , p023091aoiab0.98945.65.394.59sntt8nhn1s1hjnp38701 , p410581s1gjn0.99023.70.271.28nbtgsu4p1ow3abq07960 , p615861ow3ab0.42562.33.982.58average0.6354.353.572.87standard deviation0.2514.91.721.14non - interacting protein pairsjtp3q2801g3nabq00534 , p427731g3nab0.34757.12.881.61jcefcqgq1oiubcp24941 , p202481e9hba0.42870.52.873.04yd4l76vd1gotabp04695 , p628711gg2ab0.24983.53.392.98yrjq0jzi1ow3abq07960 , p615861ow3ab0.42562.33.982.62jq260zec1f3macq13153 , q131531f3mac0.71843.57.053.49vj8bpgq21a9nabp09661 , p085791a9nab0.33445.12.822.690olmgnwz1k5dacp62826 , p41391none0.16966.74.152.298wea7wws1fq1abq16667 , p249411fq1ab0.42560.91.901.83ewvfv6tl1fbvacp22681 , p680361fbvac0.71753.20.87 - 0.31wvw4s9tw1qbkbcq92973 , p62826none0.18061.41.352.48average0.3960.423.132.27standard deviation0.2514.91.721.14we chose sets of interacting and non - interacting protein pairs ; these pairs are taken from an analysis by homcos authors ( 22 ) .
low confidence templates are indicated as  none. for comparison , the scores from homcos and interprets for these pairs are also shown .
struct2net provides a confidence score between 0 and 1 ( 0 indicates minimum confidence while 1 indicates maximum confidence ) .
the average positive and negative scores are separated by a larger magnitude in struct2net : the separation is about 0.96 sd in struct2net ; the corresponding separation in homcos is 0.26 sd , and in interprets is 0.53 sd .
struct2net results for set of interacting and non - interacting protein pairs we chose sets of interacting and non - interacting protein pairs ; these pairs are taken from an analysis by homcos authors ( 22 ) .
none. for comparison , the scores from homcos and interprets for these pairs are also shown .
struct2net provides a confidence score between 0 and 1 ( 0 indicates minimum confidence while 1 indicates maximum confidence ) .
the average positive and negative scores are separated by a larger magnitude in struct2net : the separation is about 0.96 sd in struct2net ; the corresponding separation in homcos is 0.26 sd , and in interprets is 0.53 sd .
a problem common to all structure - based ppi prediction methods is coverage : the number of known protein structures is vastly smaller than the number of known protein sequences . as such , no structural template may be available for the protein pair being queried .
in contrast to other web services that only use homology modeling , our use of protein threading affords not only greater accuracy but also greater coverage : in yeast and fly , it covers about 10% of the genome .
this is because homology modeling matches query proteins based only on sequence alignments to sequences with known structures ; in contrast , threading is able to capture alignments more in the  twilight zone by matching query sequences to structural templates ( 19 ) .
furthermore , it has been shown that localized threading using interface profiles can further improve coverage and accuracy ( 39,40 ) . while struct2net can be used for validation purposes ( e.g. to double - check entries in biogrid ) , its coverage limitations may at the present time make it better suited to be an exploratory tool , especially for unannotated proteins where only sequence information is available , or to be used in conjunction with low - confidence experimental data .
a problem common to all structure - based ppi prediction methods is coverage : the number of known protein structures is vastly smaller than the number of known protein sequences . as such
in contrast to other web services that only use homology modeling , our use of protein threading affords not only greater accuracy but also greater coverage : in yeast and fly , it covers about 10% of the genome .
this is because homology modeling matches query proteins based only on sequence alignments to sequences with known structures ; in contrast , threading is able to capture alignments more in the  twilight zone by matching query sequences to structural templates ( 19 ) .
furthermore , it has been shown that localized threading using interface profiles can further improve coverage and accuracy ( 39,40 ) .
while struct2net can be used for validation purposes ( e.g. to double - check entries in biogrid ) , its coverage limitations may at the present time make it better suited to be an exploratory tool , especially for unannotated proteins where only sequence information is available , or to be used in conjunction with low - confidence experimental data .
although high - throughput biochemical approaches for discovering ppis have proven very successful , the current experimental coverage of the interactome remains inadequate and would benefit from computational tools .
the struct2net web server allows the user to easily query for high - probability structure - based interactions as a potentially high - quality , high - coverage data source for large - scale integrative approaches to interactome construction .
the predicted interactions also include a numeric score , allowing users to further filter the data . to the best of our knowledge
, this web server is the first of its kind and will be of considerable value to systems biologists interested in ppis , partly because of the effort we have put into identifying high - confidence positive and negative examples of ppis as inputs to machine learning algorithms and the extensive computational effort involved in making each prediction .
a strength of this web service is its ongoing integration of up - to - date structural templates for improving its predictions .
struct2net s predictions may be used on their own or as one of the inputs into a computational framework that combines them with other sources ( e.g. low - quality experimental data or predictions from functional genomic data ) .
( 9 ) have described some general approaches for combining various predictors of ppi data .
this publication was made possible by grant number 1r01gm081871 ; from the national institute of general medical sciences .
its contents are solely the responsibility of the authors and do not necessarily represent the official views of the nih or nigms .
tti - c internal research funding ( j.x . ) . funding for open access charge : national institutes of health .
 struct2net is a web server for predicting interactions between arbitrary protein pairs using a structure - based approach . 
 prediction of protein  protein interactions ( ppis ) is a central area of interest and successful prediction would provide leads for experiments and drug design ; however , the experimental coverage of the ppi interactome remains inadequate . 
 we believe that struct2net is the first community - wide resource to provide structure - based ppi predictions that go beyond homology modeling . also , most web - resources for predicting ppis currently rely on functional genomic data ( e.g. go annotation , gene expression , cellular localization , etc . ) . 
 our structure - based approach is independent of such methods and only requires the sequence information of the proteins being queried . 
 the web service allows multiple querying options , aimed at maximizing flexibility . for the most commonly studied organisms ( fly , human and yeast ) , 
 predictions have been pre - computed and can be retrieved almost instantaneously . for proteins from other species , 
 users have the option of getting a quick - but - approximate result ( using orthology over pre - computed results ) or having a full - blown computation performed . 
 the web service is freely available at http://struct2net.csail.mit.edu . 
INTRODUCTION
METHODS OVERVIEW
WEB SERVER
Limitations
CONCLUSIONS
FUNDING