Dynamic network models of protein complexes

Current views of biological networks and pathways are primarily static, comprising databases of curated pathways (Croft et al. 2011, Liberzon et al. 2011) or of pair-wise interactions, primarily between proteins (Stark et al. 2006). Many methods have been developed to cluster, partition, or segment an interaction network into putative complexes (Bader and Hogue 2003, Clauset et al. 2004, Rivera et al. 2010). Recent comparisons suggest that hierarchical stochastic block models provide the most accurate reconstruction of real protein complexes from interaction data (Clauset et al. 2008, Park and Bader 2011). These static views, however, fail to capture the rich dynamic net-work structure of a cell. Accounting for dynamic changes in protein complexes is crucial to building accurate models of cellular state. Our approach uses stochastic block models, in which interactions are conditionally independent given group membership. These models can be hierarchical, with larger complexes containing sub-complexes with more fine-grained interaction probabilities, and complexes can themselves be contained in larger structures with coarse-grained interaction probabilities. Networks are observed at specific time points, termed ‘snap-shots,’ and the goal is to infer or estimate the time-dependent block model given the snapshots. The model itself is generative. While others have explored the properties of networks generated from a pre-specified model (Leskovec et al. 2005), the focus here is on network model inference. The observed snapshots are a series of T time-ordered graphs. The goal is to infer a corresponding sequence of time-evolving stochastic block models, {M(t): t = 1, …, T}, where each M(t) is a good network-generative model for G(t). Many methods maximize the model for each snapshot independently, obtaining M (t) as arg max M P (M | G (t)), then attempt to stitch together the results. Dynamic network data In some disciplines temporal networks G (t) are directly observable through timestamps of vertices or edges accumulated over a certain period of time (Leskovec et al. 2005) (e.g., author–author citation networks).