Greedily Mining l-dense Subgraphs in Protein Interaction Networks

Dense subgraphs of protein interaction networks are believed to be potential protein complexes and play an important role in analyzing cellular organization and predicting functions of proteins. In this paper, we present a new algorithm LD-Miner for mining l-dense subgraphs in protein interaction networks. We apply algorithm LD-Miner to the protein interaction network of Saccharomyces cerevisiae collected from MIPS. Many well known protein complexes annotated by manually are detected. We also match our predicted clusters to the known complexes systematically analyzed by Given et al., Ho et al., and Krogan et al., compared to other previous density-based algorithms, LD-Miner matches much more experimentally determined complexes and known complexes by systematic analysis. Moreover, LD-Miner is very fast, which can be used in even larger biological networks.