Deterministic Graph-Theoretic Algorithm for Detecting Modules in Biological Interaction Networks
Accumulating evidence suggests that biological systems
exhibit modular organization. Accurate identification of modularity
is vital for understanding this organization. A recent
approach, Modules of Networks (MoNet), introduced an intuitive
module definition and a clear detection method based on a ranked
list of edges generated by the Girvan-Newman (G-N) algorithm.
The resulting modules from a yeast network showed significant
association with known biological processes, indicative of the
method's utility. Despite MoNet's usefulness, systematic bias in
the method leads to varied results across trials. MoNet modules
also exclude some network regions. Such deficiencies limit meaningful
analysis of a network. To address these shortcomings, we
have developed a deterministic G-N algorithm (dG-N) and a new
agglomerative algorithm, Deterministic Modularization of Networks
(dMoNet). dMoNet simultaneously processes structurally
equivalent edges while preserving the intuitive foundations of the
MoNet algorithm. dMoNet also includes all network nodes in the
identified modules, thus generating hypotheses with respect to a
full network. A GO-based method for comparison of dMoNet
to other modularization methods, including a currently favored
algorithm, shows an overall better performance by dMoNet when
analyzing large-scale yeast and human protein interaction networks.
This comparison method comprises a rational evaluation
of the quality of functional modules identified from large-scale
interaction networks. The code and resulting data from this work
are available upon request.
Index Terms
Algorithms, graph theory, interaction networks, modules.
Full Text (PDF)