Topological Network Alignment comes of Age
Topological network alignment is the task of finding best-match, near-isomorphic subgraphs between two or more networks. In biological networks the task is complicated by significant levels of noise in the edges, and by the fact that even in truth there may not be a 1-to-1 mapping between nodes in one network and nodes in another. Since network topology is exponentially complex, even defining what it means to be a “good” topological alignment can be tricky—and thus it can be difficult to define exactly what we’re trying to optimize. Thus it is important that any network alignment tool be capable of optimizing any number of different, prospective measures of network topology that may include edge alignment, graphlet measures, graph spectra, etc., because there is no clear idea on which of these may be most biologically appropriate. SANA (the Simulated Annealing Network Aligner) is able to optimize any objective function, and is faster and produces superior results (near-optimal in all cases checked) than any other existing aligner, according to our results. Here I will present some recent results using SANA to align protein-protein interaction networks and compare SANA’s results to a dozen other recent alignment algorithms.