Aligning dynamic networks with DynaWAVE

Current and future directions in network biology

Summary

Network biology is an interdisciplinary field bridging computational and biological sciences that has proved pivotal in advancing the understanding of cellular functions and diseases across biological systems and scales. Although the field has been around for two decades, it remains nascent. It has witnessed rapid evolution, accompanied by emerging challenges. These stem from various factors, notably the growing complexity and volume of data together with the increased diversity of data types describing different tiers of biological organization. We discuss prevailing research directions in network biology, focusing on molecular/cellular networks but also on other biological network types such as biomedical knowledge graphs, patient similarity networks, brain networks, and social/contact networks relevant to disease spread. In more detail, we highlight areas of inference and comparison of biological networks, multimodal data integration and heterogeneous networks, higher-order network analysis, machine learning on networks, and network-based personalized medicine. Following the overview of recent breakthroughs across these five areas, we offer a perspective on future directions of network biology. Additionally, we discuss scientific communities, educational initiatives, and the importance of fostering diversity within the field. This article establishes a roadmap for an immediate and long-term vision for network biology.

Availability and implementation

Not applicable.

Multilayer network alignment based on topological assessment via embeddings

BACKGROUND

Network graphs allow modelling the real world objects in terms of interactions. In a multilayer network, the interactions are distributed over layers (i.e., intralayer and interlayer edges). Network alignment (NA) is a methodology that allows mapping nodes between two or multiple given networks, by preserving topologically similar regions. For instance, NA can be applied to transfer knowledge from one biological species to another. In this paper, we present DANTEml, a software tool for the Pairwise Global NA (PGNA) of multilayer networks, based on topological assessment. It builds its own similarity matrix by processing the node embeddings computed from two multilayer networks of interest, to evaluate their topological similarities. The proposed solution can be used via a user-friendly command line interface, also having a built-in guided mode (step-by-step) for defining input parameters.

RESULTS

We investigated the performance of DANTEml based on (i) performance evaluation on synthetic multilayer networks, (ii) statistical assessment of the resulting alignments, and (iii) alignment of real multilayer networks. DANTEml over performed a method that does not consider the distribution of nodes and edges over multiple layers by 1193.62%, and a method for temporal NA by 25.88%; we also performed the statistical assessment, which corroborates the significance of its own node mappings. In addition, we tested the proposed solution by using a real multilayer network in presence of several levels of noise, in accordance with the same outcome pursued for the NA on our dataset of synthetic networks. In this case, the improvement is even more evident: +4008.75% and +111.72%, compared to a method that does not consider the distribution of nodes and edges over multiple layers and a method for temporal NA, respectively.

CONCLUSIONS

DANTEml is a software tool for the PGNA of multilayer networks based on topological assessment, that is able to provide effective alignments both on synthetic and real multi layer networks, of which node mappings can be validated statistically. Our experimentation reported a high degree of reliability and effectiveness for the proposed solution.

Supervised biological network alignment with graph neural networks

MOTIVATION

Despite the advances in sequencing technology, massive proteins with known sequences remain functionally unannotated. Biological network alignment (NA), which aims to find the node correspondence between species' protein-protein interaction (PPI) networks, has been a popular strategy to uncover missing annotations by transferring functional knowledge across species. Traditional NA methods assumed that topologically similar proteins in PPIs are functionally similar. However, it was recently reported that functionally unrelated proteins can be as topologically similar as functionally related pairs, and a new data-driven or supervised NA paradigm has been proposed, which uses protein function data to discern which topological features correspond to functional relatedness.

RESULTS

Here, we propose GraNA, a deep learning framework for the supervised NA paradigm for the pairwise NA problem. Employing graph neural networks, GraNA utilizes within-network interactions and across-network anchor links for learning protein representations and predicting functional correspondence between across-species proteins. A major strength of GraNA is its flexibility to integrate multi-faceted non-functional relationship data, such as sequence similarity and ortholog relationships, as anchor links to guide the mapping of functionally related proteins across species. Evaluating GraNA on a benchmark dataset composed of several NA tasks between different pairs of species, we observed that GraNA accurately predicted the functional relatedness of proteins and robustly transferred functional annotations across species, outperforming a number of existing NA methods. When applied to a case study on a humanized yeast network, GraNA also successfully discovered functionally replaceable human-yeast protein pairs that were documented in previous studies.

AVAILABILITY AND IMPLEMENTATION

The code of GraNA is available at https://github.com/luo-group/GraNA.

A Method Based on Temporal Embedding for the Pairwise Alignment of Dynamic Networks

In network analysis, real-world systems may be represented via graph models, where nodes and edges represent the set of biological objects (e.g., genes, proteins, molecules) and their interactions, respectively. This representative knowledge-graph model may also consider the dynamics involved in the evolution of the network (i.e., dynamic networks), in addition to a classic static representation (i.e., static networks). Bioinformatics solutions for network analysis allow knowledge extraction from the features related to a single network of interest or by comparing networks of different species. For instance, we may align a network related to a well known species to a more complex one in order to find a match able to support new hypotheses or studies. Therefore, the network alignment is crucial for transferring the knowledge between species, usually from simplest (e.g., rat) to more complex (e.g., human). Methods: In this paper, we present Dynamic Network Alignment based on Temporal Embedding (DANTE), a novel method for pairwise alignment of dynamic networks that applies the temporal embedding to investigate the topological similarities between the two input dynamic networks. The main idea of DANTE is to consider the evolution of interactions and the changes in network topology. Briefly, the proposed solution builds a similarity matrix by integrating the tensors computed via the embedding process and, subsequently, it aligns the pairs of nodes by performing its own iterative maximization function. Results: The performed experiments have reported promising results in terms of precision and accuracy, as well as good robustness as the number of nodes and time points increases. The proposed solution showed an optimal trade-off between sensitivity and specificity on the alignments produced on several noisy versions of the dynamic yeast network, by improving by ∼18.8% (with a maximum of 20.6%) the Area Under the Receiver Operating Characteristic (ROC) Curve (i.e., AUC or AUROC), compared to two well known methods: DYNAMAGNA++ and DYNAWAVE. From the point of view of quality, DANTE outperformed these by ∼91% as nodes increase and by ∼75% as the number of time points increases. Furthermore, a ∼23.73% improvement in terms of node correctness was reported with our solution on real dynamic networks.

Inference of a Dynamic Aging-related Biological Subnetwork via Network Propagation

Gene expression (GE)data capture valuable condition-specific information ("condition" can mean a biological process, disease stage, age, patient, etc.)However, GE analyses ignore physical interactions between gene products, i.e., proteins. Because proteins function by interacting with each other, and because biological networks (BNs)capture these interactions, BN analyses are promising. However, current BN data fail to capture condition-specific information. Recently, GE and BN data have been integrated using network propagation (NP)to infer condition-specific BNs. However, existing NP-based studies result in a static condition-specific subnetwork, even though cellular processes are dynamic. A dynamic process of our interest is human aging. We use prominent existing NP methods in a new task of inferring a dynamic rather than static condition-specific (aging-related)subnetwork. Then, we study evolution of network structure with age - we identify proteins whose network positions significantly change with age and predict them as new aging-related candidates. We validate the predictions via e.g., functional enrichment analyses and literature search. Dynamic network inference via NP yields higher prediction quality than the only existing method for inferring a dynamic aging-related BN, which does not use NP. Our data and code are available at https://nd.edu/~cone/dynetinf.

Data-driven biological network alignment that uses topological, sequence, and functional information

BACKGROUND

Network alignment (NA) can transfer functional knowledge between species' conserved biological network regions. Traditional NA assumes that it is topological similarity (isomorphic-like matching) between network regions that corresponds to the regions' functional relatedness. However, we recently found that functionally unrelated proteins are as topologically similar as functionally related proteins. So, we redefined NA as a data-driven method called TARA, which learns from network and protein functional data what kind of topological relatedness (rather than similarity) between proteins corresponds to their functional relatedness. TARA used topological information (within each network) but not sequence information (between proteins across networks). Yet, TARA yielded higher protein functional prediction accuracy than existing NA methods, even those that used both topological and sequence information.

RESULTS

Here, we propose TARA++ that is also data-driven, like TARA and unlike other existing methods, but that uses across-network sequence information on top of within-network topological information, unlike TARA. To deal with the within-and-across-network analysis, we adapt social network embedding to the problem of biological NA. TARA++ outperforms protein functional prediction accuracy of existing methods.

CONCLUSIONS

As such, combining research knowledge from different domains is promising. Overall, improvements in protein functional prediction have biomedical implications, for example allowing researchers to better understand how cancer progresses or how humans age.

Twadn: an efficient alignment algorithm based on time warping for pairwise dynamic networks

BACKGROUND

Network alignment is an efficient computational framework in the prediction of protein function and phylogenetic relationships in systems biology. However, most of existing alignment methods focus on aligning PPIs based on static network model, which are actually dynamic in real-world systems. The dynamic characteristic of PPI networks is essential for understanding the evolution and regulation mechanism at the molecular level and there is still much room to improve the alignment quality in dynamic networks.

RESULTS

In this paper, we proposed a novel alignment algorithm, Twadn, to align dynamic PPI networks based on a strategy of time warping. We compare Twadn with the existing dynamic network alignment algorithm DynaMAGNA++ and DynaWAVE and use area under the receiver operating characteristic curve and area under the precision-recall curve as evaluation indicators. The experimental results show that Twadn is superior to DynaMAGNA++ and DynaWAVE. In addition, we use protein interaction network of Drosophila to compare Twadn and the static network alignment algorithm NetCoffee2 and experimental results show that Twadn is able to capture timing information compared to NetCoffee2.

CONCLUSIONS

Twadn is a versatile and efficient alignment tool that can be applied to dynamic network. Hopefully, its application can benefit the research community in the fields of molecular function and evolution.

Temporal network alignment via GoT-WAVE

MOTIVATION

Network alignment (NA) finds conserved regions between two networks. NA methods optimize node conservation (NC) and edge conservation. Dynamic graphlet degree vectors are a state-of-the-art dynamic NC measure, used within the fastest and most accurate NA method for temporal networks: DynaWAVE. Here, we use graphlet-orbit transitions (GoTs), a different graphlet-based measure of temporal node similarity, as a new dynamic NC measure within DynaWAVE, resulting in GoT-WAVE.

RESULTS

On synthetic networks, GoT-WAVE improves DynaWAVE's accuracy by 30% and speed by 64%. On real networks, when optimizing only dynamic NC, the methods are complementary. Furthermore, only GoT-WAVE supports directed edges. Hence, GoT-WAVE is a promising new temporal NA algorithm, which efficiently optimizes dynamic NC. We provide a user-friendly user interface and source code for GoT-WAVE.

AVAILABILITY AND IMPLEMENTATION

http://www.dcc.fc.up.pt/got-wave/.

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Pairwise Versus Multiple Global Network Alignment

Biological network alignment (NA) aims to identify similar regions between molecular networks of different species. NA can be local or global. Just as the recent trend in the NA field, we also focus on global NA, which can be pairwise (PNA) and multiple (MNA). PNA produces aligned node pairs between two networks. MNA produces aligned node clusters between more than two networks. Recently, the focus has shifted from PNA to MNA, because MNA captures conserved regions between more networks than PNA (and MNA is thus hypothesized to yield higher-quality alignments), though at higher computational complexity. The issue is that, due to the different outputs of PNA and MNA, a PNA method is only compared to other PNA methods, and an MNA method is only compared to other MNA methods. Comparison of PNA against MNA must be done to evaluate whether MNA indeed yields higher-quality alignments, as only this would justify MNA's higher computational complexity. We introduce a framework that allows for this. We evaluate eight prominent PNA and MNA methods, on synthetic and real-world biological networks, using topological and functional alignment quality measures. We compare PNA against MNA in both a pairwise (native to PNA) and multiple (native to MNA) manner. PNA is expected to perform better under the pairwise evaluation framework. Indeed this is what we find. MNA is expected to perform better under the multiple evaluation framework. Shockingly, we find this not always to hold; PNA is often better than MNA in this framework, depending on the choice of evaluation test.

An Introductory Guide to Aligning Networks Using SANA, the Simulated Annealing Network Aligner

Sequence alignment has had an enormous impact on our understanding of biology, evolution, and disease. The alignment of biological networks holds similar promise. Biological networks generally model interactions between biomolecules such as proteins, genes, metabolites, or mRNAs. There is strong evidence that the network topology-the "structure" of the network-is correlated with the functions performed, so that network topology can be used to help predict or understand function. However, unlike sequence comparison and alignment-which is an essentially solved problem-network comparison and alignment is an NP-complete problem for which heuristic algorithms must be used.Here we introduce SANA, the Simulated Annealing Network Aligner. SANA is one of many algorithms proposed for the arena of biological network alignment. In the context of global network alignment, SANA stands out for its speed, memory efficiency, ease-of-use, and flexibility in the arena of producing alignments between two or more networks. SANA produces better alignments in minutes on a laptop than most other algorithms can produce in hours or days of CPU time on large server-class machines. We walk the user through how to use SANA for several types of biomolecular networks.

From homogeneous to heterogeneous network alignment via colored graphlets

Network alignment (NA) compares networks with the goal of finding a node mapping that uncovers highly similar (conserved) network regions. Existing NA methods are homogeneous, i.e., they can deal only with networks containing nodes and edges of one type. Due to increasing amounts of heterogeneous network data with nodes or edges of different types, we extend three recent state-of-the-art homogeneous NA methods, WAVE, MAGNA++, and SANA, to allow for heterogeneous NA for the first time. We introduce several algorithmic novelties. Namely, these existing methods compute homogeneous graphlet-based node similarities and then find high-scoring alignments with respect to these similarities, while simultaneously maximizing the amount of conserved edges. Instead, we extend homogeneous graphlets to their heterogeneous counterparts, which we then use to develop a new measure of heterogeneous node similarity. Also, we extend S3, a state-of-the-art measure of edge conservation for homogeneous NA, to its heterogeneous counterpart. Then, we find high-scoring alignments with respect to our heterogeneous node similarity and edge conservation measures. In evaluations on synthetic and real-world biological networks, our proposed heterogeneous NA methods lead to higher-quality alignments and better robustness to noise in the data than their homogeneous counterparts. The software and data from this work is available at https://nd.edu/~cone/colored_graphlets/.