Lecture
Protein-Protein Interaction Networks: Issues, Models, and Comparisons
Speaker: |
Natasa Przulj, Assistant Professor in the Computer Science Department at UC Irvine |
Date: |
Thursday, 14 September 2006 |
Time: |
12:00-13:30 |
Location: |
"Mediterranean Studies" Seminar Room, FORTH. Heraklion, Crete |
Host: |
Prof. Ioannis (Yanni) Tollis |
Abstract: |
One of the fundamental problems in computational biology is
understanding the inner workings of a cell. Most cellular processes are
carried out by protein-protein interactions (PPIs). Thus, analyzing and
modeling of large PPI networks is an integral part of this process.
Analogous to biological sequence comparison, comparing cellular networks is
an important problem that could provide insight into biological understanding
and therapeutics. The full-scale comparison of two arbitrary networks is
computationally intractable, because it contains the subgraph
isomorphism problem, which is NP-complete. Thus, heuristic measures must be
developed for network comparison.
We devise a highly constraining network comparison metric based on local
structural properties that are a direct generalization of the degree
distribution. We use this new metric to demonstrate that geometric random
graphs better model PPI networks than do Erdos-Renyi, random
scale-free, or Barabasi-Albert scale-free networks. Our new systematic
measure of a network's local structure imposes a large number of similarity
constraints on networks being compared. In particular, we generalize the
degree distribution, which measures the number of nodes ``touching'' k edges,
into graphlet degree distributions measuring the number of nodes ``touching''
k graphlets, where graphlets are small connected non-isomorphic induced
subgraphs of a large network. Clearly, the degree distribution is the first
one in the spectrum of graphlet degree distributions, since an edge is the
only 2-node graphlet. We design a network ``agreement'' measure as a number
in [0,1] that encompasses the 73 graphlet degree distributions of 2-, 3-, 4-,
and 5-node graphlets. This measure is easily extendible to a greater number
of constraints (i.e., graphlets) and the extensions are limited only by the
available CPU. |
Bio: |
Natasa Przulj is an Assistant Professor in the Computer Science Department
at UC Irvine. Her research involves developing new tools for analyzing and
modeling of complex networks in cellular biology. She was a postdoctoral fellow
at the Samuel Lunenfeld Research Institute in Toronto working under the
supervision of Prof. Jeff Wrana. She completed her Ph.D. in the Department of
Computer Science at the University of Toronto in 2005 under the supervision of
Prof. Derek Corneil and Prof. Igor Jurisica. She received her M.Sc. from the
same department in 2000 and her B.Sc. in Mathematics and Computing Science from
Simon Fraser University, BC, Canada in 1997 after starting at the Department
of Mathematics of the University of Belgrade in Yugoslavia. She spent two
years in industry working for Hughes Aircraft, Westech Information Systems
(subsidiary of BC Hydro, Vancouver, Canada), and IBM. |