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

Authors: Roger L. Chang, Feng Luo, Stuart Johnson, Richard H. Scheuermann

Addresses: Bioinformatics and Systems Biology Graduate Program, University of California San Diego, 9500 Gilman Dr., La Jolla, San Diego, CA 92093-0412, USA. ' School of Computing, Clemson University, 310 McAdams Hall, Clemson, SC 29634-0974, USA. ' Texas Advanced Computing Center, University of Texas Austin, 10100 Burnet Road (R8700), Austin, TX 78758-4497, USA. ' Department of Pathology, Division of Biomedical Informatics, University of Texas Southwestern Medical Center, 5323 Harry Hines Blvd, Dallas, Texas 75390-9072, USA

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.

Keywords: algorithms; graph theory; biological interaction networks; modules; betweenness; Girvan-Newman; dMoNet; deterministic modularisation; network modularisation; gene ontology; bioinformatics.

DOI: 10.1504/IJBRA.2010.032115

International Journal of Bioinformatics Research and Applications, 2010 Vol.6 No.2, pp.101 - 119

Published online: 10 Mar 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article