SMETANA: accurate and scalable algorithm for probabilistic alignment of large-scale biological networks

Abstract

In this paper we introduce an efficient algorithm for alignment of multiple large-scale biological networks. In this scheme, we first compute a probabilistic similarity measure between nodes that belong to different networks using a semi-Markov random walk model. The estimated probabilities are further enhanced by incorporating the local and the cross-species network similarity information through the use of two different types of probabilistic consistency transformations. The transformed alignment probabilities are used to predict the alignment of multiple networks based on a greedy approach. We demonstrate that the proposed algorithm, called SMETANA, outperforms many state-of-the-art network alignment techniques, in terms of computational efficiency, alignment accuracy, and scalability. Our experiments show that SMETANA can easily align tens of genome-scale networks with thousands of nodes on a personal computer without any difficulty. The source code of SMETANA is available upon request. The source code of SMETANA can be downloaded from http://www.ece.tamu.edu/~bjyoon/SMETANA/.

Figure 1. Performance of various network alignment algorithms.

(A) Equivalence class coverage: Number of equivalence classes in the 5-way alignment experiment that contain nodes from species (). (B) Node Coverage: Number of nodes (i.e. proteins) that belong to equivalence classes that contain nodes from species in the 5-way alignment.

Figure 2. Performance of various network alignment algorithms.

(A) Equivalence class coverage: Number of equivalence classes in the 8-way alignment experiment that contain nodes from species (). (B) Node Coverage: Number of nodes (i.e. proteins) that belong to equivalence classes that contain nodes from species in the 8-way alignment.

Figure 3. Number of conserved interactions (CI) and conserved orthologous interactions (COI) for different alignments.

CI reports the total number of conserved edges between any of the equivalence classes in the alignment. COI reports the total number of conserved edges between “correct” equivalence classes that consist of orthologous nodes.

Figure 4. Effects of node similarity on the performance of different network alignment algorithms.

The alignment performance has been estimated at several different levels of separation between the similarity score distribution for orthologous node pairs and that for non-orthologs pairs. Increasing the bias increases the separation between the two score distributions, which increases the discriminative power of the node similarity score for predicting potential orthologs. Measures reported: specificity (SPE), number of correct nodes (CN) (which reflects the sensitivity), mean normalized entropy (MNE), number of conserved interactions (CI), number of conserved orthologous interactions (COI).

Figure 5. Total CPU time for aligning the networks.

The total CPU time for the pairwise, 5-way, and 8-way alignments. CPU time has been averaged over DMC, DMR, and CG datasets (measured in seconds).

Figure 6. Performance on real networks.

The trend of change in sensitivity (SEN) and specificity (SP) as the number of networks in the alignment increases for different multiple network alignment algorithms.

Figure 7. Conserved subnetwork regions in the 3-way alignment of D. melanogaster, H. sapiens, and S. cerevisiae using the proposed method.

(A) Transcription factor. (B) Replication factor C. (C) RNA polymerase. (D) DNA replication. (Aligned nodes are placed in the same row of alignment and connected with yellow dashed lines. In each network, the interaction in the IsoBase dataset is shown in solid lines. For D. melanogaster some edges which are missed in IsoBase but are present in STRING protein interaction database is shown in dotted gray lines).