title: Discriminative topological features reveal biological network mechanisms.
abstract: BACKGROUND
  Recent genomic and bioinformatic advances have motivated the development of numerous network models intending to describe graphs of biological, technological, and sociological origin. In most cases the success of a model has been evaluated by how well it reproduces a few key features of the real-world data, such as degree distributions, mean geodesic lengths, and clustering coefficients. Often pairs of models can reproduce these features with indistinguishable fidelity despite being generated by vastly different mechanisms. In such cases, these few target features are insufficient to distinguish which of the different models best describes real world networks of interest; moreover, it is not clear a priori that any of the presently-existing algorithms for network generation offers a predictive description of the networks inspiring them.
  
  
  RESULTS
  We present a method to assess systematically which of a set of proposed network generation algorithms gives the most accurate description of a given biological network. To derive discriminative classifiers, we construct a mapping from the set of all graphs to a high-dimensional (in principle infinite-dimensional) "word space". This map defines an input space for classification schemes which allow us to state unambiguously which models are most descriptive of a given network of interest. Our training sets include networks generated from 17 models either drawn from the literature or introduced in this work. We show that different duplication-mutation schemes best describe the E. coli genetic network, the S. cerevisiae protein interaction network, and the C. elegans neuronal network, out of a set of network models including a linear preferential attachment model and a small-world model.
  
  
  CONCLUSIONS
  Our method is a first step towards systematizing network models and assessing their predictability, and we anticipate its usefulness for a number of communities.
authors.affiliation: Department of Physics, Columbia University, New York, USA. mjm2007@columbia.edu
authors.forename: Manuel
authors.initials: M
authors.lastname: Middendorf
authors.forename: Etay
authors.initials: E
authors.lastname: Ziv
authors.forename: Carter
authors.initials: C
authors.lastname: Adams
authors.forename: Jen
authors.initials: J
authors.lastname: Hom
authors.forename: Robin
authors.initials: R
authors.lastname: Koytcheff
authors.forename: Chaya
authors.initials: C
authors.lastname: Levovitz
authors.forename: Gregory
authors.initials: G
authors.lastname: Woods
authors.forename: Linda
authors.initials: L
authors.lastname: Chen
authors.forename: Chris
authors.initials: C
authors.lastname: Wiggins
mesh_terms: D000818:Animals; D017173:Caenorhabditis elegans / Q000502:physiology; D019295:Computational Biology / Q000379:methods*; D048168:Escherichia coli K12 / Q000235:genetics; D008954:Models, Biological; D008957:Models, Genetic; D008959:Models, Neurological; D009415:Nerve Net / Q000502:physiology; D016571:Neural Networks, Computer; D025941:Protein Interaction Mapping; D012441:Saccharomyces cerevisiae / Q000502:physiology; D029701:Saccharomyces cerevisiae Proteins / Q000378:metabolism
chemical_list: D029701:Saccharomyces cerevisiae Proteins