Paper Info
Title
Algorithms Based on Density and Shared Neighbors for Functional Modules Identification in PPI Networks
Abstract
Accumulating evidence suggests that biological systems are composed of interacting, separable, functional modules—groups of vertices within which connections are dense but between which they are sparse. Identifying these modules is essential to understand the organization of biological systems. However, the most existing deterministic algorithms only find “dense” clusters. Actually, the modules are of differing sizes, densities and shapes. In this paper, we take into account the property of diversity of module topological structure, propose an efficient algorithm relying on density and shared neighbors for detecting overlapping modules in PPI (protein-protein interaction) networks. Our algorithm first finds the skeleton of the modules, SNCS(Shared Neighbor Connected Subgraph), then constructs the modules by expanding the leaf vertices of SNCS based on shared neighbors. Furthermore, since the PPI network is noisy and still incomplete, some methods treat the PPI networks as weighted graphs in which each edge (e.g., interaction) is associated with a weight representing the probability or reliability of that interaction for preprocessing and purifying PPI data. Thus, we extend our method into weighted networks which takes into account the link weights in a more delicate way by incorporating the subgraph intensity. We test our method on PPI networks. Our analysis of the yeast PPI network suggests that most of these modules have well biological significance in the context of protein localization, function annotation.
Year
DOI
Venue
2009
10.1109/BIBE.2009.6
BIBE
Keywords
Field
DocType
functional modules identification,weighted graph,ppi networks,weighted network,ppi network,protein-protein interaction,shared neighbor,yeast ppi network,biological significance,shared neighbors,biological system,purifying ppi data,efficient algorithm,protein localization,continuous phase modulation,biological systems,data mining,sun,bioinformatics,algorithm design and analysis,identification,modules,biomedical engineering,proteins,skeleton,molecular biophysics,computer science,clustering algorithms
Cluster (physics),Computer science,Separable space,Theoretical computer science,Artificial intelligence,Cluster analysis,Graph,Algorithm design,Vertex (geometry),Algorithm,Preprocessor,Molecular biophysics,Bioinformatics,Machine learning
Conference
ISSN
Citations 
PageRank 
2471-7819
1
0.36
References 
Authors
20
2
Name
Order
Citations
PageRank
Peng Gang Sun1997.76
Lin Gao213729.86