Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
7380233 | Physica A: Statistical Mechanics and its Applications | 2014 | 12 Pages |
Abstract
Discovering motifs in protein-protein interaction networks is becoming a current major challenge in computational biology, since the distribution of the number of network motifs can reveal significant systemic differences among species. However, this task can be computationally expensive because of the involvement of graph isomorphic detection. In this paper, we present a new algorithm (CombiMotif) that incorporates combinatorial techniques to count non-induced occurrences of subgraph topologies in the form of trees. The efficiency of our algorithm is demonstrated by comparing the obtained results with the current state-of-the art subgraph counting algorithms. We also show major differences between unicellular and multicellular organisms. The datasets and source code of CombiMotif are freely available upon request.
Related Topics
Physical Sciences and Engineering
Mathematics
Mathematical Physics
Authors
Jiawei Luo, Guanghui Li, Dan Song, Cheng Liang,