Network motif identification in stochastic networks
- Molecular and Computational Biology Program, University of Southern California, Los Angeles, CA 90089
-
Edited by Philip P. Green, University of Washington School of Medicine, Seattle, WA, and approved May 8, 2006 (received for review September 8, 2005)
Abstract
Network motifs have been identified in a wide range of networks across many scientific disciplines and are suggested to be the basic building blocks of most complex networks. Nonetheless, many networks come with intrinsic and/or experimental uncertainties and should be treated as stochastic networks. The building blocks in these networks thus may also have stochastic properties. In this article, we study stochastic network motifs derived from families of mutually similar but not necessarily identical patterns of interconnections. We establish a finite mixture model for stochastic networks and develop an expectation-maximization algorithm for identifying stochastic network motifs. We apply this approach to the transcriptional regulatory networks of Escherichia coli and Saccharomyces cerevisiae, as well as the protein–protein interaction networks of seven species, and identify several stochastic network motifs that are consistent with current biological knowledge.
Footnotes
- †To whom correspondence may be addressed at: MCB 201, 1050 Childs Way, Los Angeles, CA 90089. E-mail: tingchen{at}usc.edu or fsun{at}usc.edu
-
Author contributions: R.J., Z.T., T.C., and F.S. designed research; R.J. performed research; R.J. analyzed data; and R.J., T.C., and F.S. wrote the paper.
-
Conflict of interest statement: No conflicts declared.
-
This paper was submitted directly (Track II) to the PNAS office.
- Abbreviations:
- ChIP,
- chromatin immunoprecipitation;
- EM,
- expectation-maximization.
Abbreviations:
- © 2006 by The National Academy of Sciences of the USA
