Poster Presentation Society for Molecular Biology and Evolution Conference 2016

Alignment of biological networks (#441)

Michael Charleston 1 , Alexandru Radu 2 , Martin McGrane 2
  1. School of Physical Sciences, University of Tasmania, Hobart, TAS, Australia
  2. School of Information Technologies, University of Sydney, Sydney, NSW, Australia

Systems biology is a place of networks: gene regulatory networks, protein-protein interaction networks, food webs, social and contact networks.

Nodes of biological networks can be anything from microRNAs to genes to proteins, individuals to populations to species, and combinations thereof. The edges in the networks represent the different kinds of interactions these nodes can have with each other.  These networks change over time, between species, and across ecosystems, but they often retain common features, the revelation of which can help us understand the most important aspects of the networks, and what changes may have taken place to transform one into another. 

Biological networks have topological features that we can leverage to ease such comparisons; for example an abundance of certain motifs, the connectedness and degree distribution of nodes, and the overall diameter. We have developed methods (Node Fingerprinting [1] and Node Handprinting [2]) that leverage these features to create state of the art tools to align even large biological networks, with high accuracy and speed, and minimal memory. We have extended these alignment methods to estimate paths between networks, that describe plausible evolutionary routes through "network space" which can in turn provide estimates of evolutionary distance between networks – the Biological Network Edit Distance.

This poster describes our new methods, demonstrates their accuracy, and shows their potential for informing biologists interested in studying the relationships among biological networks.

  1. [1] Node fingerprinting: an efficient heuristic for aligning biological networks. A Radu, M Charleston. Journal of Computational Biology 21 (10), 760-770, 2014.
  2. [2] Node handprinting: A scalable and accurate algorithm for aligning multiple biological networks. A Radu, M Charleston. Journal of Computational Biology 22 (7), 687-697, 2015.
  3. [3] Biological Network Edit Distance. M McGrane, M Charleston. Journal of Computational Biology, 2016 (in press).