NABEECO: biological network alignment with bee colony optimization algorithm

ABSTRACT

Motivation: A growing number of biological networks of ever increasing sizes are becoming available nowadays, making the ability to solve Network Alignment of primer importance. However, computationally the problem is hard for data sets of real-world sizes.

Results: we developed NABEECO, a novel and robust Network Alignment heuristic based on Bee Colony Optimization. We use the so-called Graph Edit Distance (GED) as optimization criterion, which is defined as the minimal amount of edge and node modifications necessary to transform one graph into another. We compare NABEECO on a set of protein-protein interaction networks to the current state of the art tool for biological networks, MI-GRAAL.

Conclusion: We present the first Bee Colony Optimization algorithm for biological Network Alignment. NABEECO, in contrast to many other tools, can be applied to all kinds of networks and allows incorporating prior knowledge about node/edge similarity, though this is not required a priori. NABEECO together with a more detailed description and all data sets used are publicly available at http://nabeeco.mpi-inf.mpg.de.

References

1. G. Blin, et al. Querying Protein-Protein Interaction Networks. ISBRA '09, 52--62, Berlin, Heidelberg, 2009. Springer.
2. H. Bunke, K. Riesen. Graph Edit Distance - Optimal and Suboptimal Algorithms with Applications, 113--143. Wiley-VCH Verlag GmbH & Co. KGaA, 2009.
3. D. Conte, et al. Thirty Years Of Graph Matching In Pattern Recognition. Int. J. Pattern Recog. and Artif. Intelligence, 2004.
4. X. Gao, et al. A survey of graph edit distance. Pattern Analysis & Applications, 13(1):113--129, 2010.
5. L. Hakes, et al. Protein-protein interaction networks and biology - what's the connection? Nat. Biotechnol., 26(1):69--72, 2008.
6. A. P. Heath, L. E. Kavraki. Computational challenges in systems biology. Comp. Sci. Rev., 3(1):1--17, 2009.
7. D. Karaboga and B. Akay. A comparative study of artificial bee colony algorithm. Appl. Math. and Comp., 214(1):108--132, 2009.
8. O. Kuchaiev, T. Milenković, V. Memišević, W. Hayes, and N. Pržulj. Topological network alignment uncovers biological function and phylogeny. J. R. Soc. Inter., 7(50):1341--1354, 2010.
9. O. Kuchaiev and N. Pržulj. Integrative Network Alignment Reveals Large Regions of Global Network Similarity in Yeast and Human. Bioinformatics, 27(10):1390--1396, 2011.
10. V. Memišević, and N. Pržulj. C-GRAAL: Common-neighbors-based global GRAph ALignment of biological networks. Integr. Biol., 4:734--743, 2012.
11. T. Milenković, W. Ng, W. Hayes, and N. Pržulj. Optimal network alignment with graphlet degree vectors. Cancer inf., 9:121, 2010.
12. K. Prasad, et al. Human Protein Reference Database - 2009 update. Nucl. acids res., 37, D767--72, 2009.
13. R. Singh, et al. Pairwise global alignment of protein interaction networks by matching neighborhood topology. RECOMB'07, 16--31, Berlin, Heidelberg, 2007. Springer.
14. I. Ulitsky, et al. Detecting Disease-Specific Dysregulated Pathways Via Analysis of Clinical Expression Profiles Research in Computational Molecular Biology. LNCS 4955, 347--359. Springer Berlin, Heidelberg, 2008.
15. I. Xenarios et al. DIP, the Database of Interacting Proteins: a research tool for studying cellular networks of protein interactions. Nucl. acids res., 30(1):303--305, 2002.

Index Terms

• Applied computing

  • Life and medical sciences

    • Computational biology

    • Genetics

    • Systems biology