title: Network motifs come in sets: correlations in the randomization process.
abstract: The identification of motifs--subgraphs that appear significantly more often in a particular network than in an ensemble of randomized networks--has become a ubiquitous method for uncovering potentially important subunits within networks drawn from a wide variety of fields. We find that the most common algorithms used to generate the ensemble from the real network change subgraph counts in a highly correlated manner, such that one subgraph's status as a motif may not be independent from the statuses of the other subgraphs. We demonstrate this effect for the problem of three- and four-node motif identification in the transcriptional regulatory networks of E. coli and S. cerevisiae in which randomized networks are generated via an edge-swapping algorithm. We find strong correlations among subgraph counts; for three-node subgraphs these correlations are easily interpreted, and we present an information-theoretic tool that may be used to identify correlations among subgraphs of any size. Our results suggest that single-feature statistics such as Z scores that implicitly assume independence among subgraph counts constitute an insufficient summary of the network.
authors.affiliation: Division of Natural Sciences and Mathematics, Bennington College, Bennington, Vermont 05201, USA. reid.ginoza@gmail.com
authors.forename: Reid
authors.initials: R
authors.lastname: Ginoza
authors.forename: Andrew
authors.initials: A
authors.lastname: Mugler
mesh_terms: D018407:Bacterial Physiological Phenomena; D001426:Bacterial Proteins / Q000378:metabolism*; D003198:Computer Simulation; D008954:Models, Biological; D015233:Models, Statistical; D020543:Proteome / Q000378:metabolism*; D015398:Signal Transduction / Q000502:physiology*
chemical_list: D001426:Bacterial Proteins; D020543:Proteome