SANA: simulated annealing far outperforms many other search algorithms for biological network alignment

Vol. 00 no. 00 2015 Pages 1–9 BIOINFORMATICS SANA: Simulated Annealing far outperforms many other search algorithms for biological network alignment Nil Mamano and Wayne B. Hayes ∗ Department of Computer Science, University of California, Irvine CA 92697-3435, USA Received on XXXXX; revised on XXXXX; accepted on XXXXX Associate Editor: XXXXXXX ABSTRACT Every alignment algorithm consists of two orthogonal components: an objective function M measuring the quality an alignment, and a search algorithm that explores the space of alignments looking for ones scoring well according to M . We introduce a new search algorithm called SANA (Simulated Annealing Network Aligner) and apply it to protein-protein interaction networks using S 3 as the the topological measure. Compared against 12 recent algorithms, SANA produces 5–10 times as many correct node mappings as the others when the correct answer is known. We expose an anti-correlation in many existing aligners between their ability to produce good topological vs. functional similarity scores, whereas SANA usually outscores other methods in both measures. If given the perfect objective function encoding the identity mapping, SANA quickly converges to the perfect solution while many other algorithms falter. We observe that when aligning networks with a known mapping and optimizing only S 3 , SANA creates alignments that are not perfect and yet whose S 3 scores match that of the perfect alignment. We call this phenomenon saturation of the topological score. Saturation implies that a measure’s correlation with alignment correctness falters before the perfect alignment is reached. This, combined with SANA’s ability to produce the perfect alignment if given the perfect objective function, suggests that better objective functions may lead to dramatically better alignments. We conclude that future work should focus on finding better objective functions, and offer SANA as the search algorithm of choice. Software available at http://sana.ics.uci.edu. Contact: whayes@uci.edu INTRODUCTION Context Network alignment is the task of finding the best way to “fit” one network inside another. It has applications in several areas, including ontology matching (Li et al., 2009), pattern recognition (Zaslavskiy et al., 2009), language processing (Bayati et al., 2009), and social networks (Zhang and Tang, 2013). Thus, the specific goal of network alignment depends on the context. We focus on a particular application from the computational biology domain: the alignment of protein-protein interaction (PPI) networks. In a PPI network, nodes represent proteins from a given organism, and edges connect proteins that interact physically. These kinds of interactions ∗ to are discovered through high throughput experimental methods such as yeast two-hybrid screening (Ito et al., 2000) or protein complex purification via mass-spectrometry (Krogan et al., 2006). PPI network alignment has many interesting applications. It can serve to transfer functional information across species (Kuchaiev et al., 2010), which, in turn, has been used to offer insights on the mechanisms of human diseases (Uetz et al., 2006), or the process of aging in humans (Milenkovi´c et al., 2013). Network alignment can be classified as local or global. The former aims to align small regions accurately (Kelley et al., 2004). Consequently, it often fails to find large conserved connected subgraphs in different networks. By contrast, global network alignment aims to generate one-to-one node mappings between two networks. By aligning entire networks, it overcomes the shortcomings of local network alignment. For this reason, the majority of recent research has focused on global network alignment (see section 1.2). There are also methods that allow alignments between more than two networks (Liao et al., 2009; Hu et al., 2014; Gligorijevi´c et al., 2015; Vijayan and Milenkovic, 2016; Alkan and Erten, 2014). We focus on pairwise, one-to-one global network alignment. Its goal is to find a injective mapping from the proteins of the smaller network to proteins in the larger network. Ideally, we would like to find the most biologically relevant mapping: aligned proteins in both networks should be functionally and/or homologically related, in the sense that they used to be the same protein in the species which was the common ancestor of the species of both PPI networks. Since proteins may have multiple descendants, such a mapping may not be one-to-one. For now we ignore this complication and view global pairwise 1-to-1 network alignment as a convenient approximation, as do almost all of the algorithms we compare against (Table 1). whom correspondence should be addressed c Oxford University Press 2015. Previous work Current PPI network alignment methods use a combination of sequence and topological information to align similar proteins. Biological information includes a priori knowledge about the proteins, such as amino acid sequences. On the other hand, topological information is extracted exclusively from the structure of the PPI network. Since the goal is to obtain biologically relevant alignments, early methods focused on biological information (usually sequence). However, as our understanding of topology- function relationships (Kuchaiev et al., 2010; Davis et al., 2015) has improved, topology information has gradually shifted to a central role. For instance, it has been shown recently that topological