Author summaryWhen two protein families interact, their sequences feature statistical dependencies. First, interacting proteins tend to share a common evolutionary history. Second, maintaining structure and interactions through the course of evolution yields coevolution, detectable via correlations in the amino-acid usage at contacting sites. Both signals can be used to computationally predict which proteins are specific interaction partners among the paralogs of two interacting protein families, starting just from their sequences. We show that combining them improves the performance of interaction partner inference, especially when the average number of potential partners is large and when the total data set size is modest. The resulting paired multiple-sequence alignments might be used as input to machine-learning algorithms to improve protein-complex structure prediction, as well as to understand interaction specificity in signaling pathways.

Predicting protein-protein interactions from sequences is an important goal of computational biology. Various sources of information can be used to this end. Starting from the sequences of two interacting protein families, one can use phylogeny or residue coevolution to infer which paralogs are specific interaction partners within each species. We show that these two signals can be combined to improve the performance of the inference of interaction partners among paralogs. For this, we first align the sequence-similarity graphs of the two families through simulated annealing, yielding a robust partial pairing. We next use this partial pairing to seed a coevolution-based iterative pairing algorithm. This combined method improves performance over either separate method. The improvement obtained is striking in the difficult cases where the average number of paralogs per species is large or where the total number of sequences is modest.