24 June 14:15: Towards a Theory of Biological Networks

• Lecturer: Dr. Natasa Przulj, Assistant Professor in the Department of Computer Science at the University of California Irvine
• Time: Tuesday, 24 June 08 at 14:15
• Venue: Room B222 (Exactum building, 2nd floor), Department of Computer Science, University of Helsinki

Historically, a new natural science proceeds through three stages of development: first, amassing observations about the world; second, developing simplistic models capable of approximately reproducing the observations; and finally, the development of accurate predictive theoretical models under which the observations and earlier models become evident. Our current understanding of biological networks can be likened to the state of physics before Newton: although Copernicus, Kepler, Galileo and others had amassed a huge corpus of observations, and even some simplistic, case-specific models describing various phenomena, there was no theoretical framework tying it all together to provide understanding. Systems biology is currently somewhere between the first and second stages: we can hardly even describe the observational data mathematically, much less understand it theoretically.

Analysis and comparison of genetic sequences is well into the second stage mentioned above and making tentative steps into the third, but network analysis is just barely entering the second stage.  In this talk I discuss new tools, developed in my lab, which are advancing network analysis into this second stage, and possibly giving hints towards the third stage---a theoretical understanding of the structure of biological networks. Analogous to tools for analyzing and comparing genetic sequences, we are developing new tools that decipher large network data sets, with the goal of improving biological understanding and contributing to development of new therapeutics.

Because nature is variable and the data are noisy, traditional graph isomorphism is of little use for graph comparison, and a more flexible, intentionally approximate approach is necessary. We introduce a systematic measure of a network's local structure that imposes a large number of local similarity constraints on networks being compared. In particular, we generalize the degree of a node to a degree vector describing the local topology around a node.  We demonstrate that this local node similarity corresponds to similarity in biological function and involvement in disease.  Next, we demonstrate how statistics from large numbers of these local similarity measures can be combined to provide a global network similarity measure.  Using this global similarity measure, we demonstrate that protein-protein interaction (PPI) networks are better modeled by geometric graphs than by any previous model.  The geometric model is further corroborated by demonstrating that PPI networks can explicitly be embedded into a low-dimensional geometric space.  Finally, we argue for a theoretical reason why PPI networks might be geometric.