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

ABSTRACT

Motivation: We address the problem of multiple protein-protein 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/.

References

1. A. E. Aladag and C. Erten. SPINAL: scalable protein interaction network alignment. Bioinformatics, 29(7):917--924, 2013.
2. F. Alkan and C. Erten. BEAMS: backbone extraction and merge strategy for the global many-to-many alignment of multiple PPI networks. Bioinformatics, 30(4):531--539, 2014.
3. S. F. Altschul, W. Gish, W. Miller, E. W. Myers, and D. J. Lipman. Basic local alignment search tool. Journal of molecular biology, 215(3):403--410, Oct. 1990.
4. B. Aranda, H. Blankenburg, S. Kerrien, F. Brinkman, A. Ceol, E. Chautard, J. Dana, J. De Las Rivas, M. Dumousseau, E. Galeota, A. Gaulton, J. Goll, R. Hancock, R. Isserlin, R. Jimenez, J. Kerssemakers, J. Khadake, D. Lynn, M. Michaut, G. O'Kelly, K. Ono, S. Orchard, C. Prieto, S. Razick, O. Rigina, L. Salwinski, M. Simonovic, S. Velankar, A. Winter, G. Wu, G. Bader, G. Cesareni, I. Donaldson, D. Eisenberg, G. Kleywegt, J. Overington, S. Ricard-Blum, M. Tyers, M. Albrecht, and H. Hermjakob. PSICQUIC and PSISCORE: accessing and scoring molecular interactions. Nature Methods, 8(7):528--529--, 2011.
5. L. Chindelevitch, C.-Y. Ma, C.-S. Liao, and B. Berger. Optimizing a global alignment of protein interaction networks. Bioinformatics, 29(21):2765--2773, 2013.
6. Y.-P. Deniélou, F. Boyer, A. Viari, and M.-F. Sagot. Multiple alignment of biological networks: A flexible approach. In CPM, pages 263--273, 2009.
7. M. El-Kebir, J. Heringa, and G. Klau. Lagrangian relaxation applied to sparse global network alignment. In M. Loog, L. Wessels, M. Reinders, and D. Ridder, editors, Pattern Recognition in Bioinformatics, volume 7036 of Lecture Notes in Computer Science, pages 225--236. Springer Berlin Heidelberg, 2011.
8. J. Flannick, A. F. Novak, C. B. Do, B. S. Srinivasan, and S. Batzoglou. Automatic parameter learning for multiple local network alignment. Journal of Computational Biology, 16(8):1001--1022, 2009.
9. J. Hu, B. Kehr, and K. Reinert. NetCoffee: a fast and accurate global alignment approach to identify functionally conserved proteins in multiple networks. Bioinformatics, 30(4):540--548, 2014.
10. R. Ibragimov, M. Malek, J. Guo, and J. Baumbach. GEDEVO: an evolutionary graph edit distance algorithm for biological network alignment. In GCB, pages 68--79, 2013.
11. R. Ibragimov, J. Martens, J. Guo, and J. Baumbach. NABEECO: biological network alignment with bee colony optimization algorithm. In GECCO (Companion), pages 43--44, 2013.
12. K. A. D. Jong. Evolutionary computation - a unified approach. MIT Press, 2006.
13. M. Kalaev, V. Bafna, and R. Sharan. Fast and accurate alignment of multiple protein networks. Journal of Computational Biology, 16(8):989--999, 2009.
14. M. Koyutürk, Y. Kim, S. Subramaniam, W. Szpankowski, and A. Grama. Detecting conserved interaction patterns in biological networks. Journal of Computational Biology, 13(7):1299--1322, 2006.
15. O. Kuchaiev and N. Przulj. Integrative Network Alignment Reveals Large Regions of Global Network Similarity in Yeast and Human. Bioinformatics, 27(10):1390--1396, Mar. 2011.
16. C.-S. Liao, K. Lu, M. Baym, R. Singh, and B. Berger. Isorankn: spectral methods for global alignment of multiple protein networks. Bioinformatics, 25(12), 2009.
17. S. Mohammadi and A. Grama. Biological network alignment. In M. Koyutark, S. Subramaniam, and A. Grama, editors, Functional Coherence of Molecular Networks in Bioinformatics, pages 97--136. Springer New York, 2012.
18. L. A. Mueller, M. Dehmer, and F. Emmert-Streib. Comparing biological networks: A survey on graph classifying techniques. In A. Prokop and B. Csukás, editors, Systems Biology, pages 43--63. Springer Netherlands, 2013.
19. B. Neyshabur, A. Khadem, S. Hashemifar, and S. S. Arab. NETAL: a new graph-based method for global alignment of protein-protein interaction networks. Bioinformatics, 29(13):1654--1662, 2013.
20. J. Parrish, J. Yu, G. Liu, J. Hines, J. Chan, B. Mangiola, H. Zhang, S. Pacifico, F. Fotouhi, V. DiRita, T. Ideker, P. Andrews, and R. Finley. A proteome-wide protein interaction map for campylobacter jejuni. Genome Biology, 8(7):R130, 2007.
21. R. Patro and C. Kingsford. Global network alignment using multiscale spectral signatures. Bioinformatics, 28(23):3105--3114, 2012.
22. J. M. Peregrin-Alvarez, X. Xiong, C. Su, and J. Parkinson. The modular organization of protein interactions in Escherichia coli. PLoS Comput Biol, 5(10):e1000523, 10 2009.
23. K. T. S. Prasad, R. Goel, K. Kandasamy, S. Keerthikumar, S. Kumar, S. Mathivanan, D. Telikicherla, R. Raju, B. Shafreen, A. Venugopal, L. Balakrishnan, A. Marimuthu, S. Banerjee, D. S. Somanathan, A. Sebastian, S. Rani, S. Ray, H. C. J. Kishore, S. Kanth, M. Ahmed, M. K. Kashyap, R. Mohmood, Y. L. Ramachandra, V. Krishna, A. B. Rahiman, S. Mohan, P. Ranganathan, S. Ramabadran, R. Chaerkady, and A. Pandey. Human Protein Reference Database--2009 update. Nucleic acids research, 37(Database issue):D767--D772, Jan. 2009.
24. N. Przulj. Biological network comparison using graphlet degree distribution. Bioinformatics, 23(2):e177--e183, Jan. 2007.
25. S. M. E. Sahraeian and B.-J. Yoon. SMETANA: Accurate and Scalable Algorithm for Probabilistic Alignment of Large-Scale Biological Networks. PLoS ONE, 8(7):e67995, 07 2013.
26. R. Saito, M. E. Smoot, K. Ono, J. Ruscheinski, P.-L. Wang, S. Lotia, A. R. Pico, G. D. Bader, and T. Ideker. A travel guide to Cytoscape plugins. Nat Meth, 9(11):1069--1076, Nov. 2012.
27. S. Sato, Y. Shimoda, A. Muraki, M. Kohara, Y. Nakamura, and S. Tabata. A large-scale protein-protein interaction analysis in synechocystis sp. pcc6803. DNA Research, 14(5):207--216, 2007.
28. A. Schlicker, F. S. Domingues, J. Rahnenführer, and T. Lengauer. A new measure for functional similarity of gene products based on gene ontology. BMC Bioinformatics, 7:302, 2006.
29. Y. Shimoda, S. Shinpo, M. Kohara, Y. Nakamura, S. Tabata, and S. Sato. A large scale analysis of protein-protein interactions in the nitrogen-fixing bacterium mesorhizobium loti. DNA Research, 15(1):13--23, 2008.
30. I. Xenarios, L. Salwınski, X. Joyce, P. Higney, S.-M. M. Kim, and D. Eisenberg. DIP, the Database of Interacting Proteins: a research tool for studying cellular networks of protein interactions. Nucleic acids research, 30(1):303--305, Jan. 2002.

Index Terms

• Applied computing

  • Life and medical sciences

    • Computational biology

    • Genetics

    • Systems biology