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.
Allows researchers to find a global alignment of multiple protein-protein interaction networks. NetCoffee searches for a global alignment and functional orthologs by maximizing a target function. It uses a simulated annealing on a set of weighted bipartite graphs that are constructed with a triplet approach similar to T-Coffee. This tool can display the mapping result and permits users to manage their submissions.
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.
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.
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.
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.
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.
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.
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 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.
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.
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 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.
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.
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.
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 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.
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.