Source-linked AI summary
MAGNA: Maximizing Accuracy in Global Network Alignment
Vikram Saraph, Tijana Milenković
TL;DR
Existing network-alignment methods construct alignments by optimizing node similarity, then evaluate them with different measures such as conserved edges, while exact network comparison is computationally intractable. MAGNA instead uses a genetic-algorithm framework with a novel alignment crossover function to optimize alignment quality directly, and it outperforms existing state-of-the-art methods.
Problem
Exact network comparison is computationally intractable, while existing methods construct alignments from node similarity and evaluate their accuracy with different measures, typically conserved edges.
Method
MAGNA uses a genetic algorithm and a novel crossover function that combines parent alignments, enabling direct optimization of an alignment quality measure.
Results
MAGNA outperforms existing state-of-the-art methods in systematic evaluations.
Takeaways & Limitations
Network alignment can support biological knowledge transfer between species and help infer species’ phylogeny from similarities between biological networks.
Takeaways & Limitations
The alignment quality measure can fail to penalize mappings between network regions with mismatched densities when it is refined with respect to only one network.
Abstract
from arXiv · showhide
Biological network alignment aims to identify similar regions between networks of different species. Existing methods compute node "similarities" to rapidly identify from possible alignments the "high-scoring" alignments with respect to the overall node similarity. However, the accuracy of the alignments is then evaluated with some other measure that is different than the node similarity used to construct the alignments. Typically, one measures the amount of conserved edges. Thus, the existing methods align similar nodes between networks hoping to conserve many edges (after the alignment is constructed!). Instead, we introduce MAGNA to directly "optimize" edge conservation while the alignment is constructed. MAGNA uses a genetic algorithm and our 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. While we optimize our new and superior measure of the amount of conserved edges, MAGNA can optimize any alignment accuracy measure. In systematic evaluations against existing state-of-the-art methods (IsoRank, MI-GRAAL, and GHOST), MAGNA improves alignment accuracy of all methods.
1 Introduction
Network alignment seeks structurally similar regions across species despite computational hardness and biological variation. MAGNA addresses a mismatch in existing methods by directly optimizing alignment quality during construction and improves existing alignments.
- Motivation and background: PPI network alignment can transfer biological knowledge across species, complementing sequence alignment because network topology may reveal functions sequences do not.The paper focuses on pairwise global network alignment, while noting that the ideas can apply to other network types and local alignment.
- Motivation and background: Exact network comparison is computationally intractable, and biological variation means one network is rarely an exact subnetwork of another.Subgraph isomorphism is NP-complete, motivating heuristic alignment methods that seek the best inexact fit.
- Existing methods: Existing global methods score node-pair similarities, construct high-scoring mappings, and evaluate edge conservation with a different measure afterward.IsoRank, MI-GRAAL, and GHOST use different topology-based scoring and alignment strategies, including greedy, linear-assignment, or quadratic-assignment approaches.
- MAGNA framework: MAGNA directly optimizes conserved edges during global alignment using a genetic algorithm whose population of alignments evolves until the objective cannot improve further.Initial populations may be random or generated by existing methods, and fitter alignments survive into later generations.
- MAGNA framework: MAGNA introduces a crossover function that combines two parent alignments into a child alignment, enabling improvement of existing alignments and generation of new ones.The crossover defines a midpoint on a shortest path between permutations in a graph of transposition-adjacent alignments.
- Contributions and evaluation: MAGNA also introduces a composite conserved-edge quality measure and can optimize any topological or biological alignment-quality measure.The evaluation against IsoRank, MI-GRAAL, and GHOST on yeast networks with noisy counterparts reports improved alignment quality for all existing methods.
2 Methods
MAGNA represents network alignments as permutations and uses a genetic algorithm with a topology-based crossover function to optimize alignment quality directly. The method supports EC, ICS, S3, or any alignment-quality measure, while S3 evaluates mismatches against both source and target network structure.
- Alignment representation: MAGNA models an alignment as an injective node mapping, padding the smaller network with zero-degree dummy nodes so alignments can be represented as permutations.This permutation representation is required by the crossover function.
- Alignment crossover function: The crossover function creates a child alignment between two parent alignments by placing them in a graph of permutation adjacencies.Adjacent permutations differ by a transposition, and the child is defined as an alignment in the middle between the parents.
- Genetic algorithm: MAGNA evolves populations of alignments by retaining the fittest half and generating the remainder through crossover, with roulette wheel selection choosing parent pairs.Initial populations combine random alignments with, in some settings, an alignment from IsoRank, MI-GRAAL, or GHOST.
- Fitness and complexity: MAGNA can optimize EC, ICS, S3, or any alignment-quality measure, using the chosen measure as its fitness function.For EC, ICS, and S3, evaluating one alignment takes O(|E| log(|E|)) time, while crossover takes O(|V|) time.
- Existing alignment-quality measures: EC divides conserved edges by source-network edges but does not penalize mapping sparser source regions to denser target regions.In the illustrated alignment, EC is 4/5 = 0.8.
- Existing alignment-quality measures: ICS divides conserved edges by edges in the induced target subnetwork but does not penalize mapping denser source regions to sparser target regions.In the illustrated alignment, ICS is 4/5 = 0.8.
- S3 measure: S3 uses both source and target network structure, penalizing mismatches in both edge-to-non-edge directions.The illustrated alignment has S3 = 4/6 = 0.67, compared with EC = 4/5 = 0.8 and ICS = 4/5 = 0.8.
3 Results and discussion
MAGNA was evaluated systematically across noisy yeast networks by varying its population, generation, and optimization parameters. It improved every existing alignment across all noise levels and optimization measures, with performance depending on the initial population and measure.
- Data description: The evaluation aligned a 1,004-protein yeast PPI network with noisy versions containing 0%-25% additional lower-confidence PPIs, using a known node mapping.The high-confidence network contains 8,323 PPIs, and the original network is an exact subgraph of each noisy network.
- MAGNA parameters: MAGNA was tested across four initial population types, seven population sizes from 200 to 15,000, up to 2,000 generations, and three optimization measures: EC, ICS, and S3.The full parameter sweep produced 5,544 final alignments.
- MAGNA parameters: A maximum of 2,000 generations was selected because it helped random populations while not worsening results from IsoRank, MI-GRAAL, or GHOST populations.Random populations generally preferred about 2,000 generations, whereas the other populations often converged within roughly 400-1,200 generations.
- MAGNA evaluation and comparison with existing methods: MAGNA improved all original alignments across every noise level and for each of EC, ICS, and S3 when evaluated by correctly aligned node pairs.Maximum improvements were 2,588% over IsoRank, 256% over MI-GRAAL, and 118% over GHOST, depending on noise and optimization measure.
- MAGNA evaluation and comparison with existing methods: The best initial population depended on conditions: MI-GRAAL sometimes surpassed GHOST, while random populations often produced the best alignments at higher noise levels.This differed from the ordering of the original methods, where GHOST and MI-GRAAL generally exceeded IsoRank and random alignments.
- MAGNA evaluation and comparison with existing methods: No optimization measure was always best for node correctness; the preferred measure varied with MAGNA’s parameters and initial population.The study also reports that node correctness correlates best and most significantly with S3.
4 Concluding remarks
The paper presents MAGNA as a novel framework for optimizing pairwise global network alignment with respect to any alignment quality measure. It reports that MAGNA outperforms existing state-of-the-art methods and may support biological knowledge transfer and network-based evolutionary inference.
- Concluding remarks: MAGNA is a conceptually novel framework for optimizing pairwise global network alignment with respect to any alignment quality measure.The framework is reported to outperform existing state-of-the-art methods.
- Concluding remarks: Network alignment can transfer biological knowledge between aligned regions of well-characterized and poorly characterized species.The paper also describes network alignment as a way to infer species’ phylogeny from similarities between biological networks.