title: A multiobjective memetic algorithm for PPI network alignment.
abstract: BACKGROUND
  There recently has been great interest in aligning protein-protein interaction (PPI) networks to identify potentially orthologous proteins between species. It is thought that the topological information contained in these networks will yield better orthology predictions than sequence similarity alone. Recent work has found that existing aligners have difficulty making use of both topological and sequence similarity when aligning, with either one or the other being better matched. This can be at least partially attributed to the fact that existing aligners try to combine these two potentially conflicting objectives into a single objective.
  
  
  RESULTS
  We present Optnetalign, 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. This allows us to produce many high-quality candidate alignments in a single run. Our algorithm produces alignments that are much better compromises between topological and biological match quality than previous work, while better characterizing the diversity of possible good alignments between two networks. Our aligner's results have several interesting implications for future research on alignment evaluation, the design of network alignment objectives and the interpretation of alignment results.
  
  
  METHODS
  The C++ source code to our program, along with compilation and usage instructions, is available at https://github.com/crclark/optnetaligncpp/
authors: Department of Computer Science, University of Colorado Colorado Springs, Colorado Springs, CO 80918, USA.
authors: Connor
authors: C
authors: Clark
authors: Department of Computer Science, University of Colorado Colorado Springs, Colorado Springs, CO 80918, USA.
authors: Jugal
authors: J
authors: Kalita
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D006801:Humans; D025941:Protein Interaction Mapping / Q000379:methods*; D011506:Proteins / Q000378:metabolism*; D016415:Sequence Alignment / Q000379:methods*; D012984:Software
chemical_list: D011506:Proteins