Deterministic graph-theoretic algorithm for detecting modules in biological interaction networks

Int J Bioinform Res Appl. 2010;6(2):101-19. doi: 10.1504/IJBRA.2010.032115.

Abstract

An approach for module identification, Modules of Networks (MoNet), introduced an intuitive module definition and clear detection method using edges ranked by the Girvan-Newman algorithm. Modules from a yeast network showed significant association with biological processes, indicating the method's utility; however, systematic bias leads to varied results across trials. MoNet modules also exclude some network regions. To address these shortcomings, we developed a deterministic version of the Girvan-Newman algorithm and a new agglomerative algorithm, Deterministic Modularization of Networks (dMoNet). dMoNet simultaneously processes structurally equivalent edges while preserving intuitive foundations of the MoNet algorithm and generates modules with full network coverage.

Publication types

  • Research Support, N.I.H., Extramural
  • Research Support, U.S. Gov't, Non-P.H.S.

MeSH terms

  • Algorithms*
  • Protein Interaction Mapping / methods
  • Proteome / analysis*
  • Proteomics / methods*

Substances

  • Proteome