GLAlign: A Novel Algorithm for Local Network Alignment

Exact p-values for global network alignments via combinatorial analysis of shared GO terms : REFANGO: Rigorous Evaluation of Functional Alignments of Networks using Gene Ontology

Network alignment aims to uncover topologically similar regions in the protein-protein interaction (PPI) networks of two or more species under the assumption that topologically similar regions tend to perform similar functions. Although there exist a plethora of both network alignment algorithms and measures of topological similarity, currently no "gold standard" exists for evaluating how well either is able to uncover functionally similar regions. Here we propose a formal, mathematically and statistically rigorous method for evaluating the statistical significance of shared GO terms in a global, 1-to-1 alignment between two PPI networks. Given an alignment in which k aligned protein pairs share a particular GO term g, we use a combinatorial argument to precisely quantify the p-value of that alignment with respect to g compared to a random alignment. The p-value of the alignment with respect to all GO terms, including their inter-relationships, is approximated using the Empirical Brown's Method. We note that, just as with BLAST's p-values, this method is not designed to guide an alignment algorithm towards a solution; instead, just as with BLAST, an alignment is guided by a scoring matrix or function; the p-values herein are computed after the fact, providing independent feedback to the user on the biological quality of the alignment that was generated by optimizing the scoring function. Importantly, we demonstrate that among all GO-based measures of network alignments, ours is the only one that correlates with the precision of GO annotation predictions, paving the way for network alignment-based protein function prediction.

GSLAlign: community detection and local PPI network alignment

High throughput protein-protein interaction (PPI) profiling and computational techniques have resulted in generating a large amount of PPI network data. The study of PPI networks helps in understanding the biological processes of the proteins. The comparative study of the PPI networks helps in identifying the conserved interactions across the species. This article presents a novel local PPI network aligner 'GSLAlign' that consists of two stages. It first detects the communities from the PPI networks by applying the GraphSAGE algorithm using gene expression data. In the second stage, the detected communities are aligned using a community aligner that is based on protein sequence similarity. The community detection algorithm produces more separable and biologically accurate communities as compared to previous community detection algorithms. Moreover, the proposed community alignment algorithm achieves 3-8% better results in terms of semantic similarity as compared to previous local aligners. The average connectivity and coverage of the proposed algorithm are also better than the existing aligners.Communicated by Ramaswamy H. Sarma.

Aligning Cross-Species Interactomes for Studying Complex and Chronic Diseases

Neurodegenerative diseases (NDs) are a group of complex disorders characterized by the progressive degeneration and dysfunction of neurons in the central nervous system. NDs encompass many conditions, including Alzheimer's disease and Parkinson's disease. Alzheimer's disease (AD) is a complex disease affecting almost forty million people worldwide. AD is characterized by a progressive decline of cognitive functions related to the loss of connections between nerve cells caused by the prevalence of extracellular Aβ plaques and intracellular neurofibrillary tangles plaques. Parkinson's disease (PD) is a neurodegenerative disorder that primarily affects the movement of an individual. The exact cause of Parkinson's disease is not fully understood, but it is believed to involve a combination of genetic and environmental factors. Some cases of PD are linked to mutations in the LRRK2, PARKIN and other genes, which are associated with familial forms of the disease. Different research studies have applied the Protein Protein Interaction (PPI) networks to understand different aspects of disease progression. For instance, Caenorhabditis elegans is widely used as a model organism for the study of AD due to roughly 38% of its genes having a human ortholog. This study's goal consists of comparing PPI network of C. elegans and human by applying computational techniques, widely used for the analysis of PPI networks between species, such as Local Network Alignment (LNA). For this aim, we used L-HetNetAligner algorithm to build a local alignment among two PPI networks, i.e., C. elegans and human PPI networks associated with AD and PD built-in silicon. The results show that L-HetNetAligner can find local alignments representing functionally related subregions. In conclusion, since local alignment enables the extraction of functionally related modules, the method can be used to study complex disease progression.

Challenges and Limitations of Biological Network Analysis

High-Throughput technologies are producing an increasing volume of data that needs large amounts of data storage, effective data models and efficient, possibly parallel analysis algorithms. Pathway and interactomics data are represented as graphs and add a new dimension of analysis, allowing, among other features, graph-based comparison of organisms' properties. For instance, in biological pathway representation, the nodes can represent proteins, RNA and fat molecules, while the edges represent the interaction between molecules. Otherwise, biological networks such as Protein-Protein Interaction (PPI) Networks, represent the biochemical interactions among proteins by using nodes that model the proteins from a given organism, and edges that model the protein-protein interactions, whereas pathway networks enable the representation of biochemical-reaction cascades that happen within the cells or tissues. In this paper, we discuss the main models for standard representation of pathways and PPI networks, the data models for the representation and exchange of pathway and protein interaction data, the main databases in which they are stored and the alignment algorithms for the comparison of pathways and PPI networks of different organisms. Finally, we discuss the challenges and the limitations of pathways and PPI network representation and analysis. We have identified that network alignment presents a lot of open problems worthy of further investigation, especially concerning pathway alignment.

A Novel Algorithm for Local Network Alignment Based on Network Embedding

Networks are widely used in bioinformatics and biomedicine to represent associations across a large class of biological entities. Network alignment refers to the set of approaches that aim to reveal similarities among networks. Local Network Alignment (LNA) algorithms find (relatively small) local regions of similarity between two or more networks. Such algorithms are in general based on a set of seed nodes that are used to build the alignment incrementally. A large fraction of LNA algorithms uses a set of vertices based on context information as seed nodes, even if this may cause a bias or a data-circularity problem. Moreover, using topology information to choose seed nodes improves overall alignment. Finally, similarities among nodes can be identified by network embedding methods (or representation learning). Given there are two networks, we propose to use network embedding to capture structural similarity among nodes, which can also be used to improve LNA effectiveness. We present an algorithm and experimental tests on real and syntactic graph data to find LNAs.

An Extensive Assessment of Network Embedding in PPI Network Alignment

Network alignment is a fundamental task in network analysis. In the biological field, where the protein-protein interaction (PPI) is represented as a graph, network alignment allowed the discovery of underlying biological knowledge such as conserved evolutionary pathways and functionally conserved proteins throughout different species. A recent trend in network science concerns network embedding, i.e., the modelling of nodes in a network as a low-dimensional feature vector. In this survey, we present an overview of current PPI network embedding alignment methods, a comparison among them, and a comparison to classical PPI network alignment algorithms. The results of this comparison highlight that: (i) only five network embeddings for network alignment algorithms have been applied in the biological context, whereas the literature presents several classical network alignment algorithms; (ii) there is a need for developing an evaluation framework that may enable a unified comparison between different algorithms; (iii) the majority of the proposed algorithms perform network embedding through matrix factorization-based techniques; (iv) three out of five algorithms leverage external biological resources, while the remaining two are designed for domain agnostic network alignment and tested on PPI networks; (v) two algorithms out of three are stated to perform multi-network alignment, while the remaining perform pairwise network alignment.

Multi-Neighborhood Learning for Global Alignment in Biological Networks

The global alignment of biological networks (GABN) aims to find an optimal alignment between proteins across species, such that both the biological structures and the topological structures of the proteins are maximally conserved. The research on GABN has attracted great attention due to its applications on species evolution, orthology detection and genetic analyses. Most of the existing methods for GABN are difficult to obtain a good tradeoff between the conservation of the biological structures and topological structures. In this paper, we propose a multi-neighborhood learning method for solving GABN (called as CLMNA). CLMNA first models GABN as an optimization of a weighted similarity which evaluates the conserved biological and topological similarities of an alignment, and then it combines a first-proximity, second-proximity and individual-aware proximity learning algorithm to solve the modeled problem. Finally, systematic experiments on 10 pairs of biological networks across 5 species show the superiority of CLMNA over the state-of-the-art network alignment algorithms. They also validate the effectiveness of CLMNA as a refinement method on improving the performance of the compared algorithms.

Comparative Analyses of Gene Co-expression Networks: Implementations and Applications in the Study of Evolution

Similarities and differences in the associations of biological entities among species can provide us with a better understanding of evolutionary relationships. Often the evolution of new phenotypes results from changes to interactions in pre-existing biological networks and comparing networks across species can identify evidence of conservation or adaptation. Gene co-expression networks (GCNs), constructed from high-throughput gene expression data, can be used to understand evolution and the rise of new phenotypes. The increasing abundance of gene expression data makes GCNs a valuable tool for the study of evolution in non-model organisms. In this paper, we cover motivations for why comparing these networks across species can be valuable for the study of evolution. We also review techniques for comparing GCNs in the context of evolution, including local and global methods of graph alignment. While some protein-protein interaction (PPI) bioinformatic methods can be used to compare co-expression networks, they often disregard highly relevant properties, including the existence of continuous and negative values for edge weights. Also, the lack of comparative datasets in non-model organisms has hindered the study of evolution using PPI networks. We also discuss limitations and challenges associated with cross-species comparison using GCNs, and provide suggestions for utilizing co-expression network alignments as an indispensable tool for evolutionary studies going forward.

A novel algorithm for finding top-k weighted overlapping densest connected subgraphs in dual 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.

Protein2Vec: Aligning Multiple PPI Networks with Representation Learning

Research of Protein-Protein Interaction (PPI) Network Alignment is playing an important role in understanding the crucial underlying biological knowledge such as functionally homologous proteins and conserved evolutionary pathways across different species. Existing methods of PPI network alignment often try to improve the coverage ratio of the alignment result by aligning all proteins from different species. However, there is a fundamental biological premise that needs to be considered carefully: not every protein in a species can, nor should, find its homologous proteins in other species. In this work, we propose a novel alignment method to map only those proteins with the most similarity throughout the PPI networks of multiple species. For the similarity features of the protein in the networks, we integrate both topological features with biological characteristics to provide enhanced supports for the alignment procedures. For topological features, we apply a representation learning method on the networks and generate a low dimensional vector embedding with its surrounding structural features for each protein. The topological similarity of proteins from different PPI networks can thus be transferred as the similarity of their corresponding vector representations, which provides a new way to comprehensively quantify the topological similarities between proteins. We also propose a new measure for the topological evaluation of the alignment results which better uncover the structural quality of the alignment across multiple networks. Both biological and topological evaluations on the alignment results of real datasets demonstrate our approach is promising and preferable against previous multiple alignment methods.