L-HetNetAligner: A novel algorithm for Local Alignment of Heterogeneous Biological Networks

The use of networks for modelling and analysing relations among data is currently growing. Recently, the use of a single networks for capturing all the aspects of some complex scenarios has shown some limitations. Consequently, it has been proposed to use Dual Networks (DN), a pair of related networks, to analyse complex systems. The two graphs in a DN have the same set of vertices and different edge sets. Common subgraphs among these networks may convey some insights about the modelled scenarios. For instance, the detection of the Top-k Densest Connected subgraphs, i.e. a set k subgraphs having the largest density in the conceptual network which are also connected in the physical network, may reveal set of highly related nodes. After proposing a formalisation of the approach, we propose a heuristic to find a solution, since the problem is computationally hard. A set of experiments on synthetic and real networks is also presented to support our approach.

Networks-based models have been used to represent and analyse datasets in many fields such as computational biology, medical informatics and social networks. Nevertheless, it has been recently shown that, in their standard form, they are unable to capture some aspects of the investigated scenarios. Thus, more complex and enriched models, such as heterogeneous networks or dual networks, have been proposed. We focus on the latter model, which consists of a pair of networks having the same nodes but different edges. In dual networks, one network, called physical, has unweighted edges representing binary associations among nodes. The other is an edge-weighted one where weights represent the strength of the associations among nodes. Dual networks capture in a single model some aspects that cannot be described by using a standard model. Dual networks can be used, for instance, to capture a co-authorships network, where physical network represents co-authors. In contrast, the conceptual network is used to model topics sharing among a couple of authors by means of edge connections. This allows capturing similar interests among authors even though they are not co-authors. We propose an innovative algorithm to find the Densest Connected Subgraph (DCS) in dual networks. DCS is the largest density subgraph in the conceptual network, which is also connected in the physical network. A DCS represents a set of highly similar nodes. Moreover, since DCS is a computationally hard problem, we propose novel heuristics to solve it. We tested the proposed algorithm on social, biological, and co-authorship networks. Results demonstrate that our approach is efficient and is able to extract meaningful information from dual networks. INDEX TERMS DCS, Dual Networks, graph alignment, social networks. Recently, more complex models have also been introduced. The use of a pair of graphs representing two different views of the same scenario has been introduced to detect hidden properties which are not detected by single network-based VOLUME 4, 2016

In this study, we deal with the problem of biological network alignment (NA), which aims to find a node mapping between species' molecular networks that uncovers similar network regions, thus allowing for the transfer of functional knowledge between the aligned nodes. We provide evidence that current NA methods, which assume that topologically similar nodes (i.e., nodes whose network neighborhoods are isomorphic-like) have high functional relatedness, do not actually end up aligning functionally related nodes. That is, we show that the current topological similarity assumption does not hold well. Consequently, we argue that a paradigm shift is needed with how the NA problem is approached. So, we redefine NA as a data-driven framework, called TARA (data-driven NA), which attempts to learn the relationship between topological relatedness and functional relatedness without assuming that topological relatedness corresponds to topological similarity. TARA makes no assumptions about what nodes should be aligned, distinguishing it from existing NA methods. Specifically, TARA trains a classifier to predict whether two nodes from different networks are functionally related based on their network topological patterns (features). We find that TARA is able to make accurate predictions. TARA then takes each pair of nodes that are predicted as related to be part of an alignment. Like traditional NA methods, TARA uses this alignment for the across-species transfer of functional knowledge. TARA as currently implemented uses topological but not protein sequence information for functional knowledge transfer. In this context, we find that TARA outperforms existing state-of-the-art NA methods that also use topological information, WAVE and SANA, and even outperforms or complements a state-of-the-art NA method that uses both topological and sequence information, PrimAlign. Hence, adding sequence information to TARA, which is our future work, is likely to further improve its performance. The software and data are available at