AligNet: alignment of protein-protein interaction networks

Abstract

Background: All molecular functions and biological processes are carried out by groups of proteins that interact with each other. Metaproteomic data continuously generates new proteins whose molecular functions and relations must be discovered. A widely accepted structure to model functional relations between proteins are protein-protein interaction networks (PPIN), and their analysis and alignment has become a key ingredient in the study and prediction of protein-protein interactions, protein function, and evolutionary conserved assembly pathways of protein complexes. Several PPIN aligners have been proposed, but attaining the right balance between network topology and biological information is one of the most difficult and key points in the design of any PPIN alignment algorithm.

Results: Motivated by the challenge of well-balanced and efficient algorithms, we have designed and implemented AligNet, a parameter-free pairwise PPIN alignment algorithm aimed at bridging the gap between topologically efficient and biologically meaningful matchings. A comparison of the results obtained with AligNet and with the best aligners shows that AligNet achieves indeed a good balance between topological and biological matching.

Conclusion: In this paper we present AligNet, a new pairwise global PPIN aligner that produces biologically meaningful alignments, by achieving a good balance between structural matching and protein function conservation, and more efficient computations than state-of-the-art tools.

Keywords: Functional consistency; Global alignment; Network matching; Protein-protein interaction network.

Fig. 1

Pipeline of AligNet algorithm

Fig. 2

a A subnetwork of the Drosophila melanogaster PPI network. b A subnetwork of the Homo Sapiens PPI network

Fig. 3

Overlapping clusterings. This figure shows the overlapping clustering on the PPINs in Fig. 2 obtained by AligNet. We can see here the 8 clusters in the network in Fig. 2 on the left, and the 9 clusters in the network in Fig. 2 on the right. The center of every cluster is highlighted in blue. Since we have considered two small pieces of a PPIN, we obtain here that, the first cluster on the left is the entire piece of network. In the right, we obtain also the entire piece of network in the second cluster on the right. Notice that we obtain the whole piece of the network when we consider the cluster of a node that is in the center of the network

Fig. 4

Alignment of a pair of clusters. This figure shows how AligNet aligns two clusters which corresponds to Step 2 of our algorithm. The clusters in this example are, respectively, the first in the list of clusters of G, which are shown on the left in Fig. 3 and the seventh in the list of clusters of G^′, which are shown on the right in Fig. 3. We show in the picture all the steps needed to align the cluster of G with the cluster of G^′. From top to bottom in this figure, we can see that AligNet first aligns the centers of the clusters, which are the nodes highlighted in blue. Then, AligNet aligns the neighbors of the centers (second row). Next, AligNet aligns the neighbors of the neighbors. In each step we show in a different colour the nodes that are aligned in the present step. Notice that, in this example, there are two nodes that remain unmatched

Fig. 5

Alignment of the clusterings. This figure shows the final assignment (same colour) between the clusters in Fig. 3 produced by AligNet, which corresponds also to Step 3. Each of the eight clusters obtained from G is aligned to one, and only one, of the nine clusters obtained from G^′. Hence, one cluster from G^′ remains unmatched which is the second cluster in the third row on the right in Fig. 3. In this figure, we show the clusters from G on the left and its corresponding cluster image from G^′ on the right

Fig. 6

Appropriate set of alignments. This figure shows how AligNet constructs an appropriate set of alignments considered to obtain a final local alignment. This corresponds to the Step 4 of our aligner. First of all, a maximum score alignment between a pair of clusters is chosen: in this case, this corresponds to the matching between the clusters in Fig. 4. Both clusters are shown in the second row of this figure. The shadowed nodes are the nodes that are not aligned. Next, a maximum score alignment of a pair of clusters with source a cluster centered at a shadowed node is chosen: it turns out to be the one in the second row in Fig. 5 and it is shown in the third row in this figure. Finally, the last alignment to be included in the appropriate set of alignments must be the one with source cluster centered at the remaining shadowed node: this corresponds to the alignment in the last row in Fig. 5 shown in the bottom of this figure. Notice that in the end, that is when we consider the three alignments together, there are four nodes in the source network with inconsistent assignments

Fig. 7

Local alignment. This figure shows the local alignment of the original networks obtained by AligNet in its fourth step, once the inconsistent assignments have been solved. The coherent assignment of nodes is obtained as the solution to the weighted bipartite hypergraph assignment problem, for the hypergraph associated to the appropriate set of alignments described in Fig. 6. In this case, the hypergraph has three hyperarcs, corresponding to the three alignments considered in the appropriate set of alignments

Fig. 8

Final global alignment. This figure shows the final global alignment of the original networks obtained by AligNet. Notice that, in the fifth step of AligNet, the previous alignment is extended to a global one. In this case, there were two unmatched nodes in the source network in Fig. 7 which are now assigned

Fig. 9

Edge Correctness Scores. This figure shows the edge correctness score obtained for each aligner in every alignment. The different aligners are presented in different colours

Fig. 10

Functional Coherence Scores. This figure shows the functional coherence score obtained for each aligner in every alignment. In a purple dot we show the maximal value expected for every The different aligners are presented in different colours

Fig. 11

Scores of mus–cel alignments. This figure shows as violin plots the distribution of the EC and FC scores obtained for every aligner in the alignments of the perturbed networks of mus and cel

Fig. 12

Scores of mus–sce alignments. This figure shows as violin plots the distribution of the EC and FC scores obtained for every aligner in the alignments of the perturbed networks of mus and sce

Fig. 13

Scores of mus–dme alignments. This figure shows as violin plots the distribution of the EC and FC scores obtained for every aligner in the alignments of the perturbed networks of mus and dme

Fig. 14

Complex Functional Coherence. This figure shows the number of non-assigned complexes (in blue), the number of coherent pairs (in green), the number of incoherent pairs (in red) and the complex functional coherence value (yellow dot). The number of complexes is shown on the left axis, while the complex functional coherence value is shown on the right axis

Fig. 15

Complex Functional Coherence Precision. This figure shows the number of coherent pairs (green) and incoherent pairs (red) obtained with one aligner versus the other

Fig. 16

Binary Classifier Metrics. This figure shows the results obtained for each aligner in the essential proteins alignment test, for every statistical measure

Fig. 17

Running times. This figure shows the running times (in seconds) we obtained when we performed all the alignments for every pair of the considered networks. In this figure we present the results obtained with the aligners AligNet, PINALOG, SPINAL, HubAlign and L-GRAAL

Fig. 18

Running times cut at 10 minutes. We show in this figure the running times for those alignments that took lees than 10 minutes

Fig. 19

Time Consistency. This figure shows the running times in seconds obtained for every pairwise alignment and every aligner. We ordered the pairwise alignments considering the size (number of nodes) of the networks