• PNAS Apple App
  • Science Sessions: The PNAS Podcast Program

Inferring network mechanisms: The Drosophila melanogaster protein interaction network

  1. Manuel Middendorf ,
  2. Etay Ziv , and
  3. Chris H. Wiggins § , ,
  1. Communicated by Barry H. Honig, Columbia University, New York, NY, December 20, 2004 (received for review September 7, 2004)

Abstract

Naturally occurring networks exhibit quantitative features revealing underlying growth mechanisms. Numerous network mechanisms have recently been proposed to reproduce specific properties such as degree distributions or clustering coefficients. We present a method for inferring the mechanism most accurately capturing a given network topology, exploiting discriminative tools from machine learning. The Drosophila melanogaster protein network is confidently and robustly (to noise and training data subsampling) classified as a duplication–mutation–complementation network over preferential attachment, small-world, and a duplication–mutation mechanism without complementation. Systematic classification, rather than statistical study of specific properties, provides a discriminative approach to understand the design of complex networks.

Footnotes

  • To whom correspondence should be addressed at: Department of Applied Physics and Applied Mathematics, Columbia University, 500 West 120th Street, New York, NY 10027. E-mail: chris.wiggins@columbia.edu.

  • Author contributions: M.M., E.Z., and C.H.W. designed research; M.M., E.Z., and C.H.W. performed research; and M.M. wrote the paper.

  • Abbreviations: DMC, duplication–mutation–complementation; DMR, duplication–mutation using random mutations; LPA, linear preferential attachment; RDS, random static; RDG, random growing; AGV, aging vertex; SMW, small-world; ADT, alternating decision tree.

  • See Commentary on page 3173.

  • †† Two graphs are isomorphic if there exists a relabeling of their vertices such that the two graphs are identical.

    Related Article

    HighWire Press-hosted articles citing this article