  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.
