Attributes of Synthetic Networks
To validate the proposed network synthesis model, we generated synthetic PPI networks according to the model and analyzed the individual and cross-species characteristics of the synthesized networks. We first generated an ancestral network
. A simple binary tree with two leaves was used to evolve
into two networks
, respectively with 5,000 nodes and 7,000 nodes. For network extension, we applied all three network growth models – DMC, DMR, and CG – discussed in this paper. For DMC, we used
as in 
. For DMR, we set the parameters to
as in 
. We used
for CG as in 
. The scaling and shape parameters of the Gamma distributions in (2) were set to
, and the exponent
in the distribution
was set to
, such that the cross-network properties between
resemble those between the D. melanogaster
PPI network and the S. cerevisiae
PPI network. The parameters
that control the functional inheritance and sequence similarity between orthologous nodes were set to
, so that protein function and sequence similarity is conserved at the
level. Although it is practically difficult to accurately determine these two parameters in real networks, the analysis in 
shows this rate of functional conservation for duplicated genes.
In the case of CG algorithm, we made a slight modification in the first step of the algorithm as follows. In the original algorithm proposed in 
, when adding a new node, the modules of the current network are recomputed at each iteration. To speed up the CG algorithm, we instead redefine the modules every
is the size of the current network. In other words, in the early iterations, we redefine modules in every iteration, while as the network grows larger, we apply the module redefinition step only occasionally and use these modules over multiple iterations. Simulation results show that the CG method can still accurately capture the generic features of real PPI networks with this modification. We leave the module redefinition frequency as a control parameter that can be freely adjusted.
The properties of the synthetic PPI network are shown in , , and , for using DMC, DMR, and CG, respectively. As can be seen in these figures, all three schemes can accurately model the scale-free degree distribution. However, it appears that the hierarchical modularity can be better captured by using either DMC or CG, rather than DMR. Regarding the cross-network properties, these results also clearly show that the proposed network synthesis model can effectively capture the attributes of real PPI networks. For example, this can be immediately seen by comparing the network properties of
in (when using DMC) with those of the D. melanogaster
and the S. cerevisiae
PPI networks shown in . Similar observations can be made from (for DMR) as well as (for CG).
Properties of the networks generated using the DMC model.
Properties of the networks generated using the DMR model.
Properties of the networks generated using the CG model.
Construction of Network Alignment Benchmark
The network synthesis model presented in this paper provides an effective framework for generating network families with diverse characteristics. Such network sets may be used to assess the performance of various alignment techniques to identify their respective strengths and weaknesses under different conditions and problems settings. Furthermore, the proposed network synthesis model may be potentially used to expose previously unknown biases that a network alignment technique may have towards specific types of networks, thereby leading to better alignment techniques.
To demonstrate the utility of the proposed network generation scheme, we used it to create synthetic benchmark datasets that can be used for evaluating and comparing the performance of various network alignment algorithms. We call the proposed N
mark as NAPAbench. In total, we generated three suites of datasets. The first suite (referred as the pairwise alignment
dataset) contains three pairs of networks, where the respective network pairs were generated using DMC, DMR, and CG, respectively. Each pair consists of a network
nodes and another network
nodes, both evolved from an ancestral network
nodes, following a binary tree with two leaves. The second suite (referred as the 5-way alignment
dataset) contains three network families, each with five networks generated using DMC, DMR, or CG. To generate the network family, we first created an ancestral network
nodes. The phylogenetic tree
in was used to evolve
into five networks –
– which correspond to the five leaf nodes. For every branch, we set its length to 500. Thus, the size of the five networks were
. This dataset simulates a family of PPI networks that correspond to distantly related species. Finally, the third suite (referred as the 8-way alignment
dataset) also consists of three network families, each with eight networks generated by one of the three network extension models. The eight networks were obtained by evolving an ancestral network
according to a full binary tree with eight leaf nodes. The branch length was set to 200 for all branches, which gave rise to eight equally sized networks, each with 1,000 nodes. This 8-way alignment dataset tries to simulate a network family of closely-related species. All the datasets in NAPAbench are publicly available at http://www.ece.tamu.edu/bjyoon/NAPAbench/
Performance Analysis of Network Alignment Algorithms
The created benchmark datasets, NAPAbench, can be used for reliable and comprehensive performance evaluation of existing network alignments. In this work, we used this synthetic benchmark to assess the performance of five well-known multiple network alignment algorithms: IsoRank 
, IsoRankN 
, NetworkBLAST-M 
, Græ mlin 2.0 
, and MI-GRAAL 
uses spectral graph theory to evaluate the overall similarity between nodes that belong to different networks. This pairwise alignment score is computed for every node pair across all pairs of networks, which is then used to build the multiple network alignment according to a greedy approach. IsoRankN
further extends the idea in IsoRank by employing a spectral clustering scheme based on the pairwise node alignment scores. NetworkBLAST-M
computes the network alignment by first constructing a layered alignment graph based on the potential orthologous nodes, and then greedily searching for highly conserved local regions in the alignment graph. Græ mlin 2.0
takes a progressive approach to construct a global alignment of multiple networks, where it repeatedly performs pairwise network alignments according to a given phylogenetic tree that describes the relationship among the networks. The alignment is predicted by maximizing an objective function based on parameters that are learned from a set of known alignments. Finally, MI-GRAAL
is a recently proposed pairwise network alignment scheme that can integrate any number and type of similarity measures between network nodes, such as sequence similarity, structural similarity, and topological similarity.
Recall that the node similarity score in the proposed model tries to mimic the BLAST bit scores. Since NetworkBLAST-M and MI-GRAAL employ the BLAST E-values, instead of the BLAST bit scores, we should transform the bit scores into the corresponding E-values for these two algorithms. As discussed in 
, the simulated bit score (
) is related to the E-value (
is the length of the BLAST query and
is the length of the target sequence. Here, we transform our simulated bit scores to E-values using
(assuming, for instance, the case when we BLAST a protein sequence with 500 residues in a database that contains a total of 200,000,000 residues). In this paper, we used the restricted-order version of NetworkBLAST-M as the running time of the relaxed-order version increases exponentially with respect to the number of networks to be aligned. As Græ mlin needs to learn the parameters of its scoring function in advance, we generated a training set that consists of five networks (with
nodes, respectively), using the proposed scheme with the DMC model by following the tree shown in . MI-GRAAL can integrate different kinds of similarity measures into the search process. Here, we adopt the graphlet degree signature distance and the E-values (measuring the sequence similarity) for MI-GRAAL alignment algorithm. For IsoRank and IsoRankN, the parameter
, which determines the balance between sequence similarity and topological similarity, was set to 0.6.
The accuracy of each network alignment algorithm was assessed using four measures – specificity, correct nodes, mean normalized entropy, and coverage – which had been previously used in 
. We refer the set of aligned nodes (i.e., potential orthologs) as the equivalence class
. Each equivalence class may include an arbitrary number of nodes from each species. To compute the accuracy measures, we first removed the unannotated nodes from the alignment (i.e, nodes with the annotation
) and then removed equivalence classes containing only a single node. A given equivalence class is viewed as being correct
if all the included nodes belong to the same FO group. The four measures are defined as follows:
NetworkBLAST-M reports only the local alignment of the input networks, while the other four algorithms yield the global alignment of the given networks. For a fair comparison between these algorithms, we first convert the local alignment predicted by NetworkBLAST-M into a global network alignment by merging all local node correspondences. For example, if nodes
are aligned in one local alignment while
are aligned in another local alignment, we assume that
belong to the same equivalence class.
The SPE, CN, and MNE of the five algorithms are summarized in , , and , for the pairwise alignment dataset, 5-way alignment dataset, and the 8-way alignment dataset, respectively. and shows the coverage of different algorithms for the 5-way and 8-way dataset, respectively.
Performance of different alignment algorithms on the pairwise alignment dataset of NAPAbench.
Performance Comparison on the 5-way network alignment dataset of NAPAbench.
Performance Comparison on 8-way network alignment dataset of NAPAbench.
Number of equivalence classes in the 5-way alignment experiment that contain nodes from
Number of equivalence classes in the 8-way alignment experiment that contain nodes from
For pairwise network alignments, NetworkBLAST-M boasts significantly higher specificity and consistency (reflected in lower MNE) compared to other algorithms. IsoRank, IsoRankN, and MI-GRAAL yielded the highest number of correctly aligned nodes (i.e., CN) for networks generated using the DMC/DMR growth models, implying high sensitivity. For the networks created using the CG model, which yield highly modular networks, NetworkBLAST-M showed highest sensitivity, closely followed by MI-GRAAL.
For the 5-way and 8-way alignment experiments, we can clearly observe the degradation in sensitivity of NetworkBLAST-M, as shown in and . This may be due to the fact that NetworkBLAST-M aims to predict equivalence classes that are conserved across all the compared species, as illustrated in and . In these experiments, Græ mlin showed moderate performance, where the sensitivity was higher than NetworkBLAST-M, but the specificity and the consistency were lower. The multiple network alignment experiments based on the 5-way and the 8-way benchmark datasets in NAPAbench show that IsoRankN can yield the most accurate network alignment results, in terms of specificity, sensitivity, and consistency. This observation is in agreement with the performance assessment in 
, based on five real biological networks.
To compared the performance of different algorithms in predicting equivalence classes conserved across all networks, we also estimated the accuracy of IsoRankN and Græ mlin only for such classes. These results are shown in the last two rows of and . We can see that IsoRankN still outperforms NetworkBLAST-M in most cases for 5-way alignment. In the 8-way network alignment, IsoRankN appears to outperform NetworkBLAST-M for networks generated using the DMC growth model. However, NetworkBLAST-M is more sensitive on networks obtained using the DMR model, and it is also more sensitive and more specific for networks generated using the CG model. These results also show that Græ mlin is outperformed by the other two algorithms in this case, which implies that it may not be effective in predicting orthologous nodes that are conserved across all species.
shows the number of equivalence classes (i.e., the coverage) that are predicted in the 5-way alignment dataset by the respective algorithms. In each case, the total number of equivalence classes is split into the number of classes that consist of nodes from
different networks (
). As shown in this figure, all three algorithms predicted similar number of equivalence classes that contain nodes from all
networks. However, we can see that IsoRankN predicts a significantly larger number of equivalence classes with
compared to the other algorithms. Considering that the 5-way alignment dataset consists of networks with varying size, equivalence classes that contain nodes from
networks are fairly common, hence the ability of identifying such equivalence classes is certainly an important advantage of IsoRankN. shows coverage of different algorithms on the 8-way dataset. The trends are similar as in the 5-way alignment, and we can see that IsoRankN results in greater coverage for equivalence classes spanning
networks. Another interesting observation is that Græ mlin predicts a large number of equivalence classes that contain only nodes from
Next, we investigate the effect of sequence similarity on the performance of the various network alignment algorithms. To this aim, we add a bias term
to the similarity score distribution of potential orthologs in (2), such that the score is randomly sampled as
. Increasing the bias
will further separate the similarity score distributions of orthologous and non-orthologous nodes. As a result, the larger
is, the easier it becomes to align the networks (and to predict the potential orthologs across networks) based on sequence similarity alone, without utilizing the topological similarity between networks. For this experiment, we generated two networks with 1,000 nodes from an ancestral network of size
. shows how specificity (SPE) and CN (which reflects sensitivity), change for varying values of
between 0 and 250. As can be seen in this figure, as the separation between the score distributions of orthologs and non-orthologs increases, both the specificity and the sensitivity are improved for IsoRank, IsoRankN, and Græ mlin. On the other hand, NetworkBLAST-M and MI-GRAAL display a constant level of accuracy that does not depend on the amount of separation. This implies that the first three alignment algorithms rely on the similarity between nodes relatively strongly when predicting the network alignment, while NetworkBLAST-M and MI-GRAAL use the similarity score mainly to predict potential orthology and do not rely too much on the extent of the similarity. In these experiments, Græ mlin appears to most strongly rely on the node similarity among the compared algorithms. In fact, Græ mlin achieves the highest specificity and sensitivity when there is a large separation between the score distributions (e.g.,
), while resulting in the lowest sensitivity when the separation is small (e.g.,
The specificity (SPE) and the CN (which reflects the sensitivity) of different alignment algorithms for varying level of separation between the similarity score distribution for orthologs and the score distribution for non-orthologs.
compares the computational complexity of the five algorithms, in terms of the total CPU time needed to align the networks in the respective datasets. All experiments have been performed on a desktop computer with a 2.2GHz Intel Core2Duo CPU and 4GB memory. It should be noted that Græ mlin requires a training stage for estimating the parameters used by the algorithm, which took more than a day in our experiments. The CPU time shown in reveals that Græ mlin (without considering the training stage) and NetworkBLAST-M are the fastest among the five algorithms, while IsoRankN and MI-GRAAL are computationally more complex than these two algorithms.
Total CPU time (min) for aligning the networks.