ParaMODA: Improving Motif-Centric Subgraph Pattern Search in PPI Networks

Abstract

Finding motifs in networks usually involves traversing through the network to enumerate all possible subgraphs of a given size, and then determining their statistical uniqueness by sampling subgraphs from many randomly generated networks that share similar features with the original network. Current algorithms for network motif analysis can be categorized into either network-centric or motif-centric algorithms. While network-centric algorithms cannot choose the subgraph patterns to search, motif-centric algorithms can search specific subgraph patterns in the network. Researchers interested in just one or a few subgraph patterns will find motif-centric tools useful since there will be no redundant work finding subgraphs they do not care about. In this paper, we present ParaMODA which improves a motif-centric tool, and incorporates existing motif-centric algorithms as well as a new algorithm for carrying out the same task. ParaMODA can also collect and store discovered instances on the disk for future retrieval and analysis. Experimental results show that ParaMODA outperforms the existing ones, although the performance improvements vary depending on the set of query graphs used. More importantly ParaMODA allows for parallelization of huge chunks of the task which will be helpful, especially for studying motifs of double-digit sizes in large networks.

Publication
IEEE International Conference on Bioinformatics and Biomedicine (BIBM)
comments powered by Disqus