Global network alignment software tools | Protein interaction data analysis
Network alignment (NA) aims to find regions of similarities between species’ molecular networks. There exist two NA categories: local (LNA) and global (GNA). GNA finds large conserved regions and produces a one-to-one node mapping. Source text: Meng at al., 2016.
An algorithm for the global alignment of protein-protein interaction networks. NETAL uses a greedy method, based on the alignment scoring matrix, which is derived from both biological and topological information of input networks to find the best global network alignment. It outperforms other global alignment methods in terms of several measurements, such as Edge Correctness, Largest Common Connected Subgraphs and the number of common Gene Ontology terms between aligned proteins. As the running time of NETAL is much less than other available methods, NETAL can be easily expanded to multiple alignment algorithm. Furthermore, it overpowers all other existing algorithms in term of performance so that the short running time of NETAL allowed us to implement it as the first server for global alignment of protein-protein interaction networks.
Allows to find a global alignment of multiple protein-protein interaction networks. NetCoffee searches for a global alignment by maximizing a target function using simulated annealing on a set of weighted bipartite graphs that are constructed using a triplet approach similar to T-Coffee.
Unifies the description of spatial effects and the heterogeneity of contact networks. HyperMap is a program that implements a fast hybrid method. It can be applied to different games and extended to multiplex networks, opening promising future lines of research.
Algorithm capable of scalable multiple network alignment. Graemlin's explicit model of functional evolution allows both the generalization of existing alignment scoring schemes and the location of conserved network topologies other than protein complexes and metabolic pathways.
Allows alignment between two or more graphs of biological data. C3Part/Isofun is a versatile tool to study syntenies in bacteria, that may be adapted to various kinds of studies such as genomes, metabolic pathways or protein-protein interactions (PPIs). It is not restricted to genomes but it can be applied to any kind of graphs. This tool can be used to search functional gene associations.
A public, open-source, web-based application for determining multiple network alignments (MNAs) from existing pairwise network alignments (PNAs) that addresses all the aforementioned challenges. With SMAL, PNAs can be combined rapidly to obtain an MNA. The software also supports visualization and user-data interactions to facilitate exploratory analysis and sensemaking. SMAL is especially useful when multiple alignments relative to a particular protein-protein interaction network (PPIN) are required; furthermore, SMAL alignments are persistent in that existing correspondences between networks (obtained during PNA or MNA) are not lost as new networks are added.
An algorithm for global alignment of multiple protein-protein interaction (PPI) networks. The guiding intuition here is that a protein in one PPI network is a good match for a protein in another network if their respective sequences and neighborhood topologies are a good match.
Finds well-fitting network models by comparing large real-world networks against random graph models according to various network structural similarity measures. GraphCrunch has unique capabilities of finding computationally expensive RGF-distance and GDD-agreement measures. In addition, it computes several standard global network measures and thus supports the largest variety of network measures thus far. GraphCrunch compares real-world networks against a series of network models and that has built-in parallel computing capabilities allowing for a user specified list of machines on which to perform compute intensive searches for local network properties.
A global multiple-network alignment tool based on spectral clustering on the induced graph of pairwise alignment scores. IsoRankN outperforms existing algorithms for global network alignment in coverage and consistency on multiple alignments of the five available eukaryotic networks. Being based on spectral methods, IsoRankN is both error tolerant and computationally efficient.
A network alignment algorithm which can integrate any number and type of similarity measures between network nodes (e.g. proteins), including, but not limited to, any topological network similarity measure, sequence similarity, functional similarity and structural similarity. MI-GRAAL has been tested on Gentoo and Mandriva Linux distributions.
A global pairwise network aligner that uses a novel spectral signature to measure topological similarity between subnetworks. GHOST combines a seed-and-extend global alignment phase with a local search procedure and exceeds state-of-the-art performance on several network alignment tasks.
Given protein-protein interaction (PPI) networks of a pair of species, a pairwise global alignment corresponds to a one-to-one mapping between their proteins. SPINAL is an algorithm for the problem of globally aligning a pair of PPI networks.
A program to directly "optimize" edge conservation while the alignment is constructed, without decreasing the quality of node mapping. MAGNA uses a genetic algorithm and a novel function for 'crossover' of two 'parent' alignments into a superior 'child' alignment to simulate a 'population' of alignments that 'evolves' over time; the 'fittest' alignments survive and proceed to the next 'generation', until the alignment accuracy cannot be optimized further.
A global network alignment algorithm that makes use of both network topology and sequence homology information, based upon the observation that topologically important proteins in a PPI network usually are much more conserved and thus, more likely to be aligned. HubAlign uses a minimum-degree heuristic algorithm to estimate the topological and functional importance of a protein from the global network topology information. Then HubAlign aligns topologically important proteins first and gradually extends the alignment to the whole network.
A formal definition of the global many-to-many alignment of multiple protein-protein interaction networks. The computational burden of the BEAMS algorithm in terms of execution speed and memory requirements is more reasonable than the competing algorithms.
A global network alignment tool, which combines an efficient solver based on Lagrangian relaxation with a scoring function based on the statistics of small induced subgraphs called graphlets. Unlike previous aligners, which either do not take into account the mapped interactions (e.g., the previous GRAAL aligners, ISORANK, etc), or use naive interaction mapping scoring schemes (e.g., NATALIE), L-GRAAL optimizes a novel objective function that takes into account both sequence-based protein conservation and graphlet-based interaction conservation, by using a novel alignment search heuristic based on integer programming and Lagrangian relaxation.
It is an extension of MAGNA. MAGNA++ introduces several novelties: 1) It simultaneously maximizes any one of three different measures of edge conservation (including our recent superior S3 measure) and any desired node conservation measure, which further improves alignment quality compared to maximizing only node conservation or only edge conservation. 2) It speeds up the original MAGNA algorithm by parallelizing it to automatically use all available resources, as well as by reimplementing the edge conservation measures more efficiently. 3) It provides a friendly graphical user interface for easy use by domain (e.g., biological) scientists. 4) At the same time, MAGNA++ offers source code for easy extensibility by computational scientists.
An algorithm for optimizing global pairwise alignments of protein interaction networks, based on a local optimization heuristic that has previously demonstrated its effectiveness for a variety of other intractable problems. PISwap can begin with different types of network alignment approaches and then iteratively adjust the initial alignments by incorporating network topology information, trading it off for sequence information.
A multiobjective memetic algorithm for the problem of PPI network alignment that uses extremely efficient swap-based local search, mutation, and crossover operations to create a population of alignments. This algorithm optimizes the conflicting goals of topological and sequence similarity using the concept of Pareto dominance, exploring the tradeoff between the two objectives as it runs.
A method for pairwise global alignment of protein–protein interaction (PPI) networks. Its novel scoring scheme integrates sequence information and both local and global network topology. Based on a hierarchical clustering of the input networks, we compute a homology score between proteins. We propose an iterative approach to find an alignment that scores high in our model while trying to preserve interactions. In our experiments on a diverse set of benchmarks, ModuleAlign outperforms state-of-the-art methods such as GHOST, MAGNA ++, NETAL, HubAlign and L-GRAAL in terms of both alignment accuracy and functional consistency.
Provides a method for pairwise global alignment of dynamic networks. DynaMAGNA++ is a dynamic network alignment (NA) method. It optimizes edge as well as node conservation across the aligned networks. It also conserves dynamic edges (events) and similarity between evolving node neighborhoods. This application is an extension of a static NA method, MAGNA++.
A Cytoscape app for visual and user-assisted network alignment. CytoGEDEVO extends the previous GEDEVO methodology for global pairwise network alignments with new graphical and functional features. It aligns pairs of networks, where the result is a one-to-one node mapping. Alignments are fully resumable, i.e. parameters can be adjusted anytime and the alignment resumed with the new parameters. Expert knowledge can be incorporated by the user by fixating node pairs. CytoGEDEVO is not limited to network topology and can make use of an unlimited number of externally supplied scores, without imposing restrictions on the score type (that means you can just throw BLAST E-values or Bit-scores or whatever at it and it will work). It also allows importing result files generated by other aligners.
Explores the space of alignments looking for ones scoring well according to M (an objective function for alignment quality). SANA is based on a metaheuristic search algorithm with a rich history of successful applications to many optimization problems across a wide variety of domains. It was applied to protein-protein interaction networks using Symmetric Substructure Score (S3) as the topological measure. The tool significantly outperforms all other aligners in S3 score, for every pair of networks tested.
Serves for pairwise global alignment of dynamic networks. DynaWAVE consists of a dynamic network alignment (NA) approach and is an extension of WAVE software. It can be used for alignment of protein interaction networks that evolve over time. In particular, this software conserves dynamic edges events and similarity between evolving node neighborhoods.
Assists users in searching similar net- works from a given database. NSSRF performs network search by considering the topology of query network and target network. It is an algorithm composed of two phases: (1) the offline model building phase, where it uses subgraph signatures and cosine similarity score as features; and (2) similarity query phase where each query is inputted into the trained regression model from which the similarity score and similar networks are returned.
A global multiple network aligner. First, Fuse computes novel similarity scores between proteins by fusing sequence similarities and network wiring patterns over all proteins in all PPI networks being aligned, using non-negative matrix tri-factorization (NMTF). Second, it construct a one-to-one global multiple network alignment by using an approximate maximum weight k-partite matching solver. We compare the alignments of Fuse to the ones of the state-of-the art aligners, Beams, Smetana, CSRW and NH. We find that even when using solely protein sequence similarity, Fuse already outperforms all other network aligners by producing a larger number of functionally homogeneous clusters that cover all aligned networks.
Aligns general molecular networks based on both the node similarity and the network architecture similarity. MNAligner is an algorithm that uses integer quadratic programming (IQP) with a log-probability like criterion. In addition to simple topological substructures such as chains and trees, it can reveal biologically meaningful units or subnetworks with loops or network motifs. It can also be applied to weighted or unweighted networks and to directed or undirected networks.
An efficient algorithm for alignment of multiple large-scale biological networks. SMETANA outperforms many state-of-the-art network alignment techniques, in terms of computational efficiency, alignment accuracy, and scalability. It can easily align tens of genome-scale networks with thousands of nodes on a personal computer without any difficulty.
Calculates global pairwise network alignment. Natalie is a Lagrangian relaxation approach that, in combination with a branch-and-bound method, computes provably optimal network alignments. Computational experiments on the alignment of protein-protein interaction (PPI) networks and on the classification of metabolic subnetworks demonstrate that Natalie is reasonably fast and has advantages over pure heuristics.
A connected-components based fast algorithm for network alignment. Comparing to existing tools, HopeMap is fast with linear computational cost, highly accurate in terms of KO and GO terms specificity and sensitivity, and can be extended to multiple alignments easily.
Serves for the global alignment of protein-protein interaction (PPI) networks. INDEX is an algorithm employing two concepts for the depth traversal and stepwise growth of the alignment core. It allows computation of the scores of all the pairs of nodes and the neighbors’ score of the pairs. It creates an initial alignment based on the matching score strategy and selects a subset of the aligned proteins between the two networks as the alignment core.
Provides an improvement over the OptNetAlign methodology. SUMONA main contribution is increasing the performance of achieving multiple alignment objectives by supervising the optimization process and prioritizing some objectives above others. SUMONA approach uses yet another generated alignment as input of OptNetAlign at each iteration. The performance of SUMONA depends on many factors such as alignment objectives, network characteristics of the aligned species and quality of input data that is generated by other prominent aligners.
Uses heuristics for maximizing the number of aligned edges between two networks and is based solely on network topology. As such, it can be applied to any type of network, such as social, transportation, or electrical networks. C-GRAAL can be used to align human-pathogen inter-species PPI networks and that it can identify patterns of pathogen interactions with host proteins solely from network topology.
Enables users to identify age related genes from non-age related genes. Tempo takes the network alignment problem one huge step forward by moving beyond the classical static network models. It can generate statistically significant alignments, even when evolution rates of given networks are high. After testing, the program has shown that it can detect genes that contribute to the progression of Alzheimer's disease, Huntington's diabetes and type II diabetes.
Maximizes an alignment quality measure by evolving a population of alignments over time. multiMAGNA++ can be used for biological network alignment, i.e., to align molecular networks of different species and consequently allows for the transfer of biological knowledge from well-studied to poorly-studied species between conserved (aligned) network regions. multiMAGNA++ is a multiple network alignment (MNA) extension of a state-of-the-art PNA MAGNA++ that can directly optimize both node and edge conservation. multiMAGNA++ scales well to larger network sizes and a larger number of networks and can be parallelized effectively.
Computes the maximum common edge subgraph problem for two or more graphs. CytoMCS is a heuristic maximum common edge subgraph detection tool for the Cytoscape network analysis and visualization platform. The software uses an iterative local search algorithm to search for an alignment that maximizes the number of edges conserved between all graphs. The input and output of the app is provided through Cytoscapes standard data types, and edges are annotated with conservation scores for visualization and analysis.
Allows global pairwise network alignment of protein-protein interactions (PPI) networks. IBNAL makes use of indices to align networks. The software uses a methodology to build a clique-based index and its results confirm that that homology information is encoded in the network topology instead of sequence similarity. IBNAL was examined on two different datasets, the Isobase and NAPAbench suite datasets.
Utilizes the artificial bee colony computing strategies for solving the so-called Graph Edit Distance (GED) problem. NABEECO is a tool for protein-protein interaction (PPI) network alignment. It is a flexible software and can work on topology only. It can further be executed on any kind of graph, directed graphs, for instance, thereby generally allowing to compare, for example, gene regulatory networks.
Provides a general network alignment strategy for simultaneously optimizing both node conservation and weighted edge conservation. WAVE can be used with any node cost function or combination of multiple node cost functions. This method is easily applicable in any domain. It is superior against alignment strategies under multiple node cost functions, especially with respect to topological alignment quality.
Allows users to increase the number of aligned triangles across networks. TAME is an algorithm that performs about the network alignment problem in using higher-order sub-structures to drive the alignment process. It also assists users in identification of novel biological insights. This method returns a set of topological scores that can be combined with many of the other ideas in the network alignment literature.
Optimizes discrete particle swarm to resolve the global alignment of protein-protein interaction (PPI) networks. PSONA employs a particle discrete method of particle swarm optimization (PSO) based on permutation for network alignment problem. Used as a booster tool, it permits users to improve the quality of state-of-art aligners. This tool can take into account protein sequence similarity and interaction conservations.
Aligns pathways using integrated database information from SCOP, CATH, EC number and UniProt. SIGNALIGN is a web-based tool which provides a search engine. This search engine mines the related inbuilt information of the proteins and their classification schemes both in CATH and SCOP along with the relevant UniProt and Protein Data Bank (PDB) information. The software allows structure based alignment of proteins and prediction of linear biochemical pathways and thus the understanding of their evolutionary relationship.
Allows users to align and query biological networks. AbiNet matches connected subgraphs to proceed. It constructs a one-to-one correspondence between pairs of nodes in the two networks. This tool can perform network querying in two different modes, depending on which of the two input networks is chosen to play the role of the Master. It is an asymmetric approach that permits users to conduct kinds of network analysis difficult to carry out with other methods.
Dr. Yashwanth Subbannayya obtained his M.Sc. degree in Medical Biochemistry from Manipal University. He qualified the competitive CSIR-UGC National Eligibility Test and joined the Institute of Bioinformatics, Bangalore as a UGC Junior Research Fellow. As part of his Ph.D. work, he studied the molecular mechanisms of gastric cancer in clinical specimens using quantitative proteomic technologies. This study, the results of which were published in Cancer Biology and Therapy, yielded a novel therapeutic target for gastric cancer- CAMKK2. Further, he also studied the serum proteome of gastric cancer patients and developed assays for potential markers using the revolutionary multiple reaction monitoring approach. The results of this study were published in Journal of Proteomics. In addition to his research work, he also trained extensively in sample preparation for mass spectrometry, fractionation techniques and gained expertise in quantitative proteomic techniques and data analysis. In addition, he also trained extensively in various validation platforms including immunohistochemsitry, multiple reaction monitoring and Western blot. He has also worked as a curator for several biological databases including NetPath, Human Protein Reference Database (HPRD) and Breast cancer database. His work in various research projects have yielded him 23 publications either as lead author or co-author in peer reviewed journals. He is a reviewer for the journal Proteomics.
Dr. Yashwanth Subbannayya joined the YU-IOB Center for Systems Biology and Molecular Medicine in June, 2015. During the initial period, his job consisted of assisting other personnel of the university in the establishment of YU-IOB Center for Systems Biology and Molecular Medicine. He was also involved in training of Ph.D. students in biological aspects. After the establishment of the center, he trained in cell culture techniques and metabolomics analysis. At YU-IOB CSBMM, he is studying the molecular mechanisms in various cancers including oral cancer. In addition, he is studying the molecular mechanisms as well as the metabolic constituents of traditional medicine formulations using mass spectrometry technologies. In June 2016, he convened the national symposium “Genomics in clinical practice: Future of precision medicine” held at Yenepoya University on June 1 and 2, 2016. The resource persons included 16 individuals from various academic organizations as well as industry. The symposium was attended by 218 participants from 24 institutions around India. He is a member of the Scientific Review Board of Yenepoya Research Centre where he facilitates timely scientific review of research projects.