Complex Biological Networks

  Presentation #1: Network Topology
  Presentation #2: Metabolic Networks Analysis

Reading (these are some of the papers we will discuss in class)

Network Topology:
»  Error and attack tolerance of complex networks, R Albert et al., Nature, 2000
»  Exploring complex networks, SH Strogatz, Nature, 2001
»  Statistical mechanics of complex networks, Albert and Barabasi, Reviews of modern physics, 2002 (a good review paper)
»  The structure and function of complex networks, MEJ Newman, SIAM review, 2003
»  Network motifs in the transcriptional regulation network of Escherichia coli, SS Shen-Orr et al., Nature Genetics, 2002
»  Superfamilies of Evolved and Designed Networks, R Milo, et al., Science, 2004
»  Network biology: understanding the cell's functional organization, Barabasi and Oltvai, Nature Reviews Genetics, 2004

Metabolic Networks Analysis:
»  The large-scale organization of metabolic networks, Jeong et al., Nature, 2000
»  The Escherichia coli MG1655 in silico metabolic genotype: its definition, characteristics, and capabilities, Edwards and Palsson, PNAS, 2000
»  In silico predictions of Escherichia coli metabolic capabilities are consistent with experimental data, JS Edwards et al, Nature biotechnology, 2001
»  Genome-scale microbial in silico models: the constraints-based approach, ND Price et al., Trends in Biotechnology, 2003
»  Genome-scale models of microbial cells: evaluating the consequences of constraints, ND Price et al. Nature Reviews Microbiology, 2004
»  Large-scale reconstruction and phylogenetic analysis of metabolic environments, Borenstein et al., PNAS, 2008
»  Topological signatures of species interactions in metabolic networks, Borenstein and Feldman, JCB, 2009

Homework Assignment (*** clarification: you can submit the assignment until 4/25/2014 ***)

In this assignment you will analyze network motifs in a metabolic network and visualize them using Cytoscape.

Part I:

Download the metabolic network of the endosymbiont Buchnera aphidicola (found here). Each line in this file represents a directed edge, linking a substrate to a product (separated by a tab character).

Write a program that reads this network as input and calculate the enrichment of each motif, following the procedure described in class. The full details can be found in the following paper: Milo, et al., Science, 2002, Network motifs: simple building blocks of complex networks. Check also the "Supporting Online Material" of this paper for all the details concerning the procedure. In short (but do make sure to read the full description in the paper above), count the number of occurrences of each of the 13 possible 3-node subgraphs in the network, and compare it to the number of occurrences in 100 randomized networks. You can use either of the two randomization algorithms described (pay attention to the section "Controlling for Appearances of (n-1)-Node Motifs" and make sure to preserve the number of mutual edges). As an output, print a table listing for each subgraph the number of occurrences in the original network, the mean and standard deviation of the number of occurrences in the randomized networks, the number of randomized networks in which the number of occurrences was equal to or higher than the number of occurrences in the original network, and the number of randomized networks in which the number of occurrences was equal to or lower than the number of occurrences in the original network. You can use the subgraph numbering illustrated in the slides and in the paper (in which, for example, a feed-forward loop is subgraph #5). It is not required to examine which of the 3-node subgraphs can be classified as an enriched motif according to the 3 criteria mentioned in class.

Additionally, the program should print out one of your randomized networks, in a similar format to that of the input file.

Part II:

Use Cytoscape ( to visualize the original network: Import the network file using File->Import->Network_from_Table. Use Layout->yFiles->Organic to better layout the network. Create a PDF file illustrating the network using File->Export->Network_View_as_Graphics.

Repeat the above for the one randomized networks you created in part I.


Make sure to submit the following files:

1) Source code of your program.

2) The output table listing the statistics for each 3-node subgraph (as described above).

3) The output network file describing a randomized network.

4) Two pdf files: one illustrating the original graph and one describing a randomized graph.