Inferring interaction partners from protein sequences using mutual information
[['Most cellular processes are carried out by interacting proteins .', 'Functional protein-protein interactions allow multi-protein complexes to assemble , and ensure proper signal transduction in various pathways .', 'Hence , mapping functional protein-protein interactions is an important fundamental question .', 'High-throughput experiments have recently elucidated a substantial fraction of protein-protein interactions in a few model organisms [1] , but such experiments remain challenging .', 'An attractive alternative is to exploit the increasingly abundant sequence data in order to identify functional protein-protein interaction partners .', 'The sequences of interacting proteins are correlated , both because of evolutionary constraints arising from the need to maintain physico-chemical complementarity among amino-acids in contact , and because of shared evolutionary history .', 'The first type of correlations has received substantial interest , both within single proteins and across protein partners , as evolutionary constraints induce correlations between amino acids that are in contact in the folded protein or in the multi-protein complex .', 'Hence , the correlations observed in multiple sequence alignments of homologous proteins contain information about protein structure .', 'Global statistical models allow direct and indirect correlations to be disentangled [2–4] .', 'Such models , built using the maximum entropy principle [5] , and assuming pairwise interactions , known in the field of proteins as Direct Coupling Analysis ( DCA ) , have been used with success to determine three-dimensional protein structures from sequences [6 , 7] , to analyze mutational effects [8–11] and conformational changes [12 , 13] , to find residue contacts between known interaction partners [4 , 14–20] , and most recently to predict interaction partners from sequence data [21 , 22] .', 'DCA models lay the emphasis on interactions between residues that are in direct contact in the three-dimensional protein structure .', 'However , correlations in protein sequences also have important collective modes [23 , 24] , which can arise from functional selection [25 , 26] , and additional correlations are due to phylogeny [23 , 27 , 28] .', 'These contributions are deleterious to the prediction of contacts [28] but not necessarily to the prediction of interacting partners , since a pair of interacting partners may be subject to common functional selection , and may also have a more strongly shared phylogenetic history than non-interacting proteins .', 'Here , we present an alternative approach to predict interaction partners from sequence data , among the paralogous proteins belonging to two interacting families .', 'In contrast to the previous pairwise maximum entropy-based approaches [21 , 22] , the present method is based on an approximate maximization of mutual information between the sequences from the two protein families .', 'Specifically , we develop a variant of the iterative pairing algorithm ( IPA ) introduced in [21] , where we use mutual information ( MI ) as a score to maximize , instead of the effective interaction energy from a pairwise maximum entropy ( DCA ) model .', 'We demonstrate that this mutual information-based algorithm ( MI-IPA ) performs slightly better than the one ( DCA-IPA ) introduced by us and colleagues in [21] .', 'Our findings entail that the statistical dependences allowing interaction partner prediction from sequence data are not restricted to the contacting residue pairs revealed by DCA .'], ['Consider an alignment of M concatenated sequences AB of length L , where A is a protein from family A and B is a protein from family B . At each amino-acid site i ∈ {1 , ‥ , L} , a given sequence can feature any amino acid ( represented by α ∈ {1 , ‥ , 20} ) , or a gap ( represented by α = 21 ) .', 'To describe the statistics of this concatenated alignment ( CA ) , we employ the single-site frequencies of occurrence of each state α at each site i , denoted by fi ( α ) , and the two-site frequencies of occurrence of each ordered pair of states ( α , β ) at each ordered pair of sites ( i , j ) , denoted by fij ( α , β ) .', 'These empirical frequencies are obtained by counting the sequences where given residues occur at given sites and dividing by the number M of sequences in the CA .', '( Note that when computing frequencies from real protein data , it is useful to weight sequences so as to attenuate the impact of biased sampling , and to include pseudocounts , in order to mitigate finite-sample effects , see Methods . )', 'The empirical frequencies constitute estimates of the corresponding probabilities pi ( α ) and pij ( α , β ) , and tend toward them in the limit where the number M of sequences in the alignment tends to infinity .', 'The pointwise mutual information ( PMI ) of a pair of residues ( α , β ) at a pair of sites ( i , j ) is defined as [29]:', 'PMI i j ( α , β ) = log [ p i j ( α , β ) p i ( α ) p j ( β ) ] ≈ M ≫ 1 log [ f i j ( α , β ) f i ( α ) f j ( β ) ] .', '( 1 )', 'Averaging this quantity over all possible residue pairs yields the mutual information ( MI ) between sites i and j [30]:', 'MI i j = ∑ α , β p i j ( α , β ) PMI i j ( α , β ) = ∑ α , β p i j ( α , β ) log [ p i j ( α , β ) p i ( α ) p j ( β ) ] .', '( 2 )', 'PMI has been used in linguistics to study the co-occurrence of words [31 , 32] .', 'Note that in some instances [29 , 31] PMI is called MI , and MI is then referred to as the average value of MI .', 'We define a pairing score SAB for each pair AB of proteins as the sum of the PMIs of the inter-protein pairs of sites of this concatenated sequence ( i . e . those that involve one site in protein A and one site in protein B ) :', 'S AB = ∑ i = 1 L A ∑ j = L A + 1 L PMI i j ( α i , β j ) , ( 3 )', 'where we have denoted the concatenated sequence AB by ( α 1 , … , α L A , β L A + 1 , ⋯ , β L ) , with LA the length of the A sequence .', 'This score can be computed for a pair AB that is a member of the CA used to estimate the PMI of each residue pair at each site , but also for any other pair AB comprised of the sequences of members of the protein families A and B . Next , consider a candidate assignment X of M′ pairs AB , where each protein A is paired with a protein B from the same species , resulting in a CA of M′ sequences of length L = LA + LB .', 'Again , the pairs in this CA can involve the proteins in the CA of M pairs used to estimate the PMIs , with the same assignment or a different one , or any other pair AB comprised of the sequences of members of the protein families A and B . We define the overall pairing score SX of the assignment X by the average of all pairing scores ( see Eq 3 ) of the pairs involved:', 'SX=1M′∑AB∈XSAB=1M′∑i=1LA∑j=LA+1L∑AB∈XPMIij ( αi , βj ) =1M′∑i=1LA∑j=LA+1L∑α , β∑AB∈Xαi=α , βj=βPMIij ( α , β ) =∑i=1LA∑j=LA+1L∑α , βfij′ ( α , β ) PMIij ( α , β ) , ( 4 )', 'where f i j ′ ( α , β ) denotes the joint empirical frequency of amino acid state α at site i and amino acid state β at site j in X . It corresponds to the number of concatenated sequences in X featuring both amino acid state α at site i and amino acid state β at site j , divided by M′ .', 'In the limit of large alignments , the empirical frequencies tend toward probabilities .', 'Besides , if the scored CA is the same as the one used to calculate the PMIs , all frequencies will be the same for both of them ( i . e . f i j ′ ( α , β ) = f i j ( α , β ) ) .', 'For different CA of proteins from the same families A and B , in the case of an assignment consistent with the CA used to estimate the PMIs , the limiting two-body probabilities will be the same in the two CA .', 'Hence , in these cases , combining Eqs 2 and 4 yields', 'SX→M→∞M′→∞∑i=1LA∑j=LA+1LMIij .', '( 5 ) For large alignments , maximizing SX thus corresponds to maximizing the sum of the MIs of inter-protein site pairs , which is itself a pairwise approximation of the MI between the sequences of two protein families A and B . A brute-force self-consistent maximization of SX over all possible assignments X of a realistic dataset would result in a combinatorial explosion , since all allowed permutations of pairs would need to be considered , and PMIs would need to be computed for each of them .', 'In practice , since biologically meaningful pairings have to be made within a species , this means that we would need to consider all combinations of all permutations within each species , which already yields prohibitively large numbers of assignments to test .', 'Hence , we propose an algorithm to perform an approximate maximization of SX .', 'In order to approximately maximize mutual information via the score SX ( see Eq 4 ) , we propose an iterative pairing algorithm ( referred to as MI-IPA ) inspired by that of [21] ( referred to as DCA-IPA ) , where the effective interaction energy from a global statistical model was approximately maximized .', 'In each iteration , we first estimate PMIs for all inter-protein residue pairs from a concatenated alignment ( CA ) of paired sequences .', 'The initial CA , used at the first iteration , is either built from a training set of known correct protein pairs , or made from random pairs , assuming no prior knowledge of interacting pairs .', 'We calculate the pairing scores SAB ( see Eq 3 ) for every possible protein pair AB within each species , by summing the inter-protein PMIs .', 'Next , within each species , we assign pairs by maximizing the sum of SAB scores in the species ( assuming one-to-one specific interactions ) , thereby maximizing SX ( see Eq 4 ) over biologically relevant pair assignments , where each protein has a partner within its species .', 'We attribute a confidence score to each predicted pair , by using the difference of scores between the optimal assignment of pairs in the species and the best alternative assignment that does not involve this predicted pair .', 'The CA is then updated by including the highest-scoring protein pairs , and the next iteration can begin .', 'At each iteration , all pairs in the CA are re-selected based on confidence scores ( except the initial training pairs , if any ) , allowing for error correction .', 'More details on each step of the MI-IPA are given in Methods .', 'As in [21] , we use histidine kinases ( HKs ) and response regulators ( RRs ) from prokaryotic two-component signaling systems as our main benchmark .', 'Two-component systems are important pathways that enable bacteria to sense and respond to environment signals .', 'Typically , a transmembrane HK senses a signal , autophosphorylates , and transfers its phosphate group to its cognate RR , which in turn induces a cellular response [33] .', 'Importantly , most cognate HK-RR pairs are encoded in the same operon , so actual interaction partners are known , which enables us to assess performance .', 'Unless otherwise specified , our results were obtained on a “standard dataset” comprising 5064 HK-RR pairs for which the correct pairings are known from gene adjacency .', 'Each species has on average 〈mp〉 = 11 . 0 pairs , and at least two pairs ( see Methods ) .', 'We start by predicting interaction partners starting from a training set of known pairs .', 'As our training set , we pick a random set of Nstart known HK-RR pairs from the standard dataset .', 'The first iteration of the MI-IPA uses this concatenated alignment ( CA ) to compute PMIs and score possible pairs .', 'We blind the pairings of the remaining dataset , and use it as a testing set on which we predict pairings .', 'At each subsequent iteration n > 1 , the CA used to recompute PMIs contains the initial training pairs plus the ( n − 1 ) Nincrement highest-scoring predicted pairs from the previous iteration ( see Methods ) .', 'As in the case of the DCA-IPA [21] , iterating , and thereby progressively adding high-scoring pairs to the CA , allows us to increase the fraction of pairs that are correctly predicted .', 'This gradual improvement of the TP fraction during the iterations of the MI-IPA is shown in Fig 1A for different training set sizes Nstart .', 'The increase of TP fraction is especially spectacular for small training sets .', 'Fig 1B shows the initial TP fraction , obtained at the first iteration , and the final TP fraction , obtained at the last iteration , versus the size of the training set Nstart , both for the MI-IPA and for the DCA-IPA [21] .', 'In both cases , comparing the initial and final TP fractions demonstrates the major interest of our iterative approach , through the massive increase in TP fraction , especially for small training sets .', 'Moreover , the final TP fraction depends only weakly on Nstart: the iterative approach removes the need for large training sets .', 'Both algorithms yield very good performance , and the MI-IPA even outperforms the DCA-IPA in the trickiest case of small training sets .', 'In this limit ( Nstart = 1 ) , the MI-IPA yields 86% true positive ( TP ) pairs while the DCA-IPA yields 84% TP , while both start from 12% TP at the first iteration .', 'These final TP fractions are strikingly higher than the random expectation of 9% , while such small training sets contain very little information about pairings , as illustrated by the associated low initial TP fraction .', 'Since the MI-IPA to the DCA-IPA yield similar performance , we asked whether they tend to predict the same correct pairs when starting from the same training set .', 'To assess this , consider a species with m AB pairs , and denote by p ( resp . q ) the number of pairs correctly assigned by the MI-IPA ( resp . by the DCA-IPA ) in this species .', 'If the two algorithms made independent predictions , it would correspond to independently and randomly drawing p ( resp . q ) proteins A among m , to be correctly paired .', 'In this null model , the number of possible MI-IPA assignments that share k correct pairs with the DCA-IPA is ( q k ) ( m - q p - k ) : k correct pairs are chosen among the q pairs correctly assigned by the DCA-IPA , and the other p − k ones are chosen among the m − q proteins A incorrectly paired by the DCA-IPA .', 'Besides , the total number of possible MI-IPA assignments with p correct pairs is ( pm ) .', 'Hence , the probability P ( p , k , m , q ) that k correct pairs are predicted by both algorithms is given by the hypergeometric distribution:', 'P ( p , k , m , q ) = ( kq ) ( p−km−q ) ( pm ) .', '( 6 )', 'The expectation of k under this distribution is given by', '⟨ k ⟩ = p q m .', '( 7 )', 'Hence , in this fully independent null model , the expectation of the total number of correct pairs predicted by both algorithms can be obtained by summing the expectations in Eq 7 over all species in the dataset .', 'Moreover , in each species , the observed number kobs of shared correct pairs can be compared to this null model , as well as to the extreme case where all correct pairs that can be shared are shared , yielding min ( p , q ) shared pairs .', 'Hence , we define the relative excess E of shared predictions by', 'E = ∑ i = 1 S k obs , i - ⟨ k i ⟩ ∑ i = 1 S min ( p i , q i ) - ⟨ k i ⟩ , ( 8 )', 'where the index i corresponds to a particular species , the sums run over the S species present in the dataset , and the expectations are given by Eq 7 .', 'If E > 0 , the two algorithms tend to predict the same pairs more frequently than if their predictions were fully independent .', 'In addition , the maximal value E can take is 1 , including the case where predictions from both algorithms are exactly the same .', 'We calculated the average value of E across 50 replicates where both algorithms were started from the same training set , for various Nstart values , in the same conditions as in Fig 1 .', 'As expected , we found that E increases with Nstart , as the algorithms share more information to begin with .', 'However , E depends rather weakly on the size Nstart of the training set , varying smoothly from 53% for Nstart = 1 to 68% for Nstart = 2000 .', 'This indicates a significant tendency of the two algorithms to make the same correct predictions , even in the case of small training sets .', 'In [21] , we showed that the DCA-IPA yields very good identification of interacting pairs without any training set , i . e . without any prior knowledge of interacting pairs .', 'Given this previous result , and given the success of the MI-IPA with very small training sets , we ask whether the MI-IPA also makes good predictions in the absence of a training set .', 'To test this , we followed the approach introduced in [21] by randomly pairing each HK with an RR from the same species , and using these 5064 random pairs to train the initial model .', 'At each subsequent iteration n > 1 , the CA only contained the ( n − 1 ) Nincrement highest-scoring pairs from the previous iteration ( see Methods ) .', 'Fig 2A shows the final TP fraction obtained for different values of Nincrement , both for the MI-IPA and for the DCA-IPA .', 'In both cases , the iterative method performs best for small increment steps , which highlights again the interest of the iterative approach .', 'Importantly , the MI-IPA performs better than the DCA-IPA for all values of Nincrement , and requires substantially less small increments than the DCA-IPA to reach the same performance .', 'The low–Nincrement limit of the final TP fraction is 0 . 87 for the MI-IPA , versus 0 . 84 for the DCA-IPA .', 'These values are consistent with those obtained above with a single training pair , Nstart = 1 ( Fig 1A ) .', 'We emphasize that the striking TP fraction of 0 . 87 is attained by the MI-IPA without any prior knowledge of HK-RR interactions .', 'Ref .', '[21] showed that an important ingredient for the DCA-IPA to bootstrap its way toward high predictive power is that sequence similarity is favored at early iterations , which increases the TP fraction in the CA , because correct pairs have more neighbors in terms of Hamming distance than incorrect pairs .', 'In [21] , this was called the Anna Karenina effect , in reference to the first sentence of Tolstoy’s novel .', 'The same explanation holds for the success of the MI-IPA starting from no training set .', 'In addition , both with MI and with DCA , when starting from random pairings , signal from actual partners should add constructively , while noise should add incoherently .', 'To confirm that the predictive power arises from correlations and similarities in the data , we ran the MI-IPA on a version of our standard alignment of HK-RR sequences where amino acids at each site ( each column ) are randomly scrambled , thus removing correlations ( shown in green in Fig 1A ) .', 'As expected , performance is then the same as for random within-species pairings ( dashed line in Fig 1A ) .', 'In S1 Fig , panel A , we investigated the performance of other variants of the IPA in the same conditions as in Fig 2A .', 'Instead of PMIs , we explored the possibilities of using normalized PMIs ( NPMIs ) , NPMIij ( α , β ) = −PMIij ( α , β ) /log ( fij ( α , β ) ) [32] and covariances , Cij ( α , β ) = fij ( α , β ) − fi ( α ) fj ( β ) ( recall that in the mean-field approximation , DCA employs the inverse of this covariance matrix ) .', 'For small Nincrement values , we find that NPMIs perform similarly as PMIs , while covariances do significantly worse than both PMIs and DCA scores .', 'An important parameter for the performance of the MI-IPA is dataset size .', 'Qualitatively , larger datasets imply more close neighbors , which is favorable to the success of bootstrapping , and they also allow one to estimate MI more accurately , so we expect the MI-IPA to perform best for large datasets .', 'Indeed , Fig 2B shows that the performance of the MI-IPA increases with dataset size .', 'Moreover , the rise of performance occurs for slightly smaller datasets in the case of the MI-IPA than for the DCA-IPA .', 'With DCA , a sufficiently large dataset is necessary to properly infer the pairwise maximum-entropy based global statistical model at the heart of the method [4 , 6 , 12] .', 'While being data-thirsty too , the MI-IPA bypasses this particular need , and thus , it is better suited for partner prediction in smaller datasets .', 'For the complete dataset ( 23 , 424 HK-RR pairs , see Methods ) , both methods reach the same striking final TP fraction of 0 . 93 .', 'The fact that the MI-IPA often performs better than the DCA-IPA for predicting interacting partners stands in contrast with the fact that DCA substantially outperforms MI for residue contact prediction , and suggests that relevant covariation information is contained in pairs of residues that are not in contact .', 'In order to test this , we ran the MI-IPA starting from random initial pairings on our standard HK-RR dataset , but suppressing all MI contributions from the contacting pairs of residues ( defined with a generous 8Å threshold on the minimum distance between amino acids ) .', 'For Nincrement = 6 , a striking TP fraction of 0 . 83 was obtained .', 'This value is only slightly smaller than the 0 . 87 TP fraction obtained when all residue pairs are included , thus confirming that substantial MI relevant for partnership prediction is present in non-contacting residue pairs .', 'As above , we investigated the extent to which the MI-IPA and the DCA-IPA tend to make the same correct predictions .', 'Note that this time , the two algorithms do not start from shared information since there is no training set .', 'For the standard dataset of 5064 HK-RR pairs , with Nincrement = 6 , we found that the average excess shared fraction ( see Eq 7 ) of correct pairs between the two algorithms is E = 53% , i . e . the same as the value obtained in the limit of a very small shared training set , Nstart = 1 ( see above ) .', 'Recall that this positive value means that the two algorithms tend to make the same correct predictions .', 'Moreover , the bias is 53% of the maximal value it could take .', 'It is interesting to compare this result to the bias toward shared correct predictions across different replicates of the same algorithm .', 'We obtained E = 73% for the DCA-IPA , and E = 94% for the MI-IPA , meaning that predictions from the two different algorithms are less similar than those made by the same algorithm .', 'Since the two algorithms do make some different correct predictions , we next asked whether this can exploited , with the intuition that pairs that are predicted both by the MI score and by the DCA score will tend to be correct more often than other pairs .', 'First , we considered using both scores within the IPA .', 'We tried a combined IPA which calculates both scores at each iteration and computes separately the two corresponding pair assignments .', 'Our ranking of pairs puts first the pairs contained in both assignments , and these pairs are ordered by decreasing MI-based confidence scores .', 'Next come the other pairs: the assignment predicted using MI is conserved for them , and they are ordered by decreasing MI-based confidence scores .', 'This means that the pairs consistently predicted by both methods are going to enter the CA earlier in the iterative process than those that differ .', 'A very minor improvement was obtained over the MI-IPA using this method ( see S1 Fig , panel B ) .', 'Since DCA typically requires large datasets to be reliable , we also tried combining MI and DCA by using MI at early iterations , when the CA is small , and switching to DCA at later iterations .', 'No improvement over the MI-IPA was obtained using this method ( see S1 Fig , panel B ) .', 'Next , we tried combining final results from the DCA-IPA and the MI-IPA .', 'In [21] , we showed that multiple different random initializations of the DCA-IPA can be exploited to increase the TP fraction .', 'Specifically , when ranking all possible HK-RR pairs by the fraction of replicates of the MI-IPA in which they are predicted ( “replication fraction” ) , in decreasing order , we found a TP fraction of 0 . 89 among the M best-ranked pairs , a significant improvement over the 0 . 84 average of TP fractions obtained in individual replicates .', '( Here , Nincrement = 6 is used . Recall that M = 5064 is the total umber of pairs in the CA of HK-RRs , see Methods , and thus the number of predicted pairs in each individual replicate of the algorithm . )', 'Applying the same strategy to the MI-IPA also yields a TP fraction of 0 . 89 , higher than that obtained from individual replicates , 0 . 87 .', 'In both cases , 500 replicates of the algorithms , differing only by their initial random within-species pairings , were used to estimate replication fractions .', 'Among the M top pairs thus predicted by the two separate methods , 87% were common , and the TP fraction among those common pairs was 0 . 97 .', 'We also combined the results from the 500 replicates of the DCA-IPA and the 500 replicates of the MI-IPA , and ranked pairs using their overall replication fraction .', 'Then the TP fraction among the M best-ranked pairs is 0 . 91 .', 'Hence , combining final predictions from both methods yields a further improvement of performance .', 'The MI-IPA approximately maximizes MI between the sequence alignments of two protein families A and B . However , there is not guarantee that it will find the assignment with highest MI .', 'In addition , the score we maximize converges toward the sum of MIs of all inter-protein residue pairs ( henceforth called “pairwise MI” ) only in the limit of large alignments and assignments consistent with the CA used to estimate the PMIs ( see Eq 5 ) .', 'In practice , how well does the MI-IPA approach the goal of maximizing pairwise MI ?', 'In order to answer this question , we now compare the pairwise MI of the pairs assigned by the MI-IPA to that of the actual protein pairs , and to the pairwise MI of the random within-species assignment which is used to initialize the MI-IPA in the absence of a training set .', 'Fig 3A shows these three quantities as a function of dataset size M , for HK-RR datasets to which the MI-IPA is applied starting from no training set , as in Fig 2B .', 'We observe a global trend of all computed pairwise MIs to decrease when M is increased .', 'This arises from a well-known finite size effect that occurs when estimating entropies from real datasets [34] , and thus affects entropy-derived quantities such as MIs .', 'To illustrate this point , Fig 3A also shows the pairwise MI of HK-RR datasets where each column of the alignment is randomly scrambled , thus destroying actual correlations while retaining finite-size noise , as well as one-body frequencies .', 'This null model features a similar decreasing trend as the other curves , thus demonstrating that this trend comes from finite-size effects .', 'Note also that the scrambled alignment features pairwise MI values close to those of the initial random assignment , which makes sense because in both cases inter-protein residue pairs are decorrelated by the scrambling .', 'The slightly higher MI of the initial random assignment arises from the fact that random partners are chosen within each species in this case , while complete columns are scrambled in the null model .', 'Apart from the downward trend , a striking observation from Fig 3A is that the pairwise MIs of the assignments predicted by the MI-IPA are significantly higher than those of the initial random assignments , and close to those of the actual protein pairs .', 'Fig 3B highlights these points by considering the excess pairwise MI in the actual protein pairs versus the initial and final assignments in the MI-IPA .', 'Interestingly , even for small datasets , where the MI-IPA yields small TP fractions ( see Fig 2B ) , the pairwise MI of the assignment predicted by the MI-IPA is much closer to that of the actual assignment than to that of the initial random assignment .', 'This suggests that the MI-IPA does a good job at maximizing pairwise MI , even though it does not reach the absolute maximum .', 'So far , we have used naive estimates of the pairwise MI , employing empirical frequencies instead of probabilities in MI ( see Eq 2 ) , without correcting for the finite-size effect discussed above and visible in Fig 3A .', 'Various approaches have been proposed in order to correct for the systematic error due to finite-size effects in entropy ( and thus MI ) estimates .', 'One can use the fact that these finite-size effects have a leading-order contribution of the form MI ^ - MI ∝ K / M , where MI is the actual value of the mutual information and MI ^ is its naive estimate using empirical frequencies , while K is the number of independent values that can be taken by the pair of random variables considered , and M represents dataset size [34] .', 'Estimates MI ^ obtained by subsampling the initial dataset can be linearly ( or polynomially , to include higher-order corrections ) fitted versus 1/M , yielding the actual MI as the intercept .', 'However , if M is not larger than K , subleading corrections become too important , and this method becomes inaccurate .', 'Here , K can go up to the square of the number of possible states per site , i . e . ∼400 .', 'Consistently , we found that polynomial fits become poor when considering datasets with less than ∼1000 sequences .', 'S2A Fig presents results obtained using corrections from these fits , for datasets of at least 1000 sequences .', 'A more sophisticated method to reliably estimating the entropies of discrete distributions was introduced in [35] .', 'It employs a Bayesian approach and a flat prior on the entropy , and results in a correction of finite-size bias in entropy estimates .', 'This NSB ( Nemenman-Shafee-Bialek ) correction is successful in undersampled cases [35 , 36] .', 'In S2B Fig , we show results obtained on our datasets using the NSB correction .', 'Employing either of these two corrections of finite-size effects on the MI estimates ( see S2 Fig ) confirms our previous conclusion .', 'For all dataset sizes , the pairwise MI of the assignment predicted by the MI-IPA is significantly closer to that of the actual assignment than to that of the initial random assignment , thus confirming that the MI-IPA yields results with near-maximal pairwise MI .', 'To demonstrate the generality of the MI-IPA , we applied it to several pairs of protein families [16] , beyond HK-RRs .', 'First , we considered several protein pairs involved in ABC transporter complexes , which permit the translocation of different substances across cell membranes [37] .', 'We built alignments of homologs of the Escherichia coli interacting protein pairs MALG-MALK , FBPB-FBPC , and GSIC-GSID , all involved in ABC transporter complexes , using the same method as in [21] ( see Methods ) .', 'As in the case of HK-RRs , for each of these pairs of protein families , we worked on subsets of ∼5000 protein pairs from species containing at least two pairs .', 'In addition , we considered smaller families of proteins , yielding ∼2000 pairs .', 'More specifically , we chose two pairs of proteins involved in enzymatic complexes: PAAH-PAAJ is a pair of proteins involved in the fatty acid β-oxidation multienzyme complex [38] , and XDHC-XDHA is a pair of proteins involved in the xanthine dehydrogenase complex [39] .', 'Fig 4 shows the performance of the MI-IPA and of the DCA-IPA for these protein pairs , starting from no initial training set , for various values of Nincrement .', 'In all cases , we find that both methods perform very well for small Nincrement , but that higher performances are reached by the MI-IPA , particularly at larger Nincrement values .', 'This is consistent with the results obtained with HK-RRs ( see Fig 2A ) .', 'Note that here , compared to HK-RRs , larger Nincrement values suffice to obtain good performance .', 'This is due to the fact that the pairing tasks are easier here , since the average number of proteins pairs per species is smaller ( see Fig 4 , to be compared to 〈mp〉 = 11 . 0 for HK-RRs ) .', 'These accurate predictions demonstrate the broad applicability of the MI-IPA .', 'Note that HK-RRs interact transiently , while the ABC transporter and enzymatic proteins we considered form permanent complexes , which highlights the generality of the method .', 'As with the DCA-IPA [21] , an important potential application of the MI-IPA is to predict new protein-protein interactions between two protein families .', 'A signature of interactions based on exploiting multiple different random initializations of the algorithm was introduced in [21] , and can be applied to the MI-IPA .', 'Br
['Introduction', 'Results', 'Discussion', 'Methods']
['Functional protein-protein interactions are crucial in most cellular processes .', 'They enable multi-protein complexes to assemble and to remain stable , and they allow signal transduction in various pathways .', 'Functional interactions between proteins result in coevolution between the interacting partners , and thus in correlations between their sequences .', 'Pairwise maximum-entropy based models have enabled successful inference of pairs of amino-acid residues that are in contact in the three-dimensional structure of multi-protein complexes , starting from the correlations in the sequence data of known interaction partners .', 'Recently , algorithms inspired by these methods have been developed to identify which proteins are functional interaction partners among the paralogous proteins of two families , starting from sequence data alone .', 'Here , we demonstrate that a slightly higher performance for partner identification can be reached by an approximate maximization of the mutual information between the sequence alignments of the two protein families .', 'Our mutual information-based method also provides signatures of the existence of interactions between protein families .', 'These results stand in contrast with structure prediction of proteins and of multi-protein complexes from sequence data , where pairwise maximum-entropy based global statistical models substantially improve performance compared to mutual information .', 'Our findings entail that the statistical dependences allowing interaction partner prediction from sequence data are not restricted to the residue pairs that are in direct contact at the interface between the partner proteins .']
['Functional protein-protein interactions are at the heart of most intra-cellular processes .', 'Mapping these interactions is thus crucial to a systems-level understanding of cells , and has broad applications to areas such as drug targeting .', 'Systematic experimental identification of protein interaction partners is still challenging .', 'However , a large and rapidly growing amount of sequence data is now available .', 'Recently , algorithms have been proposed to identify which proteins interact from their sequences alone , thanks to the co-variation of the sequences of interacting proteins .', 'These algorithms build upon inference methods that have been used with success to predict the three-dimensional structures of proteins and multi-protein complexes , and their focus is on the amino-acid residues that are in direct contact .', 'Here , we propose a simpler method to identify which proteins interact among the paralogous proteins of two families , starting from their sequences alone .', 'Our method relies on an approximate maximization of mutual information between the sequences of the two families , without specifically emphasizing the contacting residue pairs .', 'We demonstrate that this method slightly outperforms the earlier one .', 'This result highlights that partner prediction does not only rely on the identities and interactions of directly contacting amino-acids .']
['protein interactions', 'statistics', 'applied mathematics', 'split-decomposition method', 'simulation and modeling', 'algorithms', 'multiple alignment calculation', 'mathematics', 'protein structure prediction', 'protein structure', 'research and analysis methods', 'sequence analysis', 'protein-protein interactions', 'sequence alignment', 'bioinformatics', 'proteins', 'molecular biology', 'protein structure comparison', 'biochemistry', 'statistical models', 'computational techniques', 'database and informatics methods', 'biology and life sciences', 'physical sciences', 'macromolecular structure analysis']