## 3 Methods
### Solving Strategies
#### 3.1.3 Overall Method
Similarly to the IsoRank and L-GRAAL parameter \(\alpha\), we introduced a parameter \(\beta\in[0,1]\) such that the sequence part of the score has weight \((1-\beta)\) and the topology part has weight \(\beta\). We sampled the weight parameters uniformly in the range \([0,1]\) for all methods. Figure 3 shows that on the smaller networks Natalie, L-GRAAL and IsoRank identify functionally coherent alignments with similar GO scores. However, Natalie outperforms the other methods on many of the larger networks. Figure 3: Biological relevance of the alignments measured via GO similarity. ## 5 Conclusions

Inspired by results for the closely related quadratic assignment problem (QAP), we have presented new algorithmic ideas in order to make a Lagrangian relaxation approach for global network alignment practically useful and competitive. In particular, we have generalized a dual descent method for the QAP. We have found that combining this scheme with the traditional subgradient optimization method leads to fastest progress of upper and lower bounds. Our implementation of the new method, Natalie 2.0, works well and fast when aligning biological networks, which we have shown in an extensive study on the alignment of cross-species PPI networks. We have compared Natalie 2.0 to the established and new state-of-the-art methods IsoRank, GRAAL and L-GRAAL, which aim at optimizing similar scoring functions. Our experiments show that the Lagrangian relaxation approach is a powerful method, which often outperforms the competitors in terms of quality of the results and running time. Currently, all methods, including Natalie 2.0, approach the global network alignment problem heuristically, that is, the computed alignments are not guaranteed to be optimal solutions of the problem. While some approaches are intrinsically heuristic--both IsoRank and GRAAL, for instance, approximate the neighborhood of a node and then match it with a similar node--the inexactness in Natalie 2.0 and also L-GRAAL has two causes that we plan to address in future work: on the one hand, there may still be a gap between upper and lower bound of the Lagrangian relaxation approach after the last iteration. One could use these bounds in a branch-and-bound approach that will compute provably optimal solutions. On the other hand, we currently do not consider the complete bipartite alignment graph and may therefore miss optimal alignments. Here, preprocessing strategies, in the spirit of [33], which safely sparsify the input bipartite graph without violating optimality conditions, may be useful. The independence of local problems (LD\({}_{\lambda}^{ik}\)) allows for straightforward parallelization, which would lead to an even faster method. Another improvement in running times might be achieved when considering more involved heuristics for computing the lower bound, such as local search. More functionally-coherent alignments can be obtained when considering a scoring function where node-to-node correspondences are not only scored via sequence similarity but also for instance via GO similarity. In certain cases, even negative weights for topological interactions might be desired in which case one needs to reconsider the assumption of entries of matrix \(W\) being positive. ## Acknowledgments

We thank SARA Computing and Networking Services for their support in using the Lisa Compute Cluster. In addition, we are grateful to [PERSON] for helping out with various bioinformatics issues and also to [PERSON] for providing code and advice on the GO similarity experiments. We thank [PERSON] for helping us with running L-GRAAL and for general discussions. We also thank the anonymous referees for carefully reading our work and their comments. ## Author Contributions

[PERSON], [PERSON] and [PERSON] designed the study, interpreted the results and wrote the manuscript. [PERSON] and [PERSON] conceived the method. [PERSON] and [PERSON] implemented the software and ran the experiments. ## Conflicts of Interest

The authors declare no conflict of interest.