## 3 Methods
### Solving Strategies
#### 3.1.3 Overall Method  
Our overall method combines both the subgradient optimization and dual descent method. We do this performing the subgradient method until termination and then switching over to the dual descent method. This procedure is repeated \(K\) times (see Algorithm 3). ```
1\(\lambda\leftarrow\mathbf{0}\); \([\mathrm{LB}^{*},\mathrm{UB}^{*}]\leftarrow[0,\infty]\)
2 for\(k\gets 1\)to\(K\)do
3\([\mathrm{LB}^{*},\mathrm{UB}^{*}]\leftarrow\textsc{SubgradientOpt}(\lambda,M,N) \cap[\mathrm{LB}^{*},\mathrm{UB}^{*}]\)
4\([\mathrm{LB}^{*},\mathrm{UB}^{*}]\leftarrow\textsc{DualDescent}(\lambda,L) \cap[\mathrm{LB}^{*},\mathrm{UB}^{*}]\) return\([\mathrm{LB}^{*},\mathrm{UB}^{*}]\)
```  
**Algorithm 3**Natalie\((K,L,M,N)\)  
```
1\(\lambda\leftarrow\mathbf{0}\); \([\mathrm{LB}^{*},\mathrm{UB}^{*}]\leftarrow[0,\infty]\)
2 for\(k\gets 1\)to\(K\)do
3\([\mathrm{LB}^{*},\mathrm{UB}^{*}]\leftarrow\textsc{SubgradientOpt}(\lambda,M,N) \cap[\mathrm{LB}^{*},\mathrm{UB}^{*}]\)
4\([\mathrm{LB}^{*},\mathrm



We implemented Natalie in C++ using the LEMON graph library [30]. The successive shortest path algorithm for maximum weight bipartite matching was implemented and contributed to LEMON. Special care was taken to deal with the inherent numerical instability of floating point numbers. Our implementation supports both the GraphML and GML graph formats. Rather than using one big alignment graph, we store and use a different alignment graph for every local problem (LD\({}_{\lambda}^{ik}\)). This proved to be a significant improvement in running time, especially when the global alignment graph is sparse. The source code of Natalie is publicly available under the MIT license at [17]. ## 4 Experimental Evaluation

From the STRING database v8.3 [1], we obtained PPI networks for the following six species: _C. elegans_ (cel), _S. cerevisiae_ (see), _D. melanogaster_ (dme), _R. norvegicus_ (rno), _M. musculus_ (mmu) and _H. sapiens_ (hsa). We only considered interactions that were experimentally verified. Table 1 shows the sizes of the networks. We performed, using the BLOSUM62 matrix, an all-against-all global sequence alignment on the protein sequences of all \(\binom{6}{2}=15\) pairs of networks. We used affine gap penalties with a gap-open penalty of 10 and a gap-extension penalty of 2. The first experiment in Section 4.1 compares the performance of IsoRank, GRAAL, L-GRAAL and Natalie 2.0 in terms of a variety of topological measures. In Section 4.2, we evaluate the biological relevance of the alignments produced by the four methods. All experiments were conducted on a compute cluster with 2.26 GHz processors with 24 GB of RAM. ### Topological Measures

A popular evaluation metric for network alignments is edge correctness (EC), which is the number of conserved edges divided by the number of edges of the smaller network. This measure can be directly optimized, for example in Natalie 2.0, by setting the scoring function to \(s(a)=|\{(v,w)\in E_{1}\mid(a(v),a(w))\in E_{2}\}|\). In addition, for Natalie 2.0 and L-GRAAL, we measured the size of the largest aligned connected component (LCC), and the recently proposed measures induced and symmetric substructure score (ICS and S3). ICS takes also matching non-edges into account and is defined as the number of matched edges divided by the number of edges in the subgraph of \(G_{2}\) that is induced by the \begin{table}
\begin{tabular}{l r r r} \hline
**Species** & **Nodes** & **Annotated** & **Interactions** \\ \hline cel (c) & 5948 & 4694 & 23,496 \\ sce (s) & 6018 & 5703 & 131,701 \\ dme (d) & 7433 & 6006 & 26,829 \\ rno (r) & 8002 & 6786 & 32,527 \\ mmu (m) & 9109 & 8060 & 38,414 \\ hsa (h) & 11,512 & 9328 & 67,858 \\ \hline \end{tabular}
\end{table} 
Table 1: Characteristics of input networks considered in this study. The columns contain species identifier, number of nodes in the network, number of nodes annotated with at least one gene ontology (GO) term, and number of interactions. matching.