TY - GEN

T1 - Multiple graph edit distance - Simultaneous topological alignment of multiple protein-protein interaction networks with an evolutionary algorithm

AU - Ibragimov, Rashid

AU - Malek, Maximilian

AU - Baumbach, Jan

AU - Guo, Jiong

PY - 2014

Y1 - 2014

N2 - Motivation: We address the problem of multiple proteinprotein interaction (PPI) network alignment. Given a set of such networks for different species we might ask how much the network topology is conserved throughout evolution. Solving this problem will help to derive a subset of interactions that is conserved over multiple species thus forming a 'core interactome'. Methods: We model the problem as Topological Multiple one-to-one Network Alignment (TMNA), where we aim to minimize the total Graph Edit Distance (GED) between pairs of the input networks. Here, the GED between two graphs is the number of deleted and inserted edges that are required to make one graph isomorphic to another. By minimizing the GED we indirectly maximize the number of edges that are aligned in multiple networks simultaneously. However, computing an optimal GED value is computationally intractable. We thus propose an evolutionary algorithm and developed a software tool, GEDEVO-M, which is able to align multiple PPI networks using topological information only. We demonstrate the power of our approach by computing a maximal common subnetwork for a set of bacterial and eukaryotic PPI networks. GEDEVO-M thus provides great potential for computing the 'core interactome' of different species. Availability: http://gedevo.mpi- inf.mpg.de/multiple-network-alignment/.

AB - Motivation: We address the problem of multiple proteinprotein interaction (PPI) network alignment. Given a set of such networks for different species we might ask how much the network topology is conserved throughout evolution. Solving this problem will help to derive a subset of interactions that is conserved over multiple species thus forming a 'core interactome'. Methods: We model the problem as Topological Multiple one-to-one Network Alignment (TMNA), where we aim to minimize the total Graph Edit Distance (GED) between pairs of the input networks. Here, the GED between two graphs is the number of deleted and inserted edges that are required to make one graph isomorphic to another. By minimizing the GED we indirectly maximize the number of edges that are aligned in multiple networks simultaneously. However, computing an optimal GED value is computationally intractable. We thus propose an evolutionary algorithm and developed a software tool, GEDEVO-M, which is able to align multiple PPI networks using topological information only. We demonstrate the power of our approach by computing a maximal common subnetwork for a set of bacterial and eukaryotic PPI networks. GEDEVO-M thus provides great potential for computing the 'core interactome' of different species. Availability: http://gedevo.mpi- inf.mpg.de/multiple-network-alignment/.

KW - Evolutionary algorithm

KW - Graph edit distance

KW - Multiple network alignment

KW - Protein-protein interaction networks

UR - http://www.scopus.com/inward/record.url?scp=84905678869&partnerID=8YFLogxK

U2 - 10.1145/2576768.2598390

DO - 10.1145/2576768.2598390

M3 - Conference contribution

AN - SCOPUS:84905678869

SN - 9781450326629

T3 - GECCO 2014 - Proceedings of the 2014 Genetic and Evolutionary Computation Conference

SP - 277

EP - 283

BT - GECCO 2014 - Proceedings of the 2014 Genetic and Evolutionary Computation Conference

PB - Association for Computing Machinery

T2 - 16th Genetic and Evolutionary Computation Conference, GECCO 2014

Y2 - 12 July 2014 through 16 July 2014

ER -